Amazon Interview Question
Country: United States
Solution in python
def check_sums_pyramid(p, s):
x, paths = 1, [(0, p[0][0])]
for row in p[1:]:
i_paths = []
for position, value in paths:
v1 = row[position] + value
if v1 <= s:
i_paths.append((position, v1))
v2 = row[position + 1] + value
if v2 <= s:
i_paths.append((position + 1, v2))
paths = i_paths
return s in map(lambda x: x[1], paths)
Some comments to the code. Given a pyramid there are 2 ^ (number_of_rows - 1) possible paths. To represent the pyramid I am assuming the input will be a list of lists (each list should be one element larger than the previous list). To represent a path I am using a tuple of two elements, one being the last position from which we computed the path and the other the accumulated sum.
Edit: Forgot to mention that to handle negative numbers the code used to prune some paths that are over the sum should be removed.
Cheers.
Here's a java solution using a little bit of dynamic programming by computing a set of all the possible sums that I can find if I start in the current node and continue through any of its children. For this we add a BST in each node that will keep those values, so in the end the result will be true if 100 is in the root node's BST.
This solution assumes that a branch will be composed of a path between the root node and a leaf and doesn't need the tree to be a pyramid to find the result, that is to say that it doesn't expect every node to have the same height with it's siblings and cousins.
public static class SumNode<T> {
public T val;
public SumNode<T> left;
public SumNode<T> right;
public TreeSet<Integer> possibleSums;
public SumNode(T val) {
this.val = val;
this.possibleSums = new TreeSet<>();
}
}
private static void calcPossibleSums(SumNode<? extends Integer> node) {
if ( node != null && node.possibleSums.isEmpty() ) {
if ( node.left == null && node.right == null ) {
node.possibleSums.add(node.val);
} else {
if (node.left != null) {
calcPossibleSums(node.left);
for (Integer i : node.left.possibleSums) {
node.possibleSums.add(i + node.val);
}
}
if (node.right != null) {
calcPossibleSums(node.right);
for (Integer i : node.right.possibleSums) {
node.possibleSums.add(i + node.val);
}
}
}
}
}
public static boolean canSumTo(SumNode<? extends Integer> root, Integer sum) {
calcPossibleSums(root);
return root.possibleSums.contains(sum);
}
BFS
import collections
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def find_sum(root, target):
def add_to_queue(node, remaining):
if not node:
return
queue.append((node, remaining))
queue.append((node, target))
queue = collections.deque()
queue.append((root, target))
visited = set()
while queue:
head = queue.popleft()
if head in visited:
continue
remaining = head[1] - head[0].data
if not remaining:
return True
add_to_queue(head[0].left, remaining)
add_to_queue(head[0].right, remaining)
return False
def sum_nodes_starting_at(root, sums, cur_sum):
if not root:
sums.add(cur_sum)
return
cur_sum += root.data
sums.add(cur_sum)
sum_nodes_starting_at(root.left, sums, cur_sum)
sum_nodes_starting_at(root.right, sums, cur_sum)
if __name__ == '__main__':
nodes = {7: Node(7),
8: Node(8),
6: Node(6),
2: Node(2),
-3: Node(-3),
9: Node(9),
5: Node(5),
4: Node(4),
-1: Node(-1),
100: Node(100)
}
root = nodes[7]
root.left, root.right = nodes[8], nodes[6]
nodes[8].left, nodes[8].right = nodes[2], nodes[-3]
nodes[6].left, nodes[6].right = nodes[-3], nodes[9]
nodes[2].left, nodes[2].right = nodes[5], nodes[4]
nodes[-3].left, nodes[-3].right = nodes[4], nodes[-1]
nodes[9].left, nodes[9].right = nodes[-1], nodes[100]
sums = set()
for v in nodes.values():
sum_nodes_starting_at(v, sums, 0)
for sum in sums:
assert find_sum(root, sum)
for i in range(-1, max(nodes.keys()) + 1):
if i in sums:
continue
assert not find_sum(root, i), i
BFS
import collections
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def find_sum(root, target):
def add_to_queue(node, remaining):
if not node:
return
queue.append((node, remaining))
queue.append((node, target))
queue = collections.deque()
queue.append((root, target))
visited = set()
while queue:
head = queue.popleft()
if head in visited:
continue
remaining = head[1] - head[0].data
if not remaining:
return True
add_to_queue(head[0].left, remaining)
add_to_queue(head[0].right, remaining)
return False
def sum_nodes_starting_at(root, sums, cur_sum):
if not root:
sums.add(cur_sum)
return
cur_sum += root.data
sums.add(cur_sum)
sum_nodes_starting_at(root.left, sums, cur_sum)
sum_nodes_starting_at(root.right, sums, cur_sum)
if __name__ == '__main__':
nodes = {7: Node(7),
8: Node(8),
6: Node(6),
2: Node(2),
-3: Node(-3),
9: Node(9),
5: Node(5),
4: Node(4),
-1: Node(-1),
100: Node(100)
}
root = nodes[7]
root.left, root.right = nodes[8], nodes[6]
nodes[8].left, nodes[8].right = nodes[2], nodes[-3]
nodes[6].left, nodes[6].right = nodes[-3], nodes[9]
nodes[2].left, nodes[2].right = nodes[5], nodes[4]
nodes[-3].left, nodes[-3].right = nodes[4], nodes[-1]
nodes[9].left, nodes[9].right = nodes[-1], nodes[100]
sums = set()
for v in nodes.values():
sum_nodes_starting_at(v, sums, 0)
for sum in sums:
assert find_sum(root, sum)
for i in range(-1, max(nodes.keys()) + 1):
if i in sums:
continue
assert not find_sum(root, i), i
import collections
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def find_sum(root, target):
def add_to_queue(node, remaining):
if not node:
return
queue.append((node, remaining))
queue.append((node, target))
queue = collections.deque()
queue.append((root, target))
visited = set()
while queue:
head = queue.popleft()
if head in visited:
continue
remaining = head[1] - head[0].data
if not remaining:
return True
add_to_queue(head[0].left, remaining)
add_to_queue(head[0].right, remaining)
return False
def sum_nodes_starting_at(root, sums, cur_sum):
if not root:
sums.add(cur_sum)
return
cur_sum += root.data
sums.add(cur_sum)
sum_nodes_starting_at(root.left, sums, cur_sum)
sum_nodes_starting_at(root.right, sums, cur_sum)
if __name__ == '__main__':
nodes = {7: Node(7),
8: Node(8),
6: Node(6),
2: Node(2),
-3: Node(-3),
9: Node(9),
5: Node(5),
4: Node(4),
-1: Node(-1),
100: Node(100)
}
root = nodes[7]
root.left, root.right = nodes[8], nodes[6]
nodes[8].left, nodes[8].right = nodes[2], nodes[-3]
nodes[6].left, nodes[6].right = nodes[-3], nodes[9]
nodes[2].left, nodes[2].right = nodes[5], nodes[4]
nodes[-3].left, nodes[-3].right = nodes[4], nodes[-1]
nodes[9].left, nodes[9].right = nodes[-1], nodes[100]
sums = set()
for v in nodes.values():
sum_nodes_starting_at(v, sums, 0)
for sum in sums:
assert find_sum(root, sum)
for i in range(-1, max(nodes.keys()) + 1):
if i in sums:
continue
assert not find_sum(root, i), i
def sum_tree(self, my_sum):
if self.leftChild is None and self.rightChild is None and self.value is my_sum:
return True
else:
if self.leftChild:
if self.leftChild.sum_tree(my_sum) is True:
return True
if self.rightChild:
if self.rightChild.sum_tree(my_sum) is True:
return True
return False
void printPathSum(struct tree *node, int k, vector<int> &v) {
static int sum = 0;
if(node == NULL) {
return;
}
v.push_back(node->key);
sum = sum + node->key;
if(sum > k) {
return;
}
if(sum == k) {
printf("Found sum \n");
for(int i = 0;i < v.size(); i++) {
cout <<v[i] <<" ";
}
printf("\n");
return;
}
printPathSum(node->left, k, v);
sum = sum - node->left->key;
v.pop_back();
printPathSum(node->right, k, v);
sum = sum - node->right->key;
v.pop_back();
}
Whether node can be shared by two ancestors but by traversing down the tree we have to encounter only left and right child of a node. We can do this question similar to finding whether any sum equals the root to leaf path sum in a tree.
- codeinduce July 24, 2017