Amazon Interview Question for SDE-2s


Team: android amazon app, social shopping
Country: United States
Interview Type: In-Person




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

C++

#include <iostream>
#include <vector>

using namespace std;

struct Node {
	int value;
	Node* left;
	Node* right;
};

bool isFirst = true;

void printNode(Node* node) {
	if (node == NULL) return;

	cout << "(";
	printNode(node->left);

	cout << node->value;

	printNode(node->right);
	cout << ")";
}

Node* createNode(int value) {
	Node* node;

	node = new Node();
	node->value = value;
	node->left = NULL;
	node->right = NULL;

	return node;
}

void deleteNodeAll(Node* node) {
	if (node->left) {
		deleteNodeAll(node->left);
		delete node->left;
	}
	
	if (node->right) {
		deleteNodeAll(node->right);
		delete node->right;
	}
}

void findSumInStack(vector<Node*>& stack, int sum) {
	int i, j, l, s;

	l = stack.size() - 1;
	s = 0;
	for (i = l; i >= 0; i--) {
		s += stack[i]->value;
		if (s == sum) {
			if (isFirst == false) {
				cout << ", {";
			} else {
				isFirst = false;
				cout << "{";
			}
			for (j = i; j < l; j++) {
				cout << stack[j]->value << ", ";
			}
			cout << stack[l]->value;
			cout << "}";
		}
	}
}

void searchBTreeSum(Node* node, vector<Node*>& stack, int sum) {
	if (node == NULL) return;

	stack.push_back(node);

	findSumInStack(stack, sum);

	searchBTreeSum(node->left, stack, sum);
	searchBTreeSum(node->right, stack, sum);

	stack.pop_back();
}

int main(int argc, char* argv) {
	Node* root;
	vector<Node*> stack;

	root = createNode(2);
	root->left = createNode(3);
	root->right = createNode(5);

	root->left->left = createNode(4);
	root->left->right = createNode(8);

	root->right->left = createNode(6);
	root->right->right = createNode(-2);

	root->right->right->right = createNode(2);

	printNode(root);
	cout << "\n";

	searchBTreeSum(root, stack, 7);
	cout << "\n";

	deleteNodeAll(root);
	delete root;

	return 0;
}

- kyduke June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simply do a DFS on the tree.. and while doing DFS maintain the current nodes in a stack... when their sum reaches "SUM".. print the stack..

Now you know the logic so it would be better to write the code yourself.. that will help you understand it more clearly... and you will never forget it.. :)

- coderadi June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but it will miss the {2,5,-2,2}

- Vipul June 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

"Now, you do know the logic so it would be better to write the code yourself. that will help YOU understand it more clearly... and you will never forget it.. :)" [sic]

Imagine a single path from root to leaf as:

1 -> 2 -> 4 -> 8  [etc]

your algorithm must then check:

(), (1), (1, 2), (1, 2, 4), (1, 2, 4, 8), (2), (2, 4), (2, 4, 8), (4), (4, 8), (8)

But your incorrect logic will only test:

(), (1), (1, 2), (1, 2, 4), (1, 2, 4, 8)

Perhaps you should take your own advice and code the algorithm (and, gasp, test it) since your logic is wrong. I guarantee that you will remember it. Or at least remember to not talk down to people.

- zortlord June 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

As mentioned before Depth First Search but aggregating the sum and creating a new list once found that adds to the expected sum.

public static List<List<int>> TreePathThatSumsN(Node root, int n)
{
	var result = new List<List<int>>();
	
	CoreTPTSN(root, n, 0, result, new List<int>());

	return result;
}

private static void CoreTPTSN(
	Node root, 
	int n,
	int sum,
	List<List<int> result, 
	List<int> current);
{
	if(root == null)
		return;

	sum += root.Data;
	current.Add(root.Data);

	if(sum == n)
	{
		result.Add(new List<int>(current));
	}

	CoreTPTSN(
		root.Left, 
		n,
		sum,
		result, 
		current);
	
	CoreTPTSN(
		root.Rigth, 
		n,
		sum,
		result, 
		current);

	current.Remove(current.Count-1);
}

