Yahoo Interview Question
Software Engineer / DevelopersTeam: Yahoo Sports
Country: United States
Interview Type: In-Person
Approach: It is stated that node has child and parent properties. We can make use of parent property.
1. Start traversing from both the nodes using parent pointers'
2. For any one node, start pushing the nodes traveled in a hashtable. For another node traversal, keep check the node is present or not in hashtable. If node is present the found which is LCA of two nodes.
Probably have to work out the details where one traversal finishes before the other one but that can be easilly handled in the code.
If we want to avoid using any extra memory, we can treat this two list with one merging point. Which can be easily solved in O(h).
@Karthik is nailed it -- LCA problem. Greatly simplified LCA problem because we have a parent link. As such all that is necessary is:
- get depth of A (logN) by walking up
- get depth of B (logN) by walking up
- take deeper one and level with another one
- walk in parallel until they meet
We can achieve it using extra space O(P)
where P = size of path between A & B.
Algorithm:
1.Node a = A;
2.Node b = B;
3.Map<Node,Node> path = new HashMap<Node,Node>();
4.while(a.p != null && b.p != null && a != b){
if(!path.contains(a)){
path.put(a,a.p);
a = a.p;
}else if(!path.contains(b.p)){
path.put(b.p,b);
b = b.p;
}else{
return path;
}
}
//Map maintains elements in insertion order.
5.return path;
I do not think the above code will work. Can you please elaborate further ?
Please explain the following cases.
(i) B is a child of A
(ii) A and B are on the same side but one of the node is much deeper than the other.
It will be O(P) only when the nodes are on different sides of root.
Thanks a lot.
How about this (please let me know if this seems sound)
N1 = A
N2 = B
Hash H{} = null
Pathfound = false
CommonParent = null;
while patfound = false do
if N1.Parent is not null and N1.Parent exists in H then
PathFound = true;
CommonParent = N1.Parent
end If
H = H union N1.Parent
if N2.Parent is not null and N2.Parent exists in H then
PathFound = true;
CommonParent = N2.Parent
end If
H = H union N2.Parent
end while
Pseudo Code Desc:
Copy Node A,B to N1 and N2
Create empty Hash H
PathFound
We assume parent of root is null
Explanation:
Path = Node1 to Common Ancestor + Node2 to Common ancestor
We walk upward from both child nodes simultaneously. We check Both parents in a Hash first, and if not found we add the parent. Since we use hash table, we can assume checking and adding both parents can be done in constant time.
Ideal Case: both nodes are at a distance of 1 from a common ancestor
Will befound out in 1 step
Worst Case: One is the root and other is farthest leaf, will take P steps
Other Avg cases: One is a close node, other is a deep seeded node, will take less than P steps as Common Ancestor will come before P steps or exactly P steps if one is parent of other
In the end we will have common ancestor node. We traverse from each node to common ancestor (total of P steps again and find the path by traversing one of the paths from node to ancestor, the other in reverse)
This takes : P steps for finding ancestor, P steps to construct path from both nodes to ancestor, and P steps to traverse path. So 3P steps or O(P) when simplified.
This is same as finding Least Common Ancestor for A and B.
- Karthik January 20, 2014