Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

Note that the example tree is not a BST. Is this a misspell, or should the BST property be used to reduce space complexity.

- Alex August 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In-fact I was too confused. Trying to solve the problem considering the BST and wondering how to use the BST property.
If it is plain binary tree,
we can use two stack and do level order traversal with swapping stacks.

- codealtecdown September 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

void LevelSum(node * n, vector <int> &sum, int level)
{
if(n == NULL)
return;
else
{

if (sum.size() - 1 < level)
sum.push_back(0);

sum[level] += n->data;

//if (n->left != NULL || n->right != NULL)


LevelSum(n->left, sum, level + 1);
LevelSum(n->right, sum, level + 1);
}

}

- AndreasVolcenstein August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class Main {
	
	public static void computeSumAtHeights(BinaryNode tree, int currentHeight, List<Integer> sums) {
		
		if(sums.size() <= currentHeight) {
			sums.add(currentHeight, new Integer(tree.getValue()));
		} else {
			sums.set(currentHeight, sums.get(currentHeight) + tree.getValue());
		}
		
		if(tree.getLeft() != null) {
			computeSumAtHeights(tree.getLeft(), currentHeight + 1, sums);
		} 
		
		if(tree.getRight() != null) {
			computeSumAtHeights(tree.getRight(), currentHeight + 1, sums);
		}
		
	}
	
	
	public static void main(String... args) {
		
		BinaryNode level2Left1 = new BinaryNode(null, null,4);
		BinaryNode level2Right1 = new BinaryNode(null, null,5);
		BinaryNode level1Left = new BinaryNode(level2Left1, level2Right1, 2);
		
		BinaryNode level2Left2 = new BinaryNode(null, null,1);
		BinaryNode level2Right2 = new BinaryNode(null, null,2);
		BinaryNode level1Right = new BinaryNode(level2Left2, level2Right2, 3);
		
		BinaryNode root = new BinaryNode(level1Left, level1Right,1);
		
		List<Integer> sums = new ArrayList<Integer>(0);
		
		computeSumAtHeights(root, 0, sums);
		
		System.out.println(sums);
	}

}

- june.pravin August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You need to traverse the tree by level, so use BFS would do the job, but standard BFS would not work because it do not have clear boundary on each level, the key is using 2 queues, code is like:
std::queue<Node*> queues[2];

vector<int> sizes;

int cur_queue_index = 0;

int next_queue_index =1;

if (root) {
queues[0].push(root);
} else {
return;
}

cout << "[";
int sum = 0;
while (!queue[cur_queue_index].empty()) {
const node * const current_node = queues[cur_queue_index].front;
queues[cur_queue_index].pop();
sum += current_node->value;

if(current_node->left) {
queues[next_queue_index].push(current_node->left);
}

if(current_node->right) {
queues[next_queue_index].push(current_node->right);
}

if(queue[cur_queue_index].empty())
{
cout << sum << ",";
sum = 0;
swap(next_queue_index, cur_queue_index);
}
}
cout << "]";

- lucifer1986 August 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution using BFS.
Running time O(N), Space complexity O(N).

#include<iostream>
#include<list>
using namespace std;

struct node {
  int value;
  node *left;
  node *right;
  node(int v):value(v), left(0), right(0){}
};

list<int> addup(node* r)
{
  list<int> result;
  list<node*> queue;
  int cur_level= 0;
  int next_level = 0;
  int total = 0;

  if (!r)
    return result;

  queue.push_back(r);
  cur_level++;
  while(queue.size())
  {
    node *cur = queue.front();
    queue.pop_front();
    if (cur->left)
    {
      queue.push_back(cur->left);
      next_level++;
    }
    if (cur->right)
    {
      queue.push_back(cur->right);
      next_level++;
    }
    cur_level--;
    total += cur->value;
    if (cur_level==0)
    {
      result.push_back(total);
      cur_level = next_level;
      next_level = 0;
      total = 0;
    }
  }

- hankm2004 August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.List;

public class SUMBST {
	class TreeNode{
		int value;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { value = x; }
	}

	public static void SumAtLevel(TreeNode tree, int level, List<Integer> sums) {

		if(sums.size() <= level) {
			sums.add(level, tree.value);
		} else {
			sums.set(level, sums.get(level) + tree.value);
		}

		if(tree.left != null) {
			SumAtLevel(tree.left, level + 1, sums);
		} 

		if(tree.right != null) {
			SumAtLevel(tree.right, level + 1, sums);
		}

	}

	public static void main(String[] args) {
		

		TreeNode root = new SUMBST(). new TreeNode(5);
		TreeNode left = new SUMBST(). new TreeNode(2);
		TreeNode left2 = new SUMBST(). new TreeNode(1);
		TreeNode right2 = new SUMBST(). new TreeNode(4);
		TreeNode right = new SUMBST(). new TreeNode(7);
		TreeNode left1 = new SUMBST(). new TreeNode(6);
		TreeNode right1 = new SUMBST(). new TreeNode(8);

		
		root.left = left;
		//root.left.left = left2;
		//root.left.right = right2;

		root.right = right;
		//root.right.left = left1;
		//root.right.right = right1;

		
		List<Integer> sums = new ArrayList<Integer>(0);
		SumAtLevel(root, 0, sums);
		System.out.println(sums);
	}

}

- rajmeena.cse September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NB: The supplied sample isn't a BST, but it isn't important to the problem. Simple tree traversal - I use a preorder but it isn't important.
O(n) time and O(n) space (O(log n) space if your tree is unbalanced by at most a constant factor).

from data_structures import Queue

class Node(object):

    def __init__(self, key):
        super(Node, self).__init__()
        self.key = key
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.key)