- Nelson Perez June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Won't work. Doesn't consider paths not including the root.

IE: in the original example, would not consider (3, 4)

- zortlord June 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about: (let's call the target sum k)

1) make a copy of the tree with each node being the accumulated sum of its predecessors
2) use a modified version of the "identify pairs in an array that sum to k" algorithm for each path in the tree, via DFS
3) in addition, any node in the tree with value equal to k corresponds to another solution that goes from the root to this node

Step 1 should simply be a DFS with O(1) per traversal, Step 2 is also a DFS with O(1) per traversal, and Step 3 is simply an additional check to be incorporated in Step 2.

If this procedure works, then the whole algorithm should just be O(n) where n is the number of nodes.

- Naph June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Start from the root:
Check if the value of the node is equal to the sum, if yes then print.
put the value of the root inside a list.
pass this list to its childern.

While traversing DFS
for each subsequent node, add the value of the node to all the elements inside the list passed to it by its parent.
So 2 things here:
1. Check if this sum is equal to the required value. If yes, you found a path.
2. Add this sum to a new list.
Finally also add the value of the current node to the above list and pass it to its chlidren.

To get the path as an output we can use a map instead of list where the key will be the path value and the value be the path string.

- nemin June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

So unless its a binary search tree, we will have to examine all possible paths.
We cannot stop if we find a matching sequence (E.g. 2,5). We will still need to keep going till we
reach the leaf node. (E.g. 2,5,-2,2 would be a match, 2,3,4 would not be a match)

So here is a O(n^2) algorithm.

Start at root
For any node, check if there is a match till here and print it.
If its a leaf node, we return.
Else, we pass in the remaining sum (number to be found - previous node) to its children and recurse

- puneet.sohi June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is a sample code:

void findSeq(node *n, int sum, vector<int>V)
{
	if(n->lt == NULL && n->rt == NULL)
	{
		//leaf node
		if(n->data == sum)
		{
			//match
			V.push_back(n->data);
			cout << endl << "=================" << endl;
			printVec(V);
			cout << "=================" << endl;
		}
		else
		{
			//no match
			return;
		}
	}
	else
	{
		V.push_back(n->data);
		//cout<< "Not a leaf node" << endl;
		if(n->data == sum)
		{
			//match
			cout << endl << "=================" << endl;
			printVec(V);
			cout << "=================" << endl;
		}
		//recurse on child nodes
		if(n->lt != NULL)
			findSeq(n->lt, (sum - n->data), V);
		if(n->rt != NULL)
			findSeq(n->rt, (sum - n->data), V);
	}

}

- puneet.sohi June 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

So I'm not sure if I have the right idea.. getting the path from root to any node is easy, when you do the recursion down, you just pass in the current sum while you keep track of the nodes in a stack. Getting the path between any two nodes in the lineage just means you have to pass an array of sums, every time you go down the recursion, not only do you give the current sum, you also pass in the current sum from this point.

So in this question, if you're going down left most branches.. it would be:

node 2 : sum{2} : stack = 2
node 3 : sum{5, 3} : stack = 2, 3
node 4 : sum{9, 7, 4} : stack = 2, 3, 4

So at the bottom leaf, you'll see that 7 is the sum you want meaning the 7 is the sum starting from node 3 to this node. So you'd create a copy of the stack, pop until you get to that node.

Does that sound right?

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

def treePathSum(node, s):
  def _pathSum(node, cur_path, c):
    if node:
      v=int(node.val)
      c-=v
      cur_path.append(node)
      if c==0:
        for n in cur_path:
          print(n.val,' ')
        print('---')

      _pathSum(node.left, cur_path, c)
      _pathSum(node.right, cur_path, c)
      cur_path.pop()

  if node:
     treePathSum(node.left, s)
     treePathSum(node.right, s)
     _pathSum(node, [], s)

- gen-y-s- June 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ code

