Interview Question for Consultants


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); 
  } 
}

- Anonymous January 26, 2015 | Flag Reply
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.

- Mat Parker January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- Skor January 26, 2015 | Flag
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 ?

- BT January 26, 2015 | Flag Reply
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.

- Mat Parker January 26, 2015 | Flag Reply
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

- Anonymous January 26, 2015 | Flag Reply
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]

- Victor January 26, 2015 | Flag Reply
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]

- yanshidong10123815 January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Shouldn't the answer be n!?
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.

- Anonymous January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 29, 2015 | Flag
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

- Mat Parker February 05, 2015 | Flag Reply


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