## Samsung Interview Question

Software Engineer / Developers**Country:**India

You may understand the solution to this problem by watching this video

youtube.com/watch?v=UfA_v0VmiDg

The outlined algorithm is just a little bit incomplete. The code shown will work terribly for anything but the smallest inputs since there's no memorization involved. This needs to be solved using dynamic programming.

@eugene: Needs to be solved is a bit strong.

If you can derive a formula like C(2n,n)/(n+1), you don't need dynamic programming..

I didn't mean for my comment to be about all possible solutions. I was only talking about the specific recursive approach discussed in the video. To use that approach, you will need to make a fix to solve the problem of exponential runtime by memorizing values, which would then amount to dynamic programming.

the ans is simple........if n numbers are given then.......and will be

(2nCn)/(n+1)............hope it will help you...

.

above C is for combination

Recursive Solution:

int countNoOfPossibleTrees(int n)

{

if(n==0 || n==1)

return 1;

else

{

int sum = 0,left = 0,right=0,i;

for(i=1;i<=n;i++)

{

left = countNoOfPossibleTrees(k-1);

right = countNoOfPossibleTrees(n - k);

sum +=left * right;

}

return sum;

}

}

DP or recursive solutions (code of each are bellow in the comments). Base state is 1 element has 1 possibility and then for every next element sum possibilities with each root.

Example i.e. lets take [1,2,3]. We have dp[0,1,2,5] (dp[i] = j where i is the number of nodes and j are the combinations count) because 123 can have:

1.) root 1 and 23. So possibilites are dp[3] += Math.max(dp[left.len], dp[right.len]) = Math.max(dp[0], dp[2]) = 2

2.) root 2 and 13. So possibilites are dp[3] += Math.max(dp[left.len], dp[right.len]) = Math.max(dp[1], dp[1]) = 1 ⇒ dp = 2 + 1 = 3

3.) root 2 and 13. So possibilites are dp[3] += Math.max(dp[left.len], dp[right.len]) = Math.max(dp[0], dp[2]) = 2 ⇒ dp = 3 + 2 = 5

DP solution

```
public int uniqueTreesRec(int N) {
int[] dp = new int[N + 1];
dp[1] = 1;
for (int i = 2; i <= N; i++) {
int ithSum = 0;
for (int j = i - 1; j >= (i >> 1); j--)
ithSum += dp[j] << 1;
//example for 12345 we will have 14+5+2+5+14 = 2*14 + 2*5 + 1*2
if (i & 1 == 0)
dp[i] = ithSum - dp[i>>1];
else
dp[i] = ithSum;
}
return dp[N];
}
```

Recursion with memoization

```
//call with uniqueTreesRec(0, arr.length -1, dp)
private int uniqueTreesRec(int N, int startIdx, int endIdx, int[] dp) {
int possibilities = 0;
if (startIdx == endIdx && startIdx >= 0 && &&endIdx < N)
possibilities = 1;
else if (startIdx >= 0 && endIdx < N) {
if (dp[endIdx - startIdx] > 0)
return dp[endIdx - startIdx];
for (int idx = startIdx; idx <= endIdx; idx++) {
int leftNodesCnt = idx - startIdx;
int rightNodesCnt = endIdx - idx;
int leftPoss = dp[leftNodesCnt];
int rightPoss = dp[rightNodesCnt];
if (leftPoss == 0)
leftPoss = uniqueTreesRec(N, startIdx, idx - 1, dp);
if (rightPoss == 0)
rightPoss = uniqueTreesRec(N, idx + 1, endIdx, dp);
possibilities += Mat.max(leftPoss, rightPoss);
}
dp[endIdx - startIdx] = possibilities;
}
return possibilities;
}
```

I've solved this question before. I have an explanation of it there. See:

careercup DOT com/question?id=12217041

The problem I linked to sounds different, but it's not. The problem here is "How many BSTs can I make with the specified set of numbers?", which is the same as asking "How many BSTs can I make whose in-order traversal is a1, a2, a3, ..., a_n?" These are the same because any other in-order traversal does not form a BST. This is in turn the same as asking "How many binary trees can I make with the in-order traversal a1, a2, ... , a_n?" because every binary tree having this in-order traversal is a BST.

A search revealed that this question has actually been asked quite a few times:

question?id=183797

question?id=13872751

question?id=9184959

question?id=11300064

I am passing n as the parameter which is the number of numbers forming the tree. It does not matter because the numbers are unique and we do not care about the order.

```
static int count =0;
public static int maxBST(int n)
{
if(n==0)
return 1;
if(n<3)
return n;
if(n==3)
return 5;
for(int i=0;i<n;i++)
{
count+= maxBST(i)*maxBST(n-i-1);
}
return count;
}
```

let count(n)= number of BST possible using n distinct keys

- coolsolution September 13, 2012Then

count(n) = sum[ k=1to n ] ( count(k-1) * count(n-k) )