Amazon Interview Question for Systems Design Engineers

Country: India
Interview Type: Phone Interview

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

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

Comment hidden because of low score. Click to expand.
0

O(n) for intersection and then n(logn) for finding out the height.. good solution.

Comment hidden because of low score. Click to expand.
0

That'd be O(N^2) in time

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

#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
}

}

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;
}

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

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?

Comment hidden because of low score. Click to expand.
0

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..??

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

int height = Traverse(Map[-1],0)

to find the height.

Comment hidden because of low score. Click to expand.
0

I too came up with exactly this solution. By far the best linear time algo.

Comment hidden because of low score. Click to expand.
0

You need to understand that your algorithm depends upon the number of children each parent has. This O ( V + E ) where V is the number of nodes and E is the number of edges in the graph(i.e. number of children each parent has).This is not O(n).

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

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.

Comment hidden because of low score. Click to expand.
0

recheck your code with one more entry say value: 4, Index: 6

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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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)..

Comment hidden because of low score. Click to expand.
0

Find the maximum value after traversing for all leaf nodes.

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

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;
}``````

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

int height(int arr[])
{
HashMap h = new HashMap();
for(int i =0 ;i<arr.length;i++)
{
if(h.get(arr[i]) ! = null)
{
h.put(arr[i], '1');
}
}
return h.size();
}

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

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.

Comment hidden because of low score. Click to expand.
0

I am not sure Tom but this is for appstore SDE Bangalore India. I already had F2F interview long before, don't know the final result..

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.

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.