Closest Common Ancestor of a Node in a Tree
You have a tree data structure. Write an algorithm that given any two nodes in the tree, finds the node that is the closest common ancestor to them.
You 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.
- Completeness of the 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%)
This is a basic data transformation problem. The key insight is when the interviewee realizes that transforming the problem is important.
- Weak candidates start from one node, and try all sorts of weird ways to go up the tree and then turn around.
- Intermediate candidates start from both nodes at the same time, go up the tree while tracking visited nodes, and stop when one path intercepts the other.
- Very strong candidates see the path from each given node to the root of the tree as a stack. Build the stack starting from one node all the way to the root. Do the same with the other node. Now you have two stacks with the root node on top of both. Start popping as long as the top (peek) of the stacks are the same. As soon as they're not, the last common node that you popped off the stack is the closest common ancestor.
Ron Logan asked me this question in my interview with Microsoft
Breadth First Tree Traversal
Write an algorithm that takes a tree data structure and writes out all the elements in a breadth-first traversal order.
Given a tree, prune it to select for only a certain node color
Given that a tree is made of only red or black nodes, return another tree that only has the paths of the original tree leading to a red node.
Google search results for the top 1000 highest ranking URLs
You have trillions of URLs stored uniquely, without order, across numerous machines, each with a score. Find the 1000 URLs with the highest scores.
Calculate your Social Graph Klout Score
Write the algorithm that LinkedIn.com uses to tell you how many professionals you have access to.
- Amin Ariana
- July 2009