ADP Interview Question for Analysts


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

DP question...use an extra array with values initialized to -1.
Now, for each unvisited vertex(i.e., whose arr[i] value is -1) call a recursive function getHeight. Here's the pseudo code for getHeight function

getHeight(index){
	if(parent == -1)return 0;//root case
	if(height[parent] != -1)return height[parent]+1;
	height[parent] = getHeight(parent);
	return height[parent]+1;
}

Clearly the above problem satisfies both Optimal substructure property and overlapping subproblems. :)

- Harsha October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The second line in the above pseudo code just avoids recalculating the heights of already calculated nodes(overlapping subproblems). and the height array stores the distance from the root to current node. And the final height of the tree will be the maximum value in the height array :) :)

- Harsha October 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes! This is the solution I had in mind! This is right! I would call the attribute to be depth at each node. It is definitely DP problem.

- Dalek October 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

See an iterative version of this solution below.

- gudujarlson October 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi,
My reply is like this. take one hash map , keep on adding parents as key's and corresponding children as values.
ex: let us assume -1,0,1,6,6,0,0,2,7 is the array.

now the hash map will be {excluding -1 , as -1 represents that index as root. so in this case , 0 is root}
0 - 1,5,6
1 - 2
6 - 3,4
2- 7
7-8.
Now take the root element. here it is 0 .
so take one queue and insert values as mentioned in followoing manner

queue.push(1,5,6) length = 1;
pop 1,5,6 .. queue.push(2,3,4) = length ++; // length = 2 // here we have pop'd the queue .. and considered those as keys , and inserted , the values of those keys.

again pop 2,3,4 .. push , 7 = length++; // length = 3;

again pop 7 , push 8 ; length ++ // length = 4.
pop 8 .. now as we dont have any node which acts as parent , length is 4..

time complexity is 0(n) , and space is 0(n) ..

can any one plz correct my understanding ?

- gopi.komanduri October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I did not get the part where after first pushing 1,5,6 as children of root, you then pop elements one by one and push their children to the back of the queue. Am I correct? So you first pop 1, then push its children which is 2. The queue now has 5,6,2. How would you determine exactly when to increment length in this case?

- Aadarsh Kenia January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question relies on the UnionFind algorithm whereby each entry in an array points to either the sentinel value (root -1) or it's parent node. By doing a search through these unions and caching results, we can obtain O(n) run time and O(n) space complexity. The algorithm goes:

1. For each node in the list, if it is already cached or -1 skip it, otherwise move on...
2. Set depth to 0 and node to array[i]
3. While array[i] is not -1 check to see if it is cached
4. If array[i] is cached, then add current depth to cache depth, otherwise move to new node and add 1 to depth counter
5. Once you hit root or a cached node, updated the depth for your node at cache[i] to be the final depth
6. At then end, look at all cached results and return the maximum depth

Java code example:

public static int findDepth(int[] p, int[] cache){
	
	//Cycle through all elements to determine depth calculation
	for(int i = 0; i < p.length; i++){
		int depth = 0;  //Depth accumulator
		
		//Check to see if we have visited this node previously, or if this is the root
		if(cache[i] > 0 || p[i] == -1) continue;
		int node = p[i];
		
		//Transition node to node and accumulate depth count
		while(p[node] != -1){
			//If we find a previously visited node, add our current depth to it's depth and cache result
			if(cache[node] > 0){
				depth += cache[node];
				break;
			}
			else{
				node = p[node];
				depth++;
			}
		}
		cache[node] = depth;
	}
	
	//Find our largest depth and return that as the result
	int result = 0;
	for(int i: cache){
		if(i > result){ result = i; }
	}
	
	return result;
}

- masterjaso October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code returns 0 in all cases. Did you mean "cache[i] = depth;" instead of "cache[node] = depth;"?

- gudujarlson October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, assuming I understand what you are trying to implement, I think the worst case complexity is O(n^2). Consider this input: {1,2,3,4,5,6,7,8,-1}. Your solution will walk up the full tree n times which will lead to n+(n-1)+(n-2)+...1 visitations. This can be fixed by using a stack to record the depth of each node as you walk up the tree. See my solution.

- gudujarlson October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

hey got in one more way.
have taken one more array . in that array I am incrementing heights like explained below :
-1,0,1,6,6,0,0,2,7
filling lengths in the corresponding parent indexes and placing the negative parent index in that child index. why we need this is , to maintain lengths , by accessing parent index length .
a[0] = 1
a[1]= 2
a[2]= -1
a[3]=-6
a[4]=-6
a[5]=-0
a[6] = 3
a[7]=3
a[8]=4 .. the maximum val is the length of the tree

