Amazon Interview Question for Software Engineer / Developers


Country: India




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

If both Inorder and Postorder sequence are provided, then one possible implementation:

int j= inorder.Count -1;

TreeNode ConstructNodes(List<Node> inorder, List<Node> postOrder)
{      
	int index = -1;
	TreeNode n = new TreeNode();
	n.Data = postOrder[j].Data;

	//gets the index of the "postOrder[j].data" element in the inorder list.
	index = getIndex(inorder, postOrder[j].Data);
	inorder[index].Processed = true;

	if ((index < inorder.Count -1) && (!inorder[index + 1].Processed))
	{                
		j--;
		n.Right = ConstructNodes(inorder, postOrder);
	}
	else
		n.Right = null;

	if ((index > 0) && (!inorder[index -1].Processed))
	{                
		j--;
		n.Left = ConstructNodes(inorder, postOrder);
	}
	else
		n.Left = null;   
		
	return n;
}

- Ran January 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Did the interviewer or the question assume that all the data elements in post and inorder traversals are unique ?

- viv February 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We will also need inorder traversal of the tree to completely produce the tree.

- cooldaa January 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wont you also need whether each node is a leaf or non-leaf?

- V January 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

no need. Just postorder and inorder sequence is enough to build back the tree

- Anonymous January 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i=n-1;//global
struct node *construct(int post[],int in[],int n)
{
 return const_post_in(post,in,0,n-1);
}
struct node * const_post_in(int post[],int in[],int s,int e)
{
 int j;
 if(s>e)
  return NULL;
 struct node *p=getnode();//allocate mem for node
 p->info=post[i--];
 for(j=s;in[j]!=post[i-1];j++)
  ;
 p->r=const_post_in(post,in,j+1,e);
 p->l=const_post_in(post,in,s,j-1);
 return p;
}

- Cairn January 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Def buildTree(inorder[], postorder[])
{
j = len(postorder);
pre = postorder[j-1]; /* scan starting from the end of post order list */
for(i = j-2; i>=0; i--)
{
current = postorder[i];
curr_idx_in = find_position(current, inorder);
parent_idx_in = find_position(pre, inorder);
if (current_idx_in > parent_idx_in)
/* right child */
pre->right = current;
else if (current_idx_in < parent_idx_in)
pre->left = current;
pre = current;
}
}

- Anonymous January 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

FI(k, lo, hi)
	for each i from lo to hi
		if(in[i] == k)
			break
	return i
	
CT(lo, hi, mn, mx)
	n = CN(p[mn])
	p = FI(p[lo], lo, hi)
	d1 = p - lo
	d2 = hi- p
	n->l = CT(lo, p-1, mn+1, mn +1+d1-1)
	n->r = CT(p+1, hi, mn+d1+1, mx)
	return n

- Prateek Caire February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution by Tushar Roy on geeksforgeeks:

Okie i got this approach..

suppose the example

inorder = A B C D E F G H I
postorder = A C E D B H I G F

This can b done recursively following way

you start reading postorder array from backwards. So take F , split inorder array into two subarray.
A B C D E and G H I

take G (before F in postorder) split GHI into null and H I, take I(before G in postorder) split into H I into H and null and so on.

following is the code which worked fine. Check it out.

typedef struct tree
{
int key;
struct tree * left;
struct tree * right;
}Tree;

Tree * createTreeFromPostorderInorder(int postorder[],
int inorder[],int left,int right, int pos)
{
if(left > right)
{
return NULL;
}
Tree *t = (Tree*)malloc(sizeof(Tree));
t->key = postorder[pos];
int index = search(inorder,left, right, t->key);
t->right = createTreeFromPostorderInorder(postorder,inorder,
index +1, right, pos -1);
t->left = createTreeFromPostorderInorder(postorder,inorder ,
left,index-1, pos - 1 - (right - index));
return t;
}

int search(int arr[],int left, int right,int key)
{
for(int i=left; i <= right; i++)
{
if( key == arr[i])
{
return i;
}
}
return -1;
}
int postorder[] = {'A', 'C' , 'E', 'D', 'B', 'H', 'I', 'G', 'F'};
int inorder[] = {'A', 'B','C','D','E','F','G','H','I'};
Tree *newTree = createTreeFromPostorderInorder(postorder,inorder,0,8,8);

- viv February 26, 2012 | Flag Reply


Add a Comment
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.

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