Amazon Sabre Holdings Interview Question for Software Engineer / Developers






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

well, yes, its a Catalan's number for BTree if we strictly differ left and right children.
Wonder, whats the number of topologically unique BTrees (where rotation of L/R nodes is allowed)?
Ankit, Amazon probably expected from you this kind of analysis: link to comeoncodeon.wordpress.com/2010/04/13/number-of-binary-trees/

- celicom May 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A catalan number gives the structurally different binary trees not binary trees which differ in values.

- Anonymous May 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. total number = !n * Catalan Number
11. Unique trees no= Catalan number

- chandan.here4u May 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For ex: take 3 nodes. (2n)!(n+1)! = 30 binary trees can be formed.
Let see how:
nodes are A, B and C.

First A as root node,
B can be Left/Right child and similarly C can be Left/Right child so, total 4.
A->B->C , A->C->B can be Left/Right so, total 4.

and finally A left B and right C, A left C and right B. so total 2.

Total trees with A as root node is 10.

similarly for B and C . 10 + 10 + 10.

- Syam April 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think it should be (1/n+1)*2nCn. all will be structrally unique.

- CXC May 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since binary tree is to made if the number of elements in the array is n then the total number of BT that can be constructed would be np2 -> n(n-1) Since the ordering will matter (Parent-Child) I dn't think there would be duplicacies unless the array has duplicate data.

- jeangrey May 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is not very clear to me. can you explain a little further.
can we pick up any number element from array to make a binary tree? or we should use all the element from array to make a binary tree? if we should use all the element, does sequence matter in original array?

- Anonymous May 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming values in array are unique

Let there are n elements in array

one can select a root node in n different ways from this list
when root has been selected then array have n-1 elements left
one can select next element in n-1 different ways and for this node we have 2 possible positions
so no of ways for placing second node will be 2 (n-n1)

asuming we have
root
/ \
second
selected
node
/\

clearly third node can be selected in n-2 different ways and 3 possible positions for this node
means 3(n-3) ways for third node


following up in above manner
using all the n nodes from array one can make a binary tree in

n + 2(n-1) + 3(n-2) + 4(n-3)+......+n*1 ways


Please help what will be sum of this series
Also suggest for improvement if possible

- Dheeraj May 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome solution man... :)

- Naveen May 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

little correction to your solution. It should be

n * 2(n-1) * 3(n-2) * 4(n-3)*......* n*1 ways

which comes to (n!)^2

- Naveen May 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No.. it is wrong.. work out yourself before posting answers and saying "awesome solution"
With 3 nodes you can get 30 unique Binary trees..
from your formula it is 3!^2 = 36 which is wrong..

- swathi May 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can u plz explain how the answer for 3 nodes is 30?
Shouldn't it be 12?

- Anonymous May 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lets say n=3

no. of binary trees without considering the order of elements will be 2nCn / n+1 (this gives only the different possible orientations of the nodes)

now we can use the array to permutate each element in each orientation this gives:

(2nCn / n+1 ) * n! = 30.

I think if the elements of the array are unique .... all 30 binary trees will also be unique.....

- lesnar56 May 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

in case n = 3, there are only 5 structures instead of 6, since there is one duplicate.
the solution could work upon proper change.

- pansophism May 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@swathi
Why are you looking for structurally different binary trees when question asks for just different binary trees.

- Anonymous May 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For the number of unique binary tree, we can recursively solve the problem.
Obviously, S[1] = 1, and S[2] = 2, let S[0] = 1,
For an array with N unique elements, we first choose one element as root. There are n elements which we can choose from. Then we divide the unchosen n-1 elements into two groups. each group may contains (0, n-1) elements, or (1, n-2) elements ... or ( (n-1)/2, n -1 - (n-1)/2) elements. The unique binary trees composed by elements in each group can either be the left or right subtree, not important if we want to count the overall unique binary trees.

So the total number of unique trees are:

S[n] = n ( S[0]*S[n-1]*C(0,n-1) + S[1]*S[n-2]*C(1,n-1) + S[2]*S[n-3]*C(2,n-1) + ... + S[(n-1)/2]*S[n - 1 - (n-1)/2])
where C(i, n-1) is the combination operation (n-1)!/[i!*(n-1-i)!]

- Aaron May 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(2^n - n)*n! is the answer

- pansophism May 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For n = 4 ,your answer comes out to be 12*4!
but it should be 14*4!
The correct answer is ((2n)!/(n!(n+1)!))*n!

- VIP May 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For a given number of n nodes, there will be 2^n-n unique binary trees possible.

- SS May 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is Cn*n!

Cn(Catalan number) = 2n!/((n+1)! n!)

n-Cn*n!

- Anonymous August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sry i dnt know byeee

- shiva July 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sry idnt know poda daiiiii

- shivachandra babu techrel July 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

someone accessed it wrongly

- shiva July 16, 2011 | Flag


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