## Twitter Interview Question for Software Engineer / Developers

• 0
of 0 votes

Country: United States
Interview Type: Phone Interview

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

The recurrence relation should be as follows
T(n) = T(i) * T(n -1 - i) where i ranges from 0 to n - 1

It should a product of T(i) and T(n -1 - i) and not addition

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

@vegeek: I think the Catalan number represents the total number of Full Binary Trees and this question asks for binary tress in general. Please correct me if I am wrong.

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

So smart! Just wrote it in another way:

``T(n) = T(0)*T(n-1) + T(1)*T(n-1-1) + T(2)*T(n-1-2) ... + T(n-1)*T(0)``

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

Catalans numbers?

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

those indicate that T(5) is 42, but I drew it out and it was 32 possible trees.

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

@nimbus
The number of possible trees that can be made with n number of keys are:
T(n)=(2n)!/(n)!*(n+1)!
So it is 42

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

T(n)=(2n)!/(n)!*(n+1)!
seems correct, how do u get it?

Thanks

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

t(n)= summation of t(i)+t(n-1-i) with i varying from 2 to n-1

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

can you explain how this relation came ?

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

shouldn't i should vary from 0 to n -1 ??

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

The recurrence relation of a binary tree is given by the expression:
T(n)=T(k)+T(n-k-1)+c.
Here k are the number of nodes of the left subtree and n-k-1 are the number of nodes of the right subtree. Also for a complete binary tree
T(n)=T(n-1)+T(n-1)+c. So it is T(n)=2T(n-1)+c. So as it can be seen that the recurrence relation is a function of linear n. So the time complexity of traversal of a tree is O(n). (That is a whole tree both left and right).

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

I think the solution should be:

T(0) = 0
T(1) = 1
T(2) = 2
T(3) = 2
T(n) = SUM( T(i)*T(n-1-i) ) where i ranges from 1 to n - 2

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

T(N)= N!

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

Given a pre-order traversal,

``1, 2, 3, 4, ... n``

, the first character is always the root. The remaining string can be broken at any place into a left subtree and a right subtree. This remaining string is (n-1) characters long. If you break it at the i-th position, then the left subtree has T(i) ways of being constructed, and the right subtree has T(n-1-i) ways of being constructed. Therefore,

``T(n) = Sum over i from i=0 to i=n-1 T(i)*T(n-1-i)``

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

2^(n-1)

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

Standard Dynamic Programming problem.

suppose you know the number of different way to construct BST with 0~N-1 nodes T(0),T(1)......T(N-1).

If we add one more node. we could have "i" nodes on left and "N-1-i" nodes on the right tree, since it is BST, the number "i" uniquely determines the sets of number on Left tree / root / right tree.
therefore the answer T(N) = sum_{all_i}{T(i) * T(N-1-i)}

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

T(k) = 2T(k-1) + Sum_{1<=i<=k-2} T(i)*T(k-1-i)

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

Binary trees or binary search trees?

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

binary trees, not search trees.

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