## Amazon Interview Question for SDE-2s

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

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

C(n)=2n!/n!(n+1)!

Comment hidden because of low score. Click to expand.
4
of 8 vote

C(n) = (2n)!/n!*(n+1)!, Catalan Number

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

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

It is catalan number where if n keys are given to us we can generate distinct number of trees from those n keys by the below formula:

No.of.trees= (2n)! / (n!*(n+1)!)
It comes from the fact that if n are the number of keys that for every node we can have 2 children for binary tree then those can be made or mathematically arranged in (2n)!. But for n keys we will have n+1 external nodes. So the internal nodes and external nodes can be arranged seperately in n! and (n+1) !. Note here external nodes cannot be arranged with internal nodes only with external nodes so (n+1)! similarly internal nodes among themselves in n! so for both these arrangements multiply them and divide it by the number of child arrangement to get the required distribution and thus number of different trees that can be generated.

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

``````int DistingusishedTree(int n) {
if(n<1)
return 1;
int sum=0;
for(int i=1;i<=n;i++){
sum+=DistingusishedTree(i-1)*DistingusishedTree(n-i);
}
return sum;

}``````

This is the program to find the different BSTs.
The reason is simple:
suppose n=3;
so we will make each number as root and calculate the different subtrees possible.
for i=1;
left subtree will not contain any node and right subtree will contain 2 nodes i.e 2 & 3
there are two combination possible.
if i=2
left subtree will contain 1 node(1) and right subtree will contain 1 node(3)
if i=3
left subtree will contain 2 nodes(1,2).there are two combinations possible for it.

so required number will be
num(i)= sumation(num(i-1)+num(n-i)) where i=1,2...n
The compact formula for this is num(n)=C(2n,n)-C(2n,2n+1) and known as catalan number
N.B.: This problem can be solved using DP instead of recusion.

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

Question continued, trying out some formatting as a comment.

``````For ex: n = 1 => one tree
n = 2 => two trees
O        O
/           \
O            O
n = 3 =>  five trees
O       O               O               O              O
/         \               \             /             /  \
O            O              O           O               O  O
/             \           /               \
O                 O         O               O``````

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

This question is already asked in CareerCup. For more details refer to question with id= 183797

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

catalan number.. (2n)!/(n!)(n+1)!

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

Hi D,tox'mi, what 0OZz has said is right, the number trees has to be calculated with Catalan number and also it has to be solved by Dynamic programming so its a combination of Catalan number calculation and dynamic programming, please correct me if i am wrong, Me too also looking for this solution, i think it is not binary tree, rather, from a given set of numbers the BSTs need to be constructed.

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

The number actually can be given using a recurrence relation:

T(n) = 2T(n-1) + 2* Summation [(T(j) * T(n-1-j] Where j runs from 1 to (n-1)/2

You are right, the values of T(n) can be computed bottom up using DP.

Comment hidden because of low score. Click to expand.

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.