posted Jan 3, 2011 1:13 PM by Amin Ariana
[
updated Nov 30, 2011 3:30 PM
]
Tags: Moderate, data structure transformation Problem descriptionYou have a tree data structure. The ancestors of a given node are defined to be the node itself, its direct parent, or the ancestors of the parent node. The root node has no parent and is its own only ancestor. Write an algorithm that takes any two nodes and gives their closest common ancestor.
Grading- Completeness of the C# or pseudo-code algorithm (25%)
- Correctness of the algorithm, demonstrated by quick manual unit tests (25%)
- What is the time and space complexity of your algorithm? (25%)
- Is the most efficient solution, O (lg n), offered? (25%)
Source codeC# public interface Node
{
Node Parent { get; }
}
public static Node GetLeastCommonAncestor(Node a, Node b)
{
Stack<Node> aStack = GetStack(a);
Stack<Node> bStack = GetStack(b);
while (aStack.Count > 0 && bStack.Count > 0 && aStack.Pop() == bStack.Peek())
zipper = bStack.Pop();
return zipper;
}
private static Stack<Node> GetStack(Node me)
{
Stack<Node> stack = new Stack<Node>();
while (me != null)
{
stack.Push(me);
me = me.Parent;
}
return stack;
}
ReferencesRon Logan asked me this question in my interview with Microsoft. |
|
