## Samsung Interview Question for Software Engineer / Developers

Country: India

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

let count(n)= number of BST possible using n distinct keys
Then
count(n) = sum[ k=1to n ] ( count(k-1) * count(n-k) )

Comment hidden because of low score. Click to expand.
3
of 5 vote

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

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

very well explained in the link

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

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.

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

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

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

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.

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

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

.
above C is for combination

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

Yes, and they are called Catalan numbers.

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

ur solution is for no of binary trees .its askin for bst.

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

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

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

what is k here?

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

Catalan numbers.

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

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

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

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];
}``````

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

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

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

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

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

its catalan number .. for given key n , the number of different binary search trees that could be found will be equal to ((2n)!/(n!*(n+1)!))..

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

a

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

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;

}``````

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.

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

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