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