Amazon Interview Question Software Engineer / Developers
Country: India
Brute force:
Convert tree to adjacency list representation (or assume tree also has a parent pointer), and have a boolean flag associated with each node.
For each node, do a depth first search, printing all paths which sum to given number. Set the boolean flag for the node you started the dfs from.
Boolean flag is used to not print a path which has already been printed (i.e. if you end up at a node n, and n's flag is true, you don't print the path).
Potentially O(n^3), but I suppose printing Omega(n^2) paths, each with possible Omega(n) length, will make it Omega(n^3) anyway...
Let’s approach this problem by simplifying it. What if the path had to start at the root? In that
case, we would have a much easier problem:
Start from the root and branch left and right, computing the sum thus far on each path.
When we find the sum, we print the current path. Note that we don’t stop just because
we found the sum. Why? Because we could have the following path (assume we are
looking for the sum 5): 2 + 3 + –4 + 3 + 1 + 2. If we stopped once we hit 2 + 3, we’d miss
several paths (2 + 3 + -4 + 3 + 1 and 3 + -4 + 3 + 1 + 2). So, we keep going along every
possible path.
Now, what if the path can start anywhere? In that case, we make a small modification. On
every node, we look “up” to see if we’ve found the sum. That is—rather than asking “does
this node start a path with the sum?,” we ask “does this node complete a path with the sum?”
void findSum(TreeNode head, int sum, ArrayList<Integer> buffer,
int level) {
if (head == null) return;
int tmp = sum;
buffer.add(head.data);
for (int i = level;i >- 1; i--){
tmp -= buffer.get(i);
if (tmp == 0) print(buffer, i, level);
}
ArrayList<Integer> c1 = (ArrayList<Integer>) buffer.clone();
ArrayList<Integer> c2 = (ArrayList<Integer>) buffer.clone();
findSum(head.left, sum, c1, level + 1);
findSum(head.right, sum, c2, level + 1);
}
void print(ArrayList<Integer> buffer, int level, int i2) {
for (int i = level; i <= i2; i++) {
System.out.print(buffer.get(i) + “ ”);
}
System.out.println();
}
What is the time complexity of this algorithm? Well, if a node is at level r, we do r amount
of work (that’s in the looking “up” step). We can take a guess at O(n lg n) (n nodes, doing an
average of lg n amount of work on each step), or we can be super mathematical:
There are 2^r nodes at level r.
1*2^1 + 2*2^2 + 3*2^3 + 4*2^4 + ... d * 2^d
= sum(r * 2^r, r from 0 to depth)
= 2 (d-1) * 2^d + 2
n = 2^d ==> d = lg n
NOTE: 2^lg(x) = x
O(2 (lg n - 1) * 2^(lg n) + 2) = O(2 (lg n - 1) * n ) = O(n lg n)
Following similar logic, our space complexity is O(n lg n).
This seems wrong.
You get O(nlog n), while there are potentially n^2 paths!
Example: A completely balanced tree, all values 1, and you are looking for paths which sum to 2h, where h is height of the tree. Every leaf node in left subtree can be paired with every leaf node in the right, giving n^2/4 paths.
i am not telling you the number of path's , i am explaining you how to get all paths with in O(nlogn) time . and simply using a count variable initially initialized value with 0 will work fine and later you can increment on every printed path .. :)
@abhishek: If you are enumerating each path, and there are n^2/4 paths, how can your algorithm be O(n log n)?
i hope these lines are gud enough to explain what r u looking for and pls go through all the language and code which i have given ..
What is the time complexity of this algorithm? Well, if a node is at level r, we do r amount
of work (that’s in the looking “up” step). We can take a guess at O(n lg n) (n nodes, doing an
average of lg n amount of work on each step), or we can be super mathematical:
There are 2^r nodes at level r.
1*2^1 + 2*2^2 + 3*2^3 + 4*2^4 + ... d * 2^d
Don't care.
If the problem requires you to print n^2/4 paths, your algorithm, if correct, cannot possibly be O(nlog n).
How hard is it for you to understand that?
This solution which is directly copy-pasted from the CareerCup book does not fit this problem. This solution computes path top-down fashion where each element belong to the next increasing/decreasing levels i.e. 5,6,1 or 5,7 or 6,2 in this case. But here we need to consider zig-zag paths such as 1,6,2 where 1 and 2 are siblings and in the same level. The above solution will not work in this case.
abhishek27.kumar: sorry but you just failed to have a good look at the problem, like Anon said, the copy-paste answer from book can only cover all the 'top-down' style paths, but can't do nothing about the 'zig-zag' style paths.
As the Anonymous guy keep telling you O(n^2), he is actually talking about the lower bound of that algorithm, thus it should be Omega(n^2), that means, you can't do better than Omega(n^2). That's the minimum time to enumerate out *ALL POSSIBLE* paths in the tree, which you will be needing for examining the sum value of each path.
I guess working with BFS logic will work, whenever we take any node(say root) just look at the adjacency matrix of it. First make a check whether the sum is less than the node value. If not take any node from its adj. matrix and sum it up and note the predessor of this node, however, instead of maintaining single predessor lets take an array of ancestor which will give us the node path equivalent to the sum. So, I guess total time complexity will be O(E+V), where E is number of edges and V is number of vertices.
I think the problem is hard and tricky because we see the words binary search tree
and we think the solution should be neat, and recursive....blah blah. well the name
of the data structure is there to trick you. The properties of the binary tree are not of
help. The correct algorithm is DFS ( from every node) as you would do in any graph
( that's right, forget it's a binary search tree and assume it's just a simple graph or
network). I am still looking for a way to optimize the DFS algorithm for this problem
( so that it doesnt explore the same path twice , in reverse order) but besides that,
it's the right tool for the job. what do you think??
Apply the Floyd Warshall to find all pair shortest path and use optimal matrix for path reconstruction. Since this is a tree so there is just one and only path between 2 nodes. Print path for all the nodes that are at a distance K apart.
- Epic_coder September 29, 2012