## Amazon Interview Question for Software Engineer / Developers

• 0

Team: SDE
Country: India
Interview Type: In-Person

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

How if you have the following in-order sequence:
4 8 10 6 20 5 9 7 3
Yes, we could get the root from the middle of above sequence but the next the recursion is little bit shaky - on the second recursion we have two set of sequences, on the left is 4 8 10 6 and on the right is 5 9 7 3. We know we should choose 10 from the left sequence and 9 on the right sequence but 10 is 3rd element of the left sequence while 9 is the 2nd element of the right sequence.

Therefore, to fix that issue on the next recursion, instead of looking at the middle, we should look up for the biggest number on the sequence. Then it will work nicely.

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

I think this is a classic question
Yes.. it is possible to build a heap tree only from its inorder..
Cosider the following case..

``````20
/        \
10       9
/   \       /  \
8   6    3   2
/
4

Its inorder is        4 8 10 6 20 3 9 2

root will be the middle element. i.e. 20

recurse the same function on left tree(4,8,10,6)  and right tree(3,9,2)

tree is constructed..``````

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

This is in fact a BST. Building just a heap (what the question asked) is even easier.

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

the solution is little vague If in the above example 8 has a right child then the root will be shifted one place rightwards. so how we are deciding the the root is not clear

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

The root is obviously the maximum element.

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

Root certainly can't be simply the middle element. In the example given, just add two more elements i.e. right child for 8 & left child for 6. you'll see your very first step will start to break.

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

refer careercup.com/question?id=9735293

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

int find_max(int a[],int low,int high)
{ int max=0,index;
for(int i=low;i<=high;i++)
{
if(a[i]>max)
{
max=a[i];
index=i;
}
}
return index;
}
void addnode(int a[],int low,int high,node **root,node **ptr)
{
int k;
if(low>high)
return ;
else
{
node *temp= new node;
k=find_max(a,low,high);
temp->data=a[k];
temp->left=NULL;
temp->right=NULL;
if ( *root == NULL)
*root = temp;
*ptr=temp;
}
}

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.