## Amazon Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
13
of 13 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;
}``````

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

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

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

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.

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

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

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.

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

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

Can you put in simple words what leveling here means?

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

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.

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

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

Comment hidden because of low score. Click to expand.
3
of 3 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.

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

thanks grt algo

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

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

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.

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

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

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

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.

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

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

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

printf("%d ",findheight(par,size));
return 0;
}``````

ideone.com/vCLF4

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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.

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

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

}

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

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

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

{{

}}

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

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

}``````

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

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

Calculate the depth from node to root.

``````int FindHeight(int[] parent, int len) {
int height [len];
for(int i=0;i<len;i++)
height[len]=1;
for(int i=len-1;i>=0;i--)
{
int idx = parent[i];
if (idx >=0)
height[idx]=max(height[idx], height[i] + 1);
}
return height;``````

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

Oh sorry I am wrong here.

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.