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

- Vir Pratap Uttam May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 8 vote

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

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

can you please explain your answer? it seems to be correct

- chintan July 16, 2013 | Flag
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.

- vgeek July 16, 2013 | Flag Reply
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.

- sayannayak July 16, 2013 | Flag Reply
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

- Murali Mohan July 16, 2013 | Flag Reply
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

- codeAddict July 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous July 18, 2013 | Flag Reply
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.

- S@iR@m July 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Murali Mohan July 16, 2013 | Flag
Comment hidden because of low score. Click to expand.


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