Interview Question
ConsultantsInterview Type: In-Person
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]
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]
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.
this is taking from here: cslibrary.stanford.edu/110/BinaryTrees.html
- Anonymous January 26, 2015