- gopi.komanduri October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution walks up the tree to determine the depth of each node and remembers the maximum depth. To keep time complexity to O(n), the calculated depths are stored in an auxiliary array. Time O(n), Space O(n).

int height(int a[]) {
		ArrayDeque<Integer> deque = new ArrayDeque<Integer>();
		int maxHeight = 1;
		int height[] = new int[a.length]; // Cache of computed heights.
		for (int i = 0; i < a.length; ++i) {
			
			// If we have already calculated a height for this node, continue.
			if (height[i] > 0) {
				continue;
			}
			
			// Is this is the root node, record its height and continue;
			if (a[i] == -1) {
				height[i] = 1;
				continue;
			}
			
			// Walk up the tree until we find a node with a known height.
			int j = a[i];
			while (j >= 0 && height[j] == 0) {
				deque.push(j);
				j = a[j];
			}
			
			// Walk back down the tree and record the height of each node.
			int h = j >= 0 ? height[j] : 0;
			while (deque.size() > 0) {
				j = deque.pop();
				height[j] = ++h;
			}
			height[i] = height[j] + 1;
			
			// Remember the maximum height.
			if (height[i] > maxHeight) {
				maxHeight = height[i];
			}
		}
		return maxHeight;
	}

- gudujarlson October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If I have understood the question properly:

int lastIdx = arr.length - 1;
int height = 1;
while(lastIdx > 0) {
	++height;
	lastIdx = arr[lastIdx - 1];
}
return height;

1. Imagine nodes are numbered 1 to n.
2. The value at index 0 is -1 because there is no parent for root or the 1st node, at index 1 is the node number of parent of 2nd node and so on.
3. Start from the last element of the array and jump on to the parents until there are none.

On the other hand, if the array holds the value (and not the number i.e. 1st, 2nd etc.) of parent node the answer to this question is the number of unique nodes in the array.

If someone disagrees, please share an example of how that array is created possibly with a picture of the tree. Thanks

- Asif Garhi November 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

When you say parent of the ith node - the sequence in which the tree is traversed to populate this array matters. Can you please specify the sequence in which the tree is traversed and also what is the type of the array P[]? Is it array of Nodes with each Node having value and children fields?

Please suggest.

Thanks

- Asif Garhi November 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ParentArrayHeightTree {

	
	public static  int heightoftree(int[] parent){
		int max_height=Integer.MIN_VALUE;
		for(int i=0;i<parent.length;i++){
			int height=1; 
			int current = parent[i];
			while(current !=-1){
				height++;
				current= parent[current];
			}
			
			if(h>max_height){
				max_height=h;
			}
		}
		
		return max_height;
	}
	
	
	public static void main(String[] args){
		int[] parent1 = {1,5,5,2,2,-1,3};
		
		System.out.println("height of tree {1,5,5,2,2,-1,3} :"+ heightoftree(parent1));
		
		int[] parent2 = {-1,0,0,1,1,3,5};
		System.out.println("height of tree {-1,0,0,1,1,3,5}:"+ heightoftree(parent2));
	}
}

o/p:
height of tree {1,5,5,2,2,-1,3} :4
height of tree {-1,0,0,1,1,3,5}:5

Input: parent[] = {1 5 5 2 2 -1 3}
Output: 4
The given array represents following Binary Tree
5
/ \
1 2
/ / \
0 3 4
/
6


Input: parent[] = {-1, 0, 0, 1, 1, 3, 5};
Output: 5
The given array represents following Binary Tree
0
/ \
1 2
/ \
3 4
/
5
/
6

- pnd1901 January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int maxDepth(int[] array){
		int maxDepth=0;
		int[] arrayCopy = new int[array.length];
		Arrays.fill(arrayCopy, 0);
		for (int i = 0; i < array.length; i++) {
			int j = array[i];
			if(j==-1){
				arrayCopy[i]=0;
			}else if(arrayCopy[j]>0){
				arrayCopy[i]=arrayCopy[j]+1;
			}else{
				int count=1;				
				while(array[j]!=-1 && arrayCopy[j]==0){					
					j=array[j];
					count++;
				}
				arrayCopy[i]=arrayCopy[j]+count;
			}
			if(arrayCopy[i]>maxDepth)
				maxDepth=arrayCopy[i];
			System.out.println(Arrays.toString(arrayCopy));
		}
		return maxDepth;
	}

- Tarun April 04, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More