ADP Interview Question
AnalystsCountry: India
Interview Type: In-Person
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 :) :)
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.
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 ?
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?
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;
}
Your code returns 0 in all cases. Did you mean "cache[i] = depth;" instead of "cache[node] = depth;"?
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.
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
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;
}
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
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
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
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;
}
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
Clearly the above problem satisfies both Optimal substructure property and overlapping subproblems. :)
- Harsha October 31, 2014