Amazon Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
public static int countTrees(int numKeys) {
if (numKeys <=1) {
return(1);
}
else {
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root...
int sum = 0;
int left, right, root;
for (root=1; root<=numKeys; root++) {
left = countTrees(root-1);
right = countTrees(numKeys - root);
// number of possible trees with this root == left*right
sum += left*right;
}
return(sum);
}
}
I don't think that is the right answer? The question wasn't to count the number of different binary trees. It was to find the number of combinations that would result in the exact same binary tree as the input list (root as 0 index and so on, left to right order).
If the question is to find the number of combinations that would result in the exact same binary tree as the input list, I doubt the correctness of the first test case.
To calculate the result, we need to know how many permutations exist with constrain root always occur before its children(the order of occurrence of siblings does not matter), we can use some math trick to do that. However, I'll just display all possibilities here.
Let's look at the left subtree: 8, 6, 9, 4, 5, we have 8 permutations to generate this subtree:
8, 6, 4, 5, 9
8, 6, 4, 9, 5
8, 6, 5, 4, 9
8, 6, 5, 9, 4
8, 6, 9, 4, 5
8, 6, 9, 5, 4
8, 9, 6, 4, 5
8, 9, 6, 5, 4
Since the first position is fixed to 10, insert 15 to any position of any permutation shown above, then we'll get 8 * 6 = 48 permutations which form the same binary tree as the input list, rather than 24
@yangxh92
I think you are correct in your description, "we need to know how many permutations exist with constrain root always occur before its children(the order of occurrence of siblings does not matter), we can use some math trick to do that."
I just don't know what this 'math trick' is that you are talking about. You have explained it better than I could though, I will keep searching.
Thanks for your reply.
Assume that now you know there are M sub-combinations will form left subtree, and N sub-combinations will form right subtree. Now all you need to know is how many combinations can they form?
Let's assume the size of left subtree is P, the size of right subtree is Q, and P <= Q, then the answer is C(P, Q + 1) * N * M. That is, in the new combination, first you fix Q positions for the right subtree, then you need to insert a combination with P elements into the new combination. Now there are Q + 1 possible place to insert, you need to choose P out of Q + 1 positions, that is C(P, Q + 1). After the positions are fixed, multiply the result by the number of possible permutations.
@yangxh92
The first test case that you doubt the correctness of, I think it is the right number of combinations at 24. You're permutations include four that have the 5 before the 4. But isn't the 5 under the 4? The math is throwing off the other answers. How are you generating/estimating the permutations that stay in the correct order?
Let list[i:j] be the sub-list containing: list[i], list[i + 1], ..., list[j].
If the kth element in the list is the root, then there could be count(list[i:k - 1]) * count(list[k + 1:j]) unique binary search trees which have element k as their roots. Increase k from 1 to n and count the number recursively, you'll get the answer.
1) [10, 15, 8, 9, 6, 4, 5]
2) [12, 19, 15, 6, 5]
Rearranges the numbers in the list so that the root always stays in the same spot and subsequent nodes always come before their child or children. So in the first example, 10 is the root, 15 can go anywhere after 10. Then 8 must come before 6 and 9 (could be 9 then 6), 6 must come after 8, then 4 after 6, 5 after 4.
Second example, 12 is root. 6 and 19 (or 19 then 6) must come after 12, 5 must come after 6, 15 must come after 19.
This seems like a rather long problem, unless I miss a simpler way to do this. Basically I first construct a tree from the array. Then I compute the answer recursively by passing a set of nodes I can traverse from in the recursive call.
class CountIdenticalTrees {
static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
public void add(int value) {
Node n = this;
while(true) {
if(n.value > value) {
if(n.left == null) {
n.left = new Node(value);
break;
} else {
n = n.left;
}
} else {
if(n.right == null) {
n.right = new Node(value);
break;
} else {
n = n.right;
}
}
}
}
}
static public int count(int[] arr) {
Node root = null;
for(int i : arr) {
if(root == null)
root = new Node(i);
else root.add(i);
}
HashSet<Node> nodes = new HashSet<Node>();
nodes.add(root);
return countIdentical(nodes, arr.length);
}
static public int countIdentical(HashSet<Node> nodes, int num) {
if(nodes.size() == num)
return 1;
int result = 0;
HashSet<Node> clone = (HashSet<Node>)nodes.clone();
for(Node n : clone) {
for(int i=0; i<2; i++) {
Node child = (i == 0 ? n.left : n.right);
if(child == null || nodes.contains(child))
continue;
nodes.add(child);
result += countIdentical(nodes, num);
nodes.remove(child);
}
}
return result;
}
public static void main(String[] args) {
int[] arr = new int[args.length];
for(int i=0; i<args.length; i++)
arr[i] = Integer.parseInt(args[i]);
System.out.println(count(arr));
}
}
What does "Identical trees" mean?
- MIG January 08, 2015