def sum_levels(root):

    def visit(node, i):
        if node:
            try:
                sums[i] += node.key
            except IndexError:
                sums.append(node.key)
            i += 1
            visit(node.left, i)
            visit(node.right, i)
            i -= 1
            
    sums = []
    visit(root, 0)
    return sums


if __name__ == "__main__":
    nodes = [1, 2, 3, 4, 5, 1, 2]
    q = Queue()
    r = Node(nodes[0])
    q.enqueue(r)
    for k in range(1, len(nodes), 2):
        n = q.dequeue()
        n.left = Node(nodes[k])
        q.enqueue(n.left)
        n.right = Node(nodes[k + 1])
        q.enqueue(n.right)
    print(sum_levels(r))

- Dave September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static ArrayList<Integer> levelSumArray(BinaryTreeNode N) {
		// Now do the level-order traversal with calculating sum at every level

		if (N == null)
			return null;
		ArrayList<Integer> myList = new ArrayList<Integer>();

		Queue<BinaryTreeNode> myQueue = new LinkedList<GFG.BinaryTreeNode>();

		myQueue.add(N);
		myQueue.add(null);
		int sum = 0;
		while (!myQueue.isEmpty()) {
			System.out.println(myQueue.toString());
			BinaryTreeNode current = myQueue.poll();
			if (current != null) {
				sum = sum + current.value;
				if (current.left != null) {
					myQueue.add(current.left);
				}
				if (current.right != null) {
					myQueue.add(current.right);
				}
			}

			else {
				// it could be actual end or a partition
				myList.add(sum);
				sum = 0;
				if (!myQueue.isEmpty())
					myQueue.add(null);
			}

		}
		// myList.add(sum);
		return myList;

	}
public static class BinaryTreeNode {

		public BinaryTreeNode left;
		public BinaryTreeNode right;
		public int value;

		public BinaryTreeNode(int v) {
			value = v;
			left = null;
			right = null;
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return Integer.toString(value);
		}

	}

- venkatesh yerneni September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a queue to store a tuple of values ( treenode, level). Start with initial sum of 0 for the root. Add the tuple (rootnode, 0) to the queue initially. Loop till the queue is empty. At each iteration check if the level of the removed node matches the current level. If it matches, then add node.data to the sum. If level is not the same, add the sum till now to the results list, reset sum to the current node.data and continue.

def findLevelOrderSumBST(root):
	if root == None:
		return root

	results = []
	level = 0; levelsum = 0

	q = Queue()
	q.put((root, level))

	while not q.empty():
		node, currlevel = q.get()

		leftchild = node.left
		rightchild = node.right

		if leftchild != None:
			q.put((leftchild, currlevel + 1))

		if rightchild != None:
			q.put((rightchild, currlevel + 1))

		if currlevel == level:
			levelsum = levelsum + node.data

		else:
			results.append(levelsum)
			levelsum = node.data

			level = currlevel

	results.append(levelsum)
	return results

- sauravmaximus September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.Queue;

public class PrintATreeLevelByLevel {
public static class Node{
int data;
public Node left;
public Node right;

public Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}

public void printATreeLevelByLevel(Node n){
Queue<Node> queue = new LinkedList<Node>();
queue.add(n);
int node = 1; //because at root
int child = 0; //initialize it with 0
while(queue.size() != 0){
Node n1 = queue.remove();
node--;
System.err.print(n1.data +" ");

if(n1.left !=null){
queue.add(n1.left);
child ++;
}
if(n1.right != null){
queue.add(n1.right);
child ++;
}
if( node == 0){
System.err.println();
node = child ;
child = 0;
}
}
}

public static void main(String[]args){
PrintATreeLevelByLevel obj = new PrintATreeLevelByLevel();
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);

node4.left = node2;
node4.right = node6;
node2.left = node1;
// node2.right = node3;
node6.left = node5;
node6.right = node7;
node1.left = node8;
obj.printATreeLevelByLevel(node4);
}
}

