Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

void printpathGivensum(struct btree *root, int givensum)
{
	int patharray[1000];
	int sum=0;
	tracknodes(root, patharray, 0, sum, givensum);
}
void tracknodes(struct btree *root, int patharray[1000], int len, int sum, int givensum)
{
	if(root == NULL)
	return;
	
	patharray[len++]= root->data;
	sum=sum+ root->data;
	
	if(root->left == NULL && root->right ==NULL )
	printarray(patharray, len, sum, givensum);
	else
	{
		tracknodes(root->left, patharray, len, sum, givensum);
		tracknodes(root->right, patharray, len, sum, givensum);
	}
	
	
}
void printarray(int patharray[1000], int len, int sum, int givensum)
{
	int i;
	
	if(sum == givensum)
	{
	cout<<"Givensum: "<<givensum<<" "<<"Path :";
	for(i=0; i<len; i++)
	cout<<patharray[i]<<" ";
	}
 
}

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

void printpathGivensum(struct btree *root, int givensum)
{
int patharray[1000];
int sum=0;
tracknodes(root, patharray, 0, sum, givensum);
}
void tracknodes(struct btree *root, int patharray[1000], int len, int sum, int givensum)
{
if(root == NULL)
return;

patharray[len++]= root->data;
sum=sum+ root->data;

if(root->left == NULL && root->right ==NULL )
printarray(patharray, len, sum, givensum);
else
{
tracknodes(root->left, patharray, len, sum, givensum);
tracknodes(root->right, patharray, len, sum, givensum);
}

}
void printarray(int patharray[1000], int len, int sum, int givensum)
{
int i;

if(sum == givensum)
{
cout<<"Givensum: "<<givensum<<" "<<"Path :";
for(i=0; i<len; i++)
cout<<patharray[i]<<" ";
}

}

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

public List<List<Integer>> findPath (TreeNode root, int target){
		 List<List<Integer>> rst = new ArrayList<List<Integer>> ();
		 if (root == null) {
			 return rst ;
		 }
		 List<Integer> cur = new ArrayList<> ();		 
		 helper (root, target, cur, rst);
		 return rst ;		 
	}
	
	private  void helper (TreeNode root, int target, List<Integer> cur , List<List<Integer>> rst) {
	     if (root == null) {
	    	 return ;
	     }
	     if (root.left != null && root.right != null && target - root.val == 0) {
	    	 cur.add(root.val) ;
	    	 rst.add(new ArrayList<Integer> (cur));
	    	 cur.remove(cur.size() - 1) ;
	    	 return ;
	     }
	     cur.add(root.val) ;
	     helper (root.left, target - root.val, cur, rst);
	     helper (root.right, target - root.val, cur, rst);
	     cur.remove(cur.size() - 1) ;

}

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

C++11:

#include<iostream>
#include<string>

struct Node {
    int val;
    Node *l; 
    Node *r; 
};

struct Tree {
    Node *root;

    Tree() {
        Node *n =new Node();
        n->val = 20; 
        Node *n1 = new Node(); n1->val = 4;
        Node *n2 = new Node() ; n2->val = 5;
        n->l = n1; n->r = n2; 

        Node *n11 = new Node() ; n11->val = 8;
        Node *n12 = new Node() ; n12->val = 2;
        n1->l = n11; n1->r = n12;

        root = n;
    }   

    std::string get_path(int sum) {
        return get_path(sum, root);
    }   

    std::string get_path(int sum, Node *n) {
        if (n == NULL){
            return ""; 
        }   
        if ((sum  - n->val) == 0 ) { 
            return std::to_string(n->val) ;
        }   
        std::string sl = get_path(sum - n->val, n->l);
        if (sl.size()) {
            return std::to_string(n->val) + "-" + sl; 
        }   
        std::string sr = get_path(sum - n->val, n->r);
        if (sl.size()) {
            return std::to_string(n->val) +"-" + sr; 
        }   
        return ""; 
    }   
};
int main() {
    std::cout << Tree().get_path(32) << "\n";
}

$ ./a.out 
20-4-8

- lalit.kumar.bhasin July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it only natural integers? If so, the tree could be pruned for efficiency. Otherwise, every path must be searched until a sum is found using depth-first search: O(|V|+|E|)

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

LinkedList<

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

LinkedList<Node> GetPath (Node N, int original, int prev_sum, LinkedList<Node> LL){
	if (N == null)
		return null;

	prev_sum += N.data;
	
	if (N.left == null && N.right == null && prev_sum == original) {
		LL.add(N);
		return LL;
	} else if (N.left == null && N.right == null) {
		return null;
	}
		
	LL.add(N);
	Node left = GetPath(N.left, original, prev_sum, LL);
	Node right = GetPath(N.right, original, prev_sum, LL);

	if (left == null && right == null){
		LL.remove(N);	
		return null;
	}

	return LL;
}

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

This is a pretty simple problem.

Algorithm
Recusrively reduce the sum from current node value and check both left & right tree if there is a path with Subsum ( current node value - sum)

hasPathSum(Node root, int sum){
   if(root == null)
        return (root.data == sum);

   int subSum =  sum - root.data;
   return (hasPathSum(root.left, subSum) || hasPathSum(root.right, subSum));
}

- ram.prasad.prabu July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is wrong statement

if(root == null)
        return (root.data == sum);

- ash.taunk3 July 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem asks us to return the path with the given sum and not a boolean value which says whether or not a path exists with the given sum

- Anonymous September 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby impl. Assumption: tree contains only natural numbers. Hence, the tree can be pruned if the sum is exceeded. Algo is depth-first search: O(|V|+|E|)

require 'tree'

root_node = Tree::TreeNode.new("1", 1)
child1 = Tree::TreeNode.new("2",2)
child2 = Tree::TreeNode.new("3",3)
grandchild1=Tree::TreeNode.new("4",4)
grandchild2=Tree::TreeNode.new("5",5)
grandchild3=Tree::TreeNode.new("6",6)
grandchild4=Tree::TreeNode.new("7",7)
child1 << grandchild1
child1 << grandchild2
child2 << grandchild3
child2 << grandchild4
root_node << child1
root_node << child2
root_node.print_tree

def find_path_sum(node, accumulator, target_sum,path)
  return false if node.nil? || node.content.to_i + accumulator > target_sum
  
  if node.content.to_i + accumulator == target_sum
    path << node
    return true
  end

  node.children.any? do |child|
    find_path_sum(child,accumulator+node.content.to_i,target_sum,path) && path<<node
  end
end


path=[]
find_path_sum(root_node,0,10,path)

puts

puts "No path" if path.length==0

path.each_with_index do |node,index|
  print "#{path[path.length-1-index].name.to_i}"
  
  print ' -> ' if index < path.length-1
end

Output:
* 1
|---+ 2
| |---> 4
| +---> 5
+---+ 3
|---> 6
+---> 7

1 -> 3 -> 6

- Yev July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

* 1
|---+ 2
|    |---> 4
|    +---> 5
+---+ 3
    |---> 6
    +---> 7

1 -> 3 -> 6

- Yev July 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class demo{
public static void main(String[] args){

System.out.println("Welcome to Careercup.com ");
}




}

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

Comparing with normal tree traversal via BFS and DFS. The only thing need to do for this problem is to take push the sum (from root to its parent node) into the stack or queue. As traversing through the tree, compare this sum plus its own value against the given SUM. If equal, then found a path. Otherwise no.

Here is the implementation: cpluspluslearning-petert.blogspot.co.uk/2015/07/data-structure-and-algorithm-find-tree.html

- peter tang July 21, 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