RSS

Category Archives: Algorithms

Adobe Interview Questions

Its been a long time made any posts on this blog. Let me try to share a bunch of my interview experiences. Starting with the letter A 😉 – Adobe

I had an interview with Adobe in early 2009 in their Bangalore Office, when Trilogy was shutting down its Office. I had about 8 months work experience by then

It started with a written test for 2 hours. There were about 7 or 8 (out of 80+) folks short listed for further rounds.

First Round:
1. There was a discussion around Makefiles

2. I heard a new term in this question – Distributed compilations. The questions was – how would you design such a system. A basic introduction was given about the system.

3. Assume there is a “container” the container have some “components” and each component in turn contains “items”, the components have some “properties”, also the items have some properties and some components depend on the properties of some other components by which I mean if the property of one component changes then the components behaviour which is dependent on this should alter. What data structure would you use in order to maintain this information.

4. Given 2 linked lists how to find the intersection. Imagine a Y shaped linked list.

Second Round:
1. You know malloc and free() functions. malloc knows the number of bytes to allocate, where as free() just takes a pointer and frees the same amount of memory that has been allocated to this address. if I ask you to implement this malloc() and free(), what would be underlying Data Structure that you would use in order to maintain the information required. It was a good discussion on complexity various approaches etc.
2. Given a string find first non-repeating character.

3. And some good ones which I don’t remember

Third Round
1. Reverse a linked list recursively without using global variables

2. Finding anagrams of a given word from a dictionary

3. Forgot the rest 😦

Fourth Round:
1. Discussion about Yahoo! project,work in Trilogy, technologies known.

2. How to implement a generic stack in Java

 
Leave a comment

Posted by on July 28, 2013 in Algorithms

 

Tags: , , ,

Find nodes in a binary tree which are at a distance K from a given node

You are given a binary tree and a node in the tree, your task is to find all the nodes in the binary tree which are at a distance K from that node. These nodes can be downwards [descendants of the node] or upwards.

For example: In this image

http://www.cs.mcgill.ca/~jeromew/comp252/images/Binary_tree.png

The nodes that are at a distance 2 from 7 are 5 (6’s left child), 11, 5 (2’s right child).

This is a coding question.

Function prototype:

void PrintKDistanceNode(Node *root, Node *node, int K)

{

}

 
2 Comments

Posted by on July 19, 2012 in Algorithms

 

Tags: , ,

Binary Search Tree in Binary Tree

Given a binary tree, find the largest binary SEARCH tree in this binary tree.

When I mean largest, the tree with maximum number of nodes. And the binary search tree should be a sub-tree in the given binary tree.

Note: Not every binary tree is a binary search tree 😛

 
8 Comments

Posted by on August 13, 2010 in Algorithms

 

Tags: , ,

Interview Question : Print nodes of a Binary Tree level order from leaves to root

I think most of you might know about Breadth First Search (BFS), in which you print nodes of a tree from root to leaves. Now there is a small change to the way the nodes are printed. Lets say given a binary tree, I want the nodes to be printed level order but from leaves to root

Eg :  consider the binary tree at this locations http://www.cs.mcgill.ca/~jeromew/comp252/images/Binary_tree.pn

Now you need to print : 5 11 4 2 6 9 7 5 2

 
4 Comments

Posted by on May 8, 2010 in Algorithms

 

Tags: , , ,

Find the height of the tree

You are given an array of length N. The array stores information about an n-ary tree. And the n-ary tree has N-nodes numbered 0 – (N-1).The ith index in the array contains the parent nodes number j. Given this array find the height of the tree. The parent of the root is -1

It would be good to solve this problem in O(n).

 
5 Comments

Posted by on January 1, 2010 in Algorithms

 

Tags: , , ,

Find the Common Ancestor

How do you find the nearest/least common ancestor of two nodes in a
1. Binary Search Tree
2. Binary Tree

Assume the following two situations in the above cases :
1. Parent pointer is given
2. Parent pointer is not given.

 
Leave a comment

Posted by on December 9, 2009 in Algorithms

 

Tags: , ,