Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


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

#include<stdio.h>
#define max(a,b) (a>b?a:b)
#define size 9
int a[size],b[size];
void level(int);
int main()
{   
    int i,j=-1;
    printf("Enter the elements(size = 9) :\n");
    for(i=0;i<size;i++)
    {    b[i]=-1;
         scanf("%d",&a[i]);
    }
    for(i=0;i<size;i++)
         level(i);
    for(i=0;i<size;i++)
         j=max(b[i],j);
    printf("Height of the tree is %d\n",j);
    
    return 0;    
}

void level(int i)
{
     if(a[i]==-1)
          b[i]=0;
     else if(b[a[i]]!=-1)
          b[i]=b[a[i]]+1;
     else {
          level(a[i]);
          b[i]=b[a[i]]+1;
     }
     return;
}

- Barney on July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think height should be j+1 instead of j as j implies max of no. of ancestors of a node.......u r not including that node......

- crazygeek on July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I would concur with crazygeek. However, that just depends on the definition of height and is very easily fixed.

There's no need to have a return at the end of a void function.

- Anonymous on July 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't this recursing through the height of the tree? that would make this O(n^2).

- Anonymous on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Yes, it's recursing through the height of the tree. No, that doesn't make it O(N^2). It's O(N). Each call to "level" does O(1) work before possibly calling "level" again, but another call to "level" can only happen if "level" has never been called with the given argument before. So a maximum of O(N) calls to "level" can be opened, each of which costs O(1) time and O(1) space to evaluate, for a total cost of O(N) time and O(N) space.

- eugene.yarovoi on July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

A small change wud make it better:
for(i=0;i<size;i++)
level(i);
change it to
for(i=0;i<size;i++){
if(b[i]==-1)
level(i);
}

- tez on August 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you put in simple words what leveling here means?

- Anonymous on September 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The worst case is quadratic. An illustration would help , if my tree is linear like
0->1->2->3->4->5
the array would be
Parent = - 1 0 1 2 3 4
index = 0 1 2 3 4 5

The level api will have to ripple back to zeroth index always , when this has happens i times for ith call , n time for n th call.
Quadratic !

- Bhargav on December 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Bhargav: It doesn't ripple back to 0 every time. It uses cached results obtained previously to avoid that. That's what this snippet does:

else if(b[a[i]]!=-1)
          b[i]=b[a[i]]+1;

- eugene.yarovoi on April 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

here is O(n) solution
1.for each entry in the array,
-> look up in hashmap for the value(parent)
if there is an entry add the child(index) to it and add child to hashmap
else
create one entry for the value(parent) and add child(index) to it and add both to
hashmap

At the end you end up with n-ary tree. Now calculate depth of it O(n).

- Siva on July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This requires you to actually build nodes that have storage for child pointers, which uses more space than a more optimized solution. This also requires a hashtable, which significantly increases the constant factor over an array-only solution. It also means you get O(N) expected, not deterministic time.

You can solve this in O(n) deterministic time, and with a much lower constant factor too, by just using a couple arrays.

- eugene.yarovoi on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Eugene can you explain how will the deterministic time algorithm actually work?

- Unknown on July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I had the same solution in mind as Barney, the top-voted answer. I would have used iteration instead of recursion to make it more efficient.

- Anonymous on July 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Both the recursive and iterative variants are deterministic O(n) though.

- Anonymous on July 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

PA (ParentArray) be the given Array.

TempArray = new int[PA.length];

Initialize TempArray elements to -1;


for( int i=0; i<PA.length;i++){
populateTempArray(PA,i);
}



function populateTempArray(PA,i){
if(PA[i] == -1){
tempArray[i] =0;
}
if(TempArray[i]!=-1){
return;
}
if(TempArray[PA[i]]==-1){
populateTempArray(PA,PA[i]);
}
TempArray[i] = TempArray[PA[i]]+1;
}


Now loop Throgh TempArray to find the Max no, which corresponds to height.

- Anonymous on July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks grt algo

- aaman.singh85 on October 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use DP.
Say we want to calculate the height of a node p. So, its height is equal to the height of its parent plus 1.
So, while calculating the height of a node, store it somewhere so that we do not need to calculate the height again once we fall in the same path.

Lets take an example of a BST: 1,2,3,4;
For calculating the height of 3, we need height of 2. However its already stored[using DP]
Hope its clear.

#include <stdio.h>
#include <limits.h>
 
int findheight(int *par,int size)
{
        int i,j,height[size],count,maxheight;
        
        for(i=0;i<size;i++)
                height[i]=0;
 
        for(i=0;i<size;i++)
        {
                count=0;j=i;
                while(par[j]!=-1 && !height[j])
                {
                        ++count;
                        j=par[j];
                }
                height[i]=count+(j!=i?height[j]:0);
        }
        maxheight=INT_MIN;
        for(i=0;i<size;i++)
                if(maxheight<height[i])
                        maxheight=height[i];
        return maxheight;
}
 
