## Amazon Interview Question for Software Engineer Interns

Country: United States
Interview Type: Phone Interview

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

What does "Identical trees" mean?

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

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

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

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

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

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

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

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

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

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.

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

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

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

My mistake, I drew a wrong tree

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

No problem, I was just still trying to make all of the test cases work but can't seem to get them all to work.

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

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.

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

What counts as an identical binary tree? Can you give an example of two identical binary trees for eg. the first array?

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

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

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

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;
}
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);
}
HashSet<Node> nodes = new HashSet<Node>();
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;
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));
}
}``````

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

Please could you give some examples.

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

THIS IS NOT AN INTERVIEW QUESTION. THIS IS AN ONGOING PROGRAMMING CONTEST. PLEASE DONT ANSWER.

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

THIS IS NOT AN INTERVIEW QUESTION. THIS IS AN ONGOING PROGRAMMING CONTEST. PLEASE DONT ANSWER.

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.