- Jyoti Namdeo September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Implementation: cpluspluslearning-petert.blogspot.co.uk/2015/09/bst-return-sum-of-each-level-amazon.html

Test

void TestCasesOfSumOfEachLevelOfTree()
{
    std::vector<int> testInput{ 1 };
    TreeNode<int>* rootBFS = ConstructTreeOnSortedValueBFS(testInput);
    assert(rootBFS != nullptr);

    std::vector<int> result;
    GetSumOfEachLevelOfTree(rootBFS, result);
    assert(result.size() == 1);
    assert(result[0] == 1);
    DeleteTree(&rootBFS);

    testInput = {1, 2};
    rootBFS = ConstructTreeOnSortedValueBFS(testInput);
    assert(rootBFS != nullptr);
    result.clear();
    GetSumOfEachLevelOfTree(rootBFS, result);
    assert(result.size() == 2);
    assert(result[0] == 2);
    assert(result[1] == 1);
    DeleteTree(&rootBFS);

    testInput = { 1, 2, 3 };
    rootBFS = ConstructTreeOnSortedValueBFS(testInput);
    assert(rootBFS != nullptr);
    result.clear();
    GetSumOfEachLevelOfTree(rootBFS, result);
    assert(result.size() == 2);
    assert(result[0] == 2);
    assert(result[1] == 4);
    DeleteTree(&rootBFS);

    testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    rootBFS = ConstructTreeOnSortedValueBFS(testInput);
    assert(rootBFS != nullptr);
    result.clear();
    GetSumOfEachLevelOfTree(rootBFS, result);
    assert(result.size() == 4);
    assert(result[0] == 6); // 6
    assert(result[1] == 11);// 3, 8
    assert(result[2] == 21); // 1, 4, 7, 9 
    assert(result[3] == 17);// 2, 5, 10
    DeleteTree(&rootBFS);
}

- peter tang September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class SumLevels {

	public static class Node<T> {
		Node<T> left;
		Node<T> right;
		T data;
		
		public Node() {
			
		}
		
		public Node(T data) {
			this.data = data;
		}
	}
	
	public static int heightTree(Node<?> root) {
		if (root == null) {
			return 0;
		} else {
			return 1 + Math.max(heightTree(root.left), heightTree(root.right));
		}
	}
	
	public static List<Integer> sumLevels(Node<Integer> root) throws IllegalArgumentException {
		List<Integer> res = new ArrayList<Integer>();
		Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
		int height = heightTree(root);
		int breadth = 1;
		if (root == null) {
			throw new IllegalArgumentException("root node doesn't be null");
		}
		q.add(root);
		res.add(root.data);
		for (int i = 1; i < height; i++){
			int sum = 0;
			for (int j = 1; j <= breadth; j++) {
				Node<Integer> n = q.poll();
				if (n.left != null) {
					q.add(n.left);
					sum += n.left.data;
				}
				if (n.right != null) {
					q.add(n.right);
					sum += n.right.data;
				}
			}
			res.add(sum);
			breadth *= 2;
		}
		return res;
	}
	
	public static void main(String[] args) {
		Node<Integer> root = new Node<Integer>(1);
		
		root.left = new Node<Integer>(2);
		root.right = new Node<Integer>(3);
		
		root.left.left = new Node<Integer>(4);
		root.left.right = new Node<Integer>(5);
		
		root.right.left = new Node<Integer>(1);
		root.right.right = new Node<Integer>(2);
		
		System.out.println(sumLevels(root));
	}
}

- gustavoanatoly September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the tree is always complete, it could be represented as an array.

Given a level n, the can obtain the index of the first element of that level, thus the only thing required is sum the elements array[n:n+1]

#!/usr/bin/env python3

from math import log2

def first_element_index(level):
    return 2**level - 1

def elements_in_level(tree, level):
    i = first_element_index(level)
    j =	first_element_index(level + 1)
    return tree[i:j]


def solution(tree):
    number_of_levels = int(log2(len(tree)))
    sum_in_levels = []
    for level in range(number_of_levels + 1):
        sum_in_levels.append(sum(elements_in_level(tree, level)))
    return sum_in_levels


assert solution([1, 2, 3, 4, 5, 1, 2]) == [1, 5, 12]

- JP Ventura January 09, 2016 | 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