int main()
{
        int par[]={-1,0,1,6,6,0,0,2,7},size;
        size=sizeof(par)/sizeof(par[0]);
 
        printf("%d ",findheight(par,size));
        return 0;
}

ideone.com/vCLF4

- Aashish on July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In worst case ,it will still be O(n^2).
{1 2 3 4 -1}

- grave on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's true, this is O(n^2), for instance, in the case of a degenerate tree that becomes a linked list. However, there's a fairly simple fix. When searching until you find a parent whose depth is known, keep track of all previously unseen nodes in the path, and then backtrack through them and assign their depths. For instance, if you see 5 -> 8 -> 13 -> 45 -> 3 and that's where it stops because the depth of 3 is known to be, let's say for example, 2, you should store the sequence 5 -> 8 -> 13 -> 45 -> 3 somewhere and then backtrack, saying 45 is depth 3, 13 is depth 4, 8 is depth 5, 5 is depth 6. That way you can see that each node is traversed exactly once and the algo is O(N).

- eugene.yarovoi on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Isn't this recursing through the height of the tree? that would make this O(n^2).

- Anonymous on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry posted in wrong place. please ignore the above comment.

- Anonymous on July 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have a similar approach, and while traversing from current "node" up to the root, I store all intermediate nodes on a stack so that I can set their heights after I reached the root. I also would stop traversing once I encounter a "node" with a known height.

static int height(int[] parent) {
  int len = parent.length;
  int[] height = new int[len];
  int maxHeight = 0;
  for(int i=len-1; i>=0; i--) {
    int n = i;
    Stack<Integer> stack = new Stack<Integer>();
    while(parent[n] != -1) {
      if(height[n] > 0) // optimization when height is already known
        break;
      stack.push(n);
      n = parent[n];
    }
    int depth = height[n] + 1;
    while(!stack.isEmpty()) {
      n = stack.pop();
      height[n] = depth++;
      maxHeight = Math.max(maxHeight, height[n]);
    }
  }
  return maxHeight + 1;
}

- Sunny on January 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public int findDepth(int[] input) {
		List<Integer>[] children = new ArrayList[input.length];

		for (int i = 0; i < input.length; i++) {
			int parent = input[i];
			if (parent == -1)
				continue;
			if (children[parent] == null) {
				children[parent] = new ArrayList<>();
			}
			children[parent].add(i);
		}
		return findDepth(0, children);
	}

	private int findDepth(int root, List<Integer>[] children) {
		List<Integer> list = children[root];
		if (list == null)
			return 0;
		int depth = 0;
		for (Integer child : list) {
			depth = max(depth, findDepth(child, children));
		}
		return depth + 1;
	}

- mykola on July 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Yoda coding not good. Yoda do pseudo code write.

struct node {
int val;
struct node *next;
}node;

//A simple hash-map from int to node *. Supports chaining
HASHMAP<int, node*> theMap;

FILL_MAP(int A)
{
	for(int i=0;i<A.length(); i++)
		theMap[A(i)].PUSH_BACK( i);

}

int recurse_map(int node_val){
	if( NOT_EXIST( theMap[node_val] ) ) return 0;
	node * p= GET_FIRST_ELEMENT(theMap[node_val]);
	int cur_ht=0; int max_ht=0;
	while(p)
		{
		cur_ht=recurse_map(p->val);
		if(max_ht<cur_ht) max_ht=cur_ht;
		p=p->next;
		}
	return max_ht+1;
	}



int FIND_HEIGHT_N_ARY( int A[]) {
	FILL_MAP(A);
	return recurse_map(-1);
	}

IF Understand you not Yoda ask. Yoda code Proper then.

- Yoda on July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yoda hang yourself do. Reason Yoda English 'Shake'speare

- Anonymous on July 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package puzzles.twostacks;

public class TreeArrayHeight {

int getAndSetHeight(int[] array, int index) {

if (array[index] == -1) {
return 1;
}
if (array[index] >= 0) {
array[index] = -(getAndSetHeight(array, array[index]) + 1);
}
return -array[index];
}

public void getMaxHeight(int[] array) {
for (int i = 0; i < array.length; i++) {
getAndSetHeight(array, i);
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < array.length; i++) {
min = Math.min(min, array[i]);
}
System.out.println(-min-1);
}

public static void main(String[] args) {
new TreeArrayHeight().getMaxHeight(new int[]{-1,0,1,2,3,4});
}
}

- gadolin on July 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Access to parent node is given i.e. parent(x) = array[x].
Sub-problem: Given any node and only parent pointer/references, find out its height from root. Cache the stuff to avoid re-calculation at each stage.

- Anonymous on July 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. O(n^2)

