## Twitter Interview Question for Software Engineer / Developers

• 0

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

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

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

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

can you explain how this relation came ?

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

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

binary trees, not search trees.

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.