Amazon Interview Question


Country: United States




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

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.

bool checkSum100(node *root){
	if(root == NULL){
		return false;
	}
	//if leaf check the sum
    if(node->left == NULL && node->right == NULL && node->data == sum){
        return true;
    }
    return hasPathSum(node->left, sum-node->data) || hasPathSum(node->right, sum-node->data);
}

- codeinduce July 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Fernando July 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- funk July 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- smffap July 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- smffap July 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ssffap July 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Boolean pathSum100(Node n, int sum){
           Int runSum=sum;
           if(null == n){
                    return ( sum == 100);
           } else {
                    runSum = sum+n.value;
                    if (pathSum100(n.left, runSum) == 100 || pathSum100(n.right, runSum) ==100){
                              return true;
                    }
           }
}

- Anonymous July 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS

public boolean findBranch(Node node, int sum) {
		if (node.left == null && node.right == null){ // leaf
			return node.data == sum; 
		}
		
		return  (node.left  != null && findBranch(node.left,  sum - node.data)) || 
				(node.right != null && findBranch(node.right, sum - node.data));
	}

- vzyarko July 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if nodes shared we could speedup the search by saving node.leftSum & node.rightSum to reuse them in later recursions

- vzyarko July 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Batool July 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();

}

- vikalpveer August 16, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More