Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
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]<<" ";
}
}
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) ;
}
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
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;
}
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));
}
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
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
- Himanshu July 06, 2015