Amazon Interview Question
Systems Design EngineersCountry: India
Interview Type: Phone Interview
#include<stdio.h>
#include<stdlib.h>
int Total[100];
int Height(int a[],int n,int i)
{
if(a[i]==-1) //it's root node
{
Total[i]=0;
return 0;
}
else
{
Total[i]=1+Height(a,n,a[i]); //1+height of parent
return Total[i];
}
}
int main()
{
int a[]={3,2,-1,2,0,1};
int n=sizeof(a)/sizeof(a[0]);
int i,j;
for(i=0;i<n;i++)
Total[i]=-2;
for(i=0;i<n;i++)
{
if(Total[i]==-2)
Height(a,n,i);
}
for(i=0;i<n;i++)
printf("%d %d\n",i,Total[i]);
getchar();
return 0;
}
Good question I suppose. You can maintain a hashmap with keys being equal to the (integer) roots and value can be an array/list of child.
So your hashmap would be like (for the above example)
map[-1] = 3
map[3] = (1,2,4)
map[1] = (0,5)
Creating the map should take O(n) and traversing should take O(n) (write a recursive function to traverse - should be easy). Overall, you can improve the running time to O(n).
Any better solutions?
how it will be O(n) suppose you have node 6 link to 2 so what will happen... or if we have a bigger graph then what..??
Whatever be the case.. Creation of the map would take O(n).
I think the second part confuses you. What I am trying to say here is, map[-1] is always the root. Lets take the above example itself (along with node 6 link to 2)
map[-1] = 3
map[3] = (1,2,4)
map[1] = (0,5)
map[2] = (6)
If we traverse in a function like:
int Traverse(List<int> l, int height)
{
if(list == null)
{
return height;
}
int maxHeight = height;
foreach(int a in L)
{
int h = Traverse(Map[i], height+1);
if(h>maxHeight)
maxHeight=h;
}
return maxHeight;
}
The above is more of a pseudo code (not syntactically correct). The algorithm works in O(n) because the traversal will hit each node once and there are n nodes.
If there is no space complexity
1) Create a boolean array of size(input array) + 1.
2) Loop through the input array, set the index of the boolean true .
for the given example:
if my new array is say B and given input array is say A.
B[A[i] + 1] = true;
where i ranges from 0 to size-1 of input array.
3) Then loop through the B array and count at how mnay indexes you have set true.
4) Count gives the height of your tree.
If there is no space complexity
1) Create a boolean array of size(input array) + 1.
2) Loop through the input array, set the index of the boolean true .
for the given example:
if my new array is say B and given input array is say A.
B[A[i] + 1] = true;
where i ranges from 0 to size-1 of input array.
3) Then loop through the B array and count at how mnay indexes you have set true.
4) Count gives the height of your tree.
this solution work only for this example what if node with label 2 will have a child with value 6.
your solution will result 4 but the ans is still 3
yes sanjay you are correct, its my mistake.
Now i have the B array which can tell me what all nodes are leaf nodes(which are false). So i traverse from leaf node to root node and have a counter to store number of nodes i pass thorugh.
By this new B array we need to traverse the tree for leaf nodes only. But i think the complexity will still be O(n^2)..
Take an int array of size n which will store the height of node, initialise it with -1
int height[i];
int findMaxHeight( int * data, int n)
{
int * height = new int(n);
memset(height, n, -1);
for( int i=0; i < n; i++)
{
if( height[i]!=-1)
continue;
height[i] = findHeight(data,height,i);
}
return max(height);
}
int findHeight(int * data, int * height, int i)
{
if(data[i]==-1)
return 0;
height[data[i]] = findHeight(data,height,data[i]);
return height[data[i]] +1;
}
Hello Sanjay,
I noticed your origin is India. Is the phone interview being held at India with the interviewer also? Is there Amazon R&D office at India? Is it outsourcing?
I will be surprised if the intensive interview is meant for the offshore contractors and outsourced companies.
Thanks for answering.
I think we can find all the leaves node by taking intersection with parent indices of all available node and available indices and then we can traverse from each leave node to root to find the max height....
- Ajay March 20, 2012-Ajay