#include<iostream>
#include<vector>
using namespace std;
struct Node {
	int data;
	Node* left;
	Node* right;
	Node(int x): data{x}, left{nullptr} , right{nullptr} {} 
	Node(int x, Node* l,Node* r): data{x}, left{l},right{r} {} 
};
void findPaths(Node* n, int sum, int sumLeft, int start, int level) {
	static vector < int > X(100);
	if(n==nullptr)
		return;
	X[level]=n->data;
	if(sumLeft==n->data) {
		for(int i=start;i<=level;i++)
			cout<<X[i]<<" ";
		cout<<endl;
	}
	findPaths(n->left,sum,sumLeft-(n->data),start,level+1);
	findPaths(n->left,sum,sum,level+1,level+1);
	findPaths(n->right,sum,sumLeft-(n->data),start,level+1);
	findPaths(n->right,sum,sum,level+1,level+1);
}
void findPaths(Node * root, int sum) {
	findPaths(root,sum,sum,0,0);
}
int main() {
	Node n1{4};
	Node n2{8};
	Node n3{3,&n1,&n2};
	Node n4{6};
	Node n5{2};
	Node n6{-2,nullptr,&n5};
	Node n7{5,&n4,&n6};	
	Node n8{2,&n3,&n7};
	findPaths(&n8,7);
}

- montreal6 June 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function path_sum($node, $path, $level, $target){
	if($node === NULL){
		return;
	}
	
	$path[$level] = $node->data;
	$sum = 0;
	for($i=$level; $i>=0; $i--){
		$sum += $path[$i];
		if($sum === $target){
			for($j=$i; $j<=$level; $j++){
				echo $path[$j] . ' - ';
			}
			echo '<br/>';
		}
	}
	/*$sum += $node->data;
	if($sum === $target){
		print_r('<pre>'); 
		print_r($path);
	}*/
	
	path_sum($node->left, $path, $level + 1, $target);
	path_sum($node->right, $path, $level + 1, $target);
}

- oelsayed June 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS, use a pointer to parent node, runtime complexity of O(n log n) with memory O(log n)

class TreeNode {
    TreeNode parent;
    TreeNode lchild;
    TreeNode rchild;
    int data;
}

    public static void addToSum(TreeNode tree, int sum) {
        Stack<TreeNode> dfsStack = new Stack<>();
        dfsStack.push(tree);
        int currentSum = 0;
        StringBuffer output = new StringBuffer();

        while (!dfsStack.empty()) {
            TreeNode node = dfsStack.pop();
            output.setLength(0);
            output.append("{");
            output.append(node.data);
            output.append("}");

            currentSum = node.data;
            TreeNode parent = node.parent;
            while (null != parent) {
                output.insert(1, ", ");
                output.insert(1, parent.data);
                currentSum += parent.data;
                if (currentSum == sum) {
                    System.out.println(output);
                }
                parent = parent.parent;
            }

            if (null != node.rchild) {
                dfsStack.push(node.rchild);
            }

            if (null != node.lchild) {
                dfsStack.push(node.lchild);
            }
        }
    }

- kurtl July 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

do dfs and maintain a stack
check the stack for when you are backtracking
input file:
1:2
2:3
3:5
4:4
5:8
5:6
7:-2
15:2

package com.loadgeneral.projects;

import java.util.Map;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;

import java.util.Iterator;





public class PathSum {

		
	Node root = null;
	Map<Integer, Node> nodes = new HashMap<Integer,Node>();
	
	
	static class Node {
		int value;
		int id;
		Node left;
		Node right;
		
		public Node ( int id, int val ){
			this.id = id;
			this.value = val;
		}
		
		public String toString(){
			return id+":"+this.value;
		}
	}

	public PathSum(String fileName) {
		try (BufferedReader rdr = new BufferedReader(new FileReader(fileName))) {
			String line = null;
			while ((line = rdr.readLine()) != null) {
				Node n = parseLine(line);
				if ( root == null ) root = n;
			}
		} 
		catch (IOException ioe) {
			System.err.println("error: " + ioe);
		}
	}
	
	Node parseNode( int id, int val ) {
		
		if ( nodes.containsKey(id)  ) return nodes.get(id);
		
		Node n = new Node(id,val);
		nodes.put( id, n);
		return n;	
	}

	Node parseLine(String line) {
		int idx = line.indexOf(":");
		int id = Integer.parseInt(line.substring(0, idx).trim());
		int val = Integer.parseInt(line.substring(idx+1).trim());

		Node n = parseNode(id,val);
		if ( id != 1 ) {
			Node parentNode = nodes.get(id/2);
			if ( id%2 == 0 ) parentNode.left = n;
			if ( id%2 == 1 ) parentNode.right = n;
		}
        
		return n;
	}
	
	void dfsSum( Node node, Deque<Integer> stack, int sum  ){
		
        if ( node == null ) return;
        stack.push(node.value);

        dfsSum(node.left,stack,sum);
        dfsSum(node.right,stack,sum);
        checkStack(stack,sum);
        stack.pop();
	}
	
	void checkStack( Deque<Integer> stack, int sum  ){
	    int currSum = 0;
	    boolean found = false;
	    for ( Iterator<Integer> iter = stack.iterator() ; iter.hasNext(); ) {
	    	currSum += iter.next();
            if ( currSum == sum ) {
                found = true;
                break;
            }
	    }
	    
	    if ( found == false ) return;
	    currSum = 0;
	    List<Integer> l = new ArrayList<Integer>();
	    for ( Iterator<Integer> iter = stack.iterator() ; iter.hasNext(); ) {
	    	int val = iter.next();
	    	currSum += val;
        	l.add(0,val);
            if ( currSum == sum ) {
                break;
            }
	    }
	    
	    System.out.print(l + " ");
	   	    
	}

void printSum(int sum) {
        dfsSum(this.root, new ArrayDeque<Integer>(), sum);
	}

	static public void main(String[] args) {
		PathSum ps = new PathSum(args[0]);
		ps.printSum(Integer.parseInt(args[1]));
	}

}

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

C# version

static void PrintSumPath(BinarySearchTree<int>.Node root, int k, List<int> list)
        {
            if (root == null || root.data > k)
                return;

            list.Add(root.data);

            if (root.data == k)
            {
                PrintList(list);
            }


            PrintSumPath(root.left, k - root.data, list);
            PrintSumPath(root.right, k - root.data, list);

            list.Remove(root.data);

            PrintSumPath(root.left, k, list);
            PrintSumPath(root.right, k, list);

        }

        private static void PrintList(List<int> list)
        {
            foreach (int i in list)
                Console.Write(i + " ");

            Console.WriteLine();
        }

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

Runtime complexity of O(n^2) with memory O(n) (if this were a balanced binary tree it would be O(n Log n) and O(log n) respectively):

static class Node{
    int value;
    Node left, right;
}

//use non-recursive DFS to start a path towards the leaves of each branch
public static void findSumPaths(Node root, int sum){
    Stack<Node> dfsPosition = new Stack<Node>();
    dfsPosition.push(root);
    while(!dfsPosition.isEmpty()){
        StringBuilder output = new StringBuilder();
        output.append('(');
        Node node = dfsPosition.pop();
        makeOutputFromPosition(node, 0, sum, output);    
        if(node.right != null){
            dfsPosition.push(node.right);
        }
        if(node.left != null){
            dfsPosition.push(node.left);
        }
    }
}

//Recursive DFS search from each specified node checking if the current path taken meets the sum
public static void makeOutputFromPosition(Node node, int currentSum, int sum, StringBuilder output){
    currentSum += node.value;
    boolean addedComma = false;
    String intString = Integer.toString(node.value);
    if(output.length() > 1){
        output.append(',');
        addedComma = true;
    }
    output.append(intString);
    if(currentSum == sum){
        output.append(')');
        System.out.println(output.toString());
        output.setLength(output.length()-1);
    }
    if(node.left != null){
        makeOutputFromPosition(node.left, currentSum, sum, output);
    }
    if(node.right != null){
        makeOutputFromPosition(node.right, currentSum, sum, output);
    }
    output.setLength(output.length() - intString.length());
    if(addedComma){
        output.setLength(output.length() -1 );
    }
}

- zortlord June 22, 2015 | 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