for(int i=0; i<n;i++)
{
p=Parent[i];
while(p!=-1)
{
Height[p]=max(Height[p], Height[i]+1);
i=p;
p=Parent[i];
}
}
return Height[root];

2. O(n) time, and O(n) space
1- build a n-ary tree based the parent array
2- traverse n-nary tree to compute height

void BuildTree()
{
Tree[n];

for(i=0;i<n;i++)
{
if(Parent[i]!=-1)
{
Tree[Parent[i]]->nextChild = &Tree[i]; //add i to its parent's child list
}
}

int Height(node)
{
if(!node->Child) //leaves
return 0;
int h=0;
while(!node->Child)
{
h=max(h,Height(node->Child));
node->Child = node->nextChild;
}

return h+1;
}

- Anonymous on July 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void create_hash(int parent[],int n)
{

	int i;
	for(i=0;i<n;i++)
	{
		if(parent[i]!=-1)
		hash[parent[i]]++;
	}
}
void Find_unique(int unique[],int child[],int n)
{

	for(int i=0;i<n;i++)
	{
		if(hash[child[i]] == 0) //abset from parent array
			{unique[pos] = child[i];
			pos++;}
	}

}
int Find_height(int unique[],int child[],int parent[],int n)
{
	int x = 0,i;
	int ht = 0;
	int maxht = 0;
	for(i=0;i<pos;i++)
	{	
		ht = 0;
		x = unique[i];
		while(parent[x]!=-1)
		{
			x = parent[x];
			ht++;
			
		}
		//check when stops
		if(ht > maxht)
			maxht = ht;
		
	
	
	}//end of for 

return maxht;

}

- Anonymous on July 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just using a recursion with memoization so that we do not check the paths again. This will be O(n) time and space. Here is the Java code bellow:

public int maxDistance(int[] arr) {
  int[] dp = new int[arr.length];
  int result = 0;
 
  for (int i = 0; i < arr.length; i++)
   result = Math.max(result, maxDistance(arr, dp, i));
 
  return result;
 }
 
 private int maxDistRec(int[] arr, int[] dp, int i) {
  int result = 0;
  
  if (dp[i] != 0 || arr[i] == -1)
   result = dp[i];
  else {
   result = maxDistRec(arr, dp, arr[i]) + 1;
   dp[i] = result;
  }
  
  return result;
 }

- GKalchev on July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

class Test{

static int[] A = {-1,0,1,6,6,0,0,2,7,5,9,10,11,12};

public static void main(String[] str){
Test test = new Test();
System.out.println(test.height(0));
}

public int height(int e){
int depth = 0;
int eFound=find(e);
if(eFound == -1){
return 0;
}
else{
ArrayList aList = new ArrayList();
for( int k=eFound; k <14; k++)
{
if( e == A[k] ){
depth=height(k)+1;
//System.out.println(depth+" "+e);
aList.add(depth);
}
}
int max=((Integer)aList.get(0)).intValue();
for ( int h = 1; h<aList.size();h++){
int temp = ((Integer)aList.get(h)).intValue();
if(max < temp)
max=temp;
}
return max;
}
}

public static int find(int e){
int flag = -1;
for(int i=0; i <14; i++ ){
if( A[i] == e ){
flag=i;
break;
}
}
return flag;
}
}

- Anonymous on October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{

}}

- add on October 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

in java:
public int findHeight(int [] parents){
	int len = parents.length;
	HashMap<Integer, Boolean> seen = new HashMap<Integer,Boolean>;
	int height = 0;
	for(int i=0;i<len;i++){
		seen.put(parents[i],false);
	}
	
	for(int i=0;i<len;i++){
		int p = parents[i];
		boolean seenParent = seen.get(p);
		if(!seenParent){
			height++;
			seen.put(p,true);
		}
	}
	return height;
}

- TheB on October 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void FindTreeHeight(int[] inputArray)
{

 int arrLen = inputArray.Length;
        int[] tempArr = new int[arrLen];
        for(int i=0;i<arrLen;i++)
        {
            int level =0;
            int j=i;
            while (inputArray[j] != -1)
            {
                j = inputArray[j];
                level++;
            }
            tempArr[i]=level;    

        }


        foreach(int ele in tempArr)
        {
            Console.WriteLine(ele);
        }

}

- Ron on February 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if no additional memory is allowed, this is my solution with a while loop instead of recursion.

static int maxDepth(int[] parents) {
	int maxDepth = 0, curDepth = 0, curNode;
	for (int i=0;i<parents.length;i++) {
		curNode = i;
		curDepth = 1;
		while (parents[curNode] != curNode) {
			curDepth += 1;
			curNode = parents[curNode];
		}
		maxDepth = Math.max(curDepth,maxDepth);
	}
	return maxDepth;
}

- josefsresearch on February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh sorry I am wrong here.

- DashDash on December 27, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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