Amazon Interview Question
SDE-2sTeam: android amazon app, social shopping
Country: United States
Interview Type: In-Person
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.. :)
"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.
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);
}
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.
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.
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
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);
}
}
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?
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)
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);
}
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);
}
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);
}
}
}
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]));
}
}
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();
}
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 );
}
}
C++
- kyduke June 23, 2015