Another problem and solution for LeetCode challenge :
Given n, generate all structurally unique BSTs that store value 1 .. n
 The answer is said to be Catalan number = (2n)! / (n+1)! (n)!
How do we arrive at it ? Let's take a look:
Consider all possible Binary Search trees with each number as the root. For each of the n nodes as root, there are n-1 non-root nodes. We can partition these non-root nodes into the lower values than the root and the higher values than the root for the left and the right subtree. If we choose say i  in a sorted list as the root node, then there are i-1 nodes in the left subtree and n-i in the right subtree.
Thus if we denote the number of possible BSTs with the function t(n), then we can write it as the
sum of i = 1 to n of the product t(i-1) t(n-1). We multiply because the arrangement of the left subtree is independent of the right subtree and for each such arrangement of the two sub-trees, we get one BST with the root as i. Also note that regardless of the values of the elements in the sorted list, the number of unique BSTs depends on the number of elements n.
Therefore we write the code as follows:
int numUniqueBSTs(int n)
{
int count = 0;
if (n == 0) return 1;
for (int i = 1; i <= n i++)
  count += numUniqueBSTs(i-1) * numUniqueBSTs(n-i)
return count;
}
The iterative solution is also equally useful:
int numUniqueBSTs(int n)
{
int[] count = new int[n+1];
count[0] = 1;
for (I = 1; I <= n; I++)
   for (int j = 0; j < I; j++)
      count[I] += count[j] *count(I-j-1)
return count[n];
}

Okay one more coding exercise:
Given an array of positive integers with every element appearing twice except for one, find that one:
int OccursOnce(int[] num)
{
if (num == null || num.length <= 0) return -1;
int candidate = A[0];
for (int i = 1; i < num.length; i++)
{
  candidate = candidate ^ num[i];
}
return candidate.
}

My next few posts will be on managing hybrid clouds, PAAS and OpenStack.