Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
It's catalan numbers.
(2 * n ) ! / ( (n + 1) ! * (n) ! ) : Catalan number can be computed using Dynamic programming as it can overflow if you simply use factorial calculation. So here by I am posting one DP silution for it.
long[][] DP = new long[100][100];
long catalan(int N) {
for (int i = 0; i <= N; i++) {
DP[i][0] = 1;
for (int j = 1; j <= i; j++) {
DP[i][j] = DP[i][j - 1];
if (j < i) {
DP[i][j] += DP[i - 1][j];
} else
DP[i][j] += DP[i - 1][j - 1];
}
}
return N == 0 ? 1 : DP[N - 1][N - 1];
}
No. of unique BST made using integers from 1 to n is equal to the n th term in the Catalan Series.
public class CatalanNumbers
{
public static int Catalan(int n)
{
// if(n==0 || n==1) return 1;
int result = 1;
for(int i=2;i<=n;i++)
{
result = result*(n+i)/i;
}
return result;
}
}
The Answer is Catalan Number 2n!/(n! (n+1)!)
Hence T(1) = 1
T(2) = 2
T(3) = 5 and so on
Edit :
Catalan numbers follow a linear recursion
C(n+1) = ((4n+2)*C(n))/(n+2)
you dont need O(n^2) dynamic programming
Let T(k) be number of trees formed of k nodes
so trivial case is
T(1) = 1
T(2)=2
T(3)=3
T(4)= T(3) + T(1).T(2) + T(2).T(1)+ T(3).
let 1,2,3,4 be the elements of the array.
You would have a set of trees with:-
1 as the root ==> T(3)
2 as the root ==>T(1). T(2) [ 1 on the left side and 3,4 on right side]
3 as the root ==> T(2). T(1) [ 1, 2 on the left tree and 4 on right tree]
4 as the root ==> T(3) [1,2,3 on left tree and Null on right]
import java.util.HashMap;
public class uniqueBSTs {
static HashMap<Integer, Integer> known = new HashMap<Integer,Integer>();
public static int getBSTCount(int n){
int total=0;
if (n>1)
{
for(int i=1;i<=n;i++){
int left=1,right=1;
if (known.containsKey(i-1))
left = known.get(i-1);
else
left =getBSTCount(i-1);
if (known.containsKey(n-i))
right = known.get(n-i);
else
right =getBSTCount(n-i);
total+=(left*right);
}
}
else{
total=1;
}
known.put(n, total);
return total;
}
public static void main(String[] args) {
System.out.println(getBSTCount(2));
System.out.println(getBSTCount(3));
System.out.println(getBSTCount(4));
System.out.println(getBSTCount(5));
System.out.println(getBSTCount(7));
System.out.println(getBSTCount(10));
}
}
get all permutations and construct tree from them.
eg 1,2,3 ---> we get 123 , 132 , 213, 231 , 312 , 321
/**
*
*/
package personal.abhijit.trial.general;
import java.util.ArrayList;
import java.util.List;
/**
* @author Abhijit
*/
public class Permutation {
/**
* @param args
*/
public static void main(String[] args) {
Permutation p = new Permutation();
int[] a = {
1, 2, 3, 4
};
System.out.println(p.permuation(a));
}
public List<List<Integer>> permuation(int[] a) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (a.length == 1) {
List<Integer> innerList = new ArrayList<Integer>();
innerList.add(a[0]);
list.add(innerList);
return list;
}
for (int i = 0; i < a.length; i++) {
int[] array = new int[a.length - 1];
int k = 0;
for (int j = 0; j < a.length; j++) {
if (a[i] == a[j]) {
continue;
}
array[k++] = a[j];
}
List<List<Integer>> shortList = permuation(array);
boolean flag = false;
for (int l = 0; l < shortList.size(); l++) {
List<Integer> innerList = new ArrayList<Integer>();
innerList.add(a[i]);
List<Integer> sl = shortList.get(l);
innerList.addAll(sl);
if (innerList.size() == 3) {
int start = innerList.get(0);
int middle = innerList.get(1);
int end = innerList.get(2);
if ((start < middle && start > end) || (start > middle && start < end)) {
if (flag == false) {
list.add(innerList);
flag = true;
}
continue;
}
}
list.add(innerList);
}
}
return list;
}
}
T(i) is the # of permutation of BST for {1, 2, ... i}.
Now consider {1, 2, ..., n}, if you pick element x (1<= x <= n) as your BST's root node, then the BST permutation when x is root node is the permutation of left and right subtree together:
T(x-1) + T((x+1) ~ n).
Looking the right subtree, since all element is greater than x in the right subtree (BST definition), let's substract x from all elements, then T((x+1) ~n) become T(1~(n-x)) = T(n-x). Hence picking x as root node has the permutation of
T(x-1) + T(n-x).
The algorithm can hence be described recursively as
int T(int x)
{
if (x = 0) return 0;
if (x = 1) return 1;
int result = 0;
for (i =1; i <= x; i++)
{
result += T(i - 1) + T(x - i);
}
return result;
You can further optimize it by doing dynamic programming and storing all intermediate T(x) into a table
Catalan number is math fanciness (and that's great) but to me it confuses the issue and adds jargan. The following site gives a more lucid explanation:
Essentially, if you n distinct nodes (I'm thinking this gets messed up if some of the nodes are not distinct, because we don't have the full range of possible trees to use, someone please correct this). Parenthetical aside, the theory is that we only care about calculating the possible geometries and can fill in the tree properly using the values later.
you pick a root somewhere between 1 and n, say i. With root i, on the one side we have a sub tree from i-1 (i nodes - root) and then on the other, n-i (n nodes - (left hand side+root)). Multiplying these together should return the total number of ways this root, the left sub tree and the right sub tree can be combined. This recurrence, therefore seems enough to get to the correct answer, but it's extremely slow.
That's where DP comes in. We create a lookup table to store/and lookup pre-calculated values. As the article points out, this is quadratic because for each root, n calculations need to be made.
- Vir Pratap Uttam May 05, 2015private static int catalanNumber(int n) { if (n == 0) return 1; int count = 0; for (int i = 1; i <= n; i++) { count += catalanNumber(i - 1) * catalanNumber(n - i); } return count; }