CareerCup

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

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

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.

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

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

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.