## Interview Question for Consultants

• 0

Interview Type: In-Person

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

this is taking from here: cslibrary.stanford.edu/110/BinaryTrees.html

``````/**
For the key values 1...numKeys, how many structurally unique
binary search trees are possible that store those keys?
Strategy: consider that each value could be the root.
Recursively find the size of the left and right subtrees.
*/
public static int countTrees(int numKeys) {
if (numKeys <=1) {
return(1);
}
else {
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...
int sum = 0;
int left, right, root;

for (root=1; root<=numKeys; root++) {
left = countTrees(root-1);
right = countTrees(numKeys - root);

// number of possible trees with this root == left*right
sum += left*right;
}

return(sum);
}
}``````

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

Its a very tricky question as it needs to be solved using a catalan sequence.

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

The Catalan sequence will give you the number of ways of arranging a binary tree, but binary search tree becomes more difficult because ordering matters there.

I'm not sure of any other way of doing this other than brute force...

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

Could you please explain the qn a bit ? Is this the count on the nodes of a BST ?

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

We are given N Nodes ,each having unique values in[1,N] how many different Binary search tree are possible using all of them.

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

this solution works fine with a smaller input.
Try with N=100 . It starts crying. I tried with dynamic program as well but I am unable to get the correct output for N=100 .
Output expected is :25666077

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

Dynamic programming in Python. Results are in accordance with the Catalan number function.

``````import sys

N = int(sys.argv[1])

m = [N * [0] for i in range(N)]

for i in range(N):
m[i][i] = 1

for s in range(2, N+1):
for i in range(N-s+1):
m[i][i+s-1] = 0

for j in range(i, i+s):
c = 1
if i <= (j-1):
c *= m[i][j-1]
if (j+1) <= (i+s-1):
c *= m[j+1][i+s-1]

m[i][i+s-1] += c

print m[0][N-1]``````

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

I have resolved it here: oj.leetcode.com/problems/unique-binary-search-trees/

``````class Solution:
# @return an integer
def numTrees(self, n):
# c[i] is the count of different bts using 1...i
c = [0] * (n + 1)
c[1] = 1

for i in range(1, n + 1):
# the tree's root is j, left child may be 1...j-1, right child may be j+1...i
for j in range(1, i + 1):
if c[j - 1] * c[i - j] > 0:
# the count of bts using j+1...i is equal to using 1...i-j
c[i] += c[j - 1] * c[i - j]
elif c[j - 1] == 0:
c[i] += c[i - j]
elif c[i - j] == 0:
c[i] += c[j - 1]

return c[n]``````

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

Reason: To create a tree BST, first we will choose a root number which can be chosen in n ways. After we have chosen root number, we can add next number by selecting one of any remaining (n-1) numbers. For any selected second number we have only one possible location where it can be added (to maintain the BST property). So the total number of the possible trees with two numbers selected from n unique numbers will be simply n*(n-1). If we extend the same idea further, third number to be added can be chosen in (n-2) ways and once it is selected, its position in the already made tree of 2 nodes will be unique. So we get only n*(n-1)*(n-2) ways to make a BST with 3 numbers selected from n numbers. We can go on like this. The final answer will be simple n*(n-1)*(n-2)*...3*2*1, which is n!.
For coding n!, there are many ways which will fail as soon as n value of n! becomes big enough to cross upper limit of the integer in a programming language.
So if we want to make it work for arbitrary big number, we will have to use either BigInterger of java or right our own string based multiplication algorithm.

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

Sorry.. many typos in the answer but I hope that my idea was clear.

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

Finally I have the solution.
The solution is using Memoization.
Thanks for all the help guys

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.