Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Complexity O(log(n)) assume tree is balanced. O(n) worst case.
Roll up from node to root, use a stack to remember all nodes in the path. Do this for both nodes. Drill down the following way: For the two stacks, peek the current heads. If different, root is the common ancestor. Otherwise pop the heads for both stacks and peek the heads. Repeat until the two heads in two stacks are different (including null vs something). The last pop up node is the common ancestor.
import scala.collection.mutable.Stack
object CommonAncestor extends App {
case class Node(key:String, children:Node*) {
var parent:Option[Node]=None
children.foreach(_.parent=Some(this))
}
def ancestor(n1:Node, n2:Node) = {
var s1 = Stack.empty[Option[Node]]
var s2 = Stack.empty[Option[Node]]
var n = n1.parent
while (n!=None) { s1.push(n); n=n.get.parent }
n = n2.parent
while (n!=None) { s2.push(n); n=n.get.parent }
while (!s1.isEmpty && !s2.isEmpty && s1.head==s2.head) {
n=s1.pop
n=s2.pop
}
n
}
val g = Node("G")
val f = Node("F")
val m = Node("M")
val d = Node("D", g, f)
val e = Node("E")
val b = Node("B", d, e)
val c = Node("C", m)
val a = Node("A", b, c)
var anc = ancestor(d,f)
println(anc match { case None=>"None" case _=>anc.get.key})
anc =
println(ancestor(c,g) match { case None=>"None" case anc:Some[Node[String]]=>anc.get.key})
}
There re multiple ways of doing that:
First way: Modify the Class Node and use DFS
class Node {
Node left;
Node right;
object data;
int inRoot; //represents the number of times the node is in root of a searched value
}
Node GetLCP(Node root, object val1, object val2)
{
//Handle special case
if(root == null)
return null;
//Clear inRoot value using any traversal technique
ClearInRoot(root); //Unimplemented here
if(SearchValue(root, val1) && SearchValue(root, val2))
{
//Traverse from root as long as inRoot == 2 then return the point of separation
Node current = root;
while(current != null)
{
if(current.left != null && current.inRoot == current.left.inRoot)
{
current = current.left;
}
else if(current.right != null && current.inRoot == current.right.inRoot)
{
current = current.right;
}
else //Found a separation point or reached one of the values
{
return current;
}
}
}
//One of the values doesn't exist in the tree, return null;
return null;
}
bool SearchValue(Node treeNode, object val)
{
if(treeNode == null)
return false;
if(treeNode.data == val)
{
treeNode.inRoot++;
return true;
}
if(SearchValue(treeNode.left) || SearchValue(treeNode.right))
{
treeNode.inRoot++;
return true;
}
return false;
}
A second technique, would be to get an array of all the nodes on the path to Val1 and another array of all the nodes on the path to Val2 and trace both arrays, as long as the elements are matching keep going, till either array is finished or you reach a non matching point
Using simple loop - log(n) operations
TreeNode LowestCommonAncestorLoop(TreeNode currentNode, int Node1Value, int Node2Value)
{
while (currentNode != null)
{
// Move to the left subtree if the given values are less than current node's value.
if (Node1Value < currentNode.NodeValue && Node2Value < currentNode.NodeValue)
{
currentNode = currentNode.LeftNode;
}
// Move to right subtree if the given values are greater than current node's value.
else if (Node1Value > currentNode.NodeValue && Node2Value > currentNode.NodeValue)
{
currentNode = currentNode.RightNode;
}
else
{
// We have found the common ancestor.
break;
}
}
return currentNode;
}
private Node insert(Node node, int data,int pos,Node ances) {
if (node==null) {
node = new Node(data,pos);
node.ancestor=ances;
}
else {
if (data <= node.data) {
node.left = insert(node.left, data,getPosition(node.pos),node);
}
else {
node.right = insert(node.right, data,getPosition(node.pos),node);
}
}
return(node); // in any case, return the new pointer to the caller
}
public int getCommonAncestor(int a,int b)
{
Node tempA=root;
Node tempB=root;
while(true)
{
if(tempA.data<a)
tempA=tempA.right;
else if(tempA.data>a)
tempA=tempA.left;
else
return -1;
if(tempB.data<b)
tempB=tempB.right;
else if(tempB.data>b)
tempB=tempB.left;
else
return -1;
if(tempA.data!=tempB.data)
return tempA.ancestor.data;
}
}
private void traverseToRoot(List<Node> path, Node node){
for(; node != null; node = node.parent){
path.add(node);
}
}
public Node commonAncestor(Node nodeOne, Node nodeTwo)
{
if(nodeOne == null || nodeTwo == null) return null;
if(nodeOne == nodeTwo) return nodeOne;
List<Node> pathOfOne = new ArrayList<Node>();
traverseToRoot(pathOfOne, nodeOne);//get nodeOne's path from root
List<Node> pathOfTwo = new ArrayList<Node>();
traverseToRoot(pathOfTwo, nodeTwo);//get nodeTwo's path from root
if(pathOfOne.size() > pathOfTwo.size(){//swap to make pathOfTwo longer
List<Node> tmp = pathOfOne;
pathOfOne = pathOfTwo;
pathOfTwo = tmp;
};
for(int i = 0, j = pathOfTwo.size() - pathOfOne.size(); i < pathOfOne.size(); ++i, ++j){
if(pathOfOne.get(i) == pathOfTwo.get(j)) return pathOfOne.get(i);
}
//if reaching here, it means nodeOne and nodeTwo are in different trees
return null;
}
class FirstCommonAncestorImp implements FirstCommonAncestor {
@Override
public Node commonAncestor(Node nodeOne, Node nodeTwo) {
Stack<Node> nodeOneStack = new Stack<Node>();
Stack<Node> nodeTwoStack = new Stack<Node>();
getNodes(nodeOne,nodeOneStack);
getNodes(nodeOne,nodeTwoStack);
Node commonAncestor = null ;
while (!nodeOneStack.isEmpty() && !nodeTwoStack.isEmpty()){
Node one = nodeOneStack.pop();
Node two = nodeTwoStack.pop();
if (one == two){
commonAncestor = one ;
}
}
return commonAncestor;
}
public void getNodes(Node node, Stack<Node> stack){
if (!node.isRoot()){
stack.push(node);
getNodes(node.parent, stack);
}else{
stack.push(node);
}
}
}
Best way to start from root and check both node available in subTree. Then mode to Left child and check same Otherwise move to right child and check same. Otherwise root is Deepest Ancestor. Algorithm:
DeepestAncestor = Root
DeepestAncestor = Root.Left => Verify that both Node is SubChild of This. If Yes, move forward and forget Right Child
Otherwise
DeepestAncestor = Root.Right => Verify that both Node is SubChild of This. If Yes, move forward and forget Left Child
If both Left and Right child DONT have both nodes as subchild then RETURN DeepestAncestor. Parent ....
public class findAncestor implements FirstCommonAncestor{
public Node commonAncestor(Node one, Node two){
///
int depth1 = findDepth(one);
int depth2 = findDepth(two);
///
if(one == null || two == null){
return null;
}else if(one.isRoot){
return one;
else if (two.isRoot){
return two;
}
return findCommonAncestor(one, two,depth1,depth2);
}
public findCommonAncestor(Node one,Node two,int depth1, int depth2);
if (depth1 == depth2){
if(one.parent == two.parent){
return one.parent;
}else
return one.parent.parent;
}
else if (depth1 > depth2){
one = one.parent;
findCommonAncestor( one, two, depth1 - 1, depth2);
}else
two = two.parent
findCommonAncestor( one, two,int depth1, depth2 - 1);
}
}
public int findDepth(node n){
if(n.isRoot){
return 0;
}
return 1 + depth(root.parent);
}
Why not modify the nodes to maintain a int visited. While bouncing between the two nodes, walk toward the root setting the visited flag to the current visited value. If you see the same visited flag and the node you see it on is not one of the two starting nodes you have your nearest common ancestor.
PS for those of you out there who say, well what about multiple threads walking the tree at the same time...ThreadLocal<Integer> visited will work just fine for this bad boy
I think this problem warrants mentioning of some existing literature. Commonly, this problem is known as the Lowest Common Ancestor (LCA) and has been shown to be solvable in O(1) after a preparation of just O(N), where N is the number of nodes in the tree. Dov Harel and Robert Tarjan were the first to develop an optimal solution. Check out the Wikipedia page on it. More reading on this is definitely recommended, since it can be reduced into a Range Minimum Query (RMQ) in linear time and a Sparse Table algorithm can be applied efficiently.
I'm not sure if it's good that on this site people just tend to throw code around. I think I would give a candidate quite a few bonus points if they knew their algorithm theory well enough to cite the history of that problem.
I also appreciate how amazing this realization is to me. Imagine a genealogy graph. No matter how big that graph, we will be able to tell you with no increase in delay at all (assuming we are done with the pre-processing) who any two people on this planet share an ancestor with! Think about that ... or don't. I imagine companies such as LinkedIn and Facebook working quite a bit with graph structures (mine does, too), so showing some excitement for that fact is something I would really value about a candidate.
Anyway, without further ado and without further excitement, again a recursive definition for the solution of this problem: in order for a node in a binary tree/sub-tree to be the lowest common ancestor of two nodes N1 and N2, both of its sub-trees need to contain either of the nodes. If a single sub-tree contains both nodes N1 and N2, the lowest common ancestor should be the lowest common ancestor of N1 and N2 in the sub-tree that contains them.
Translating this formulation directly into code gives us the following:
static Node FindLowestCommonAncestor(Node n, int n1, int n2)
{
if (n == null) return null;
if (n.Value == n1 || n.Value == n2) return n;
Node left = FindLowestCommonAncestor(n.Left, n1, n2);
Node right = FindLowestCommonAncestor(n.Right, n1, n2);
if (left == null && right == null) return null;
if (left != null && right != null) return n;
if (left != null) return left;
if (right != null) return right;
return null;
}
No, this solution does not support queries in constant time, but requires coding effort of constant time and will usually satisfy an interviewer. :) I said "satisfy", not blow away. I would be blown away if a candidate could implement the original algorithm of 1984 in the space of a phone interview and I would be impressed if someone would use RMQ and Sparse Tables and code that cleanly.
Impressive explanation! I learned how to convert LCA to RMQ and solve RMQ in O(n) time from my data structure class. But totally forgot how to implement it in detail. It is so demanding to implement it in a phone interview (for me).
There are two problems that I think are there in the code.
1. Using above example, your code would return D as the deepest common ancestor, while tis the parent of D, that is B, which should be returned as the DCA, unless the question fails to mention that a node can be ancestor of itself too.
2. Your code would fail if either one or both nodes are not in the tree. This can be ignored if we already know that both nodes are in the tree.
// time complexity: o(log n)
public class Solution implements FirstCommonAncestor {
private boolean findNode(Node parent,Node find)
{
if(parent==find)
return true;
if(parent.left==find)
return true;
else if(parent.right==find)
return true;
else
return( findNode(parent.right,find)|| findNode(parent.left,find));
}
@override
private Node commonAncestor(Node one, Node two){
if(one==null || two==null)
return null;
if(one==two)
return one;
if(two.parent==one.parent)
return one.parent;
if(two.parent==one)
return one;
if(one.parent==two)
return two;
Node temp=one;
while(!find(temp,two))
{
temp=temp.parent;
}
return temp;
}
}
and
public class FirstCommonAncestor {
/**
* Given two nodes of a tree,
* method should return the deepest common ancestor of those nodes.
*
* A
* / \
* B C
* / \ \
* D E M
* / \
* G F
*
* commonAncestor(D, F) = B
* commonAncestor(C, G) = A
*/
public static class Node {
final Node parent;
//final Node left;
//final Node right;
final int data;
/*public Node(Node parent, Node left, Node right, int data) {
this.parent = parent;
this.left = left;
this.right = right;
this.data = data;
} */
public Node(Node parent, int data){
this.parent = parent;
this.data = data;
}
boolean isRoot() {
return parent == null;
}
}
public static int findDepth(Node n){
if(n.isRoot()){
return 0;
}
return findDepth(n.parent)+1;
}
public static Node commonAncestor(Node nodeOne, Node nodeTwo)
{
int nodeOneDepth = findDepth(nodeOne);
int nodeTwoDepth = findDepth(nodeTwo);
while(nodeOneDepth > 0 && nodeTwoDepth > 0){
if(nodeOneDepth > nodeTwoDepth){
nodeOne = nodeOne.parent;
nodeOneDepth--;
}
else if(nodeOneDepth < nodeTwoDepth){
nodeTwo = nodeTwo.parent;
nodeTwoDepth--;
}
else{
if(nodeOne.parent == nodeTwo.parent){
return nodeOne.parent;
}
nodeOne = nodeOne.parent;
nodeTwo = nodeTwo.parent;
nodeOneDepth--;
nodeTwoDepth--;
}
}
return null;
}
public static void main(String[] args){
Node node1 = new Node(null, 1);
Node node2 = new Node(node1, 2);
Node node3 = new Node(node1, 3);
Node node4 = new Node(node2, 4);
Node node5 = new Node(node2, 5);
Node node6 = new Node(node3, 6);
Node node7 = new Node(node3, 7);
Node node8 = new Node(node4, 8);
Node node9 = new Node(node4, 9);
Node commonAnce = commonAncestor(node4, node8);
System.out.println(commonAnce.data);
}
}
and
public class FirstCommonAncestor {
/**
* Given two nodes of a tree,
* method should return the deepest common ancestor of those nodes.
*
* A
* / \
* B C
* / \ \
* D E M
* / \
* G F
*
* commonAncestor(D, F) = B
* commonAncestor(C, G) = A
*/
public static class Node {
final Node parent;
//final Node left;
//final Node right;
final int data;
/*public Node(Node parent, Node left, Node right, int data) {
this.parent = parent;
this.left = left;
this.right = right;
this.data = data;
} */
public Node(Node parent, int data){
this.parent = parent;
this.data = data;
}
boolean isRoot() {
return parent == null;
}
}
public static int findDepth(Node n){
if(n.isRoot()){
return 0;
}
return findDepth(n.parent)+1;
}
public static Node commonAncestor(Node nodeOne, Node nodeTwo)
{
int nodeOneDepth = findDepth(nodeOne);
int nodeTwoDepth = findDepth(nodeTwo);
while(nodeOneDepth > 0 && nodeTwoDepth > 0){
if(nodeOneDepth > nodeTwoDepth){
nodeOne = nodeOne.parent;
nodeOneDepth--;
}
else if(nodeOneDepth < nodeTwoDepth){
nodeTwo = nodeTwo.parent;
nodeTwoDepth--;
}
else{
if(nodeOne.parent == nodeTwo.parent){
return nodeOne.parent;
}
nodeOne = nodeOne.parent;
nodeTwo = nodeTwo.parent;
nodeOneDepth--;
nodeTwoDepth--;
}
}
return null;
}
public static void main(String[] args){
Node node1 = new Node(null, 1);
Node node2 = new Node(node1, 2);
Node node3 = new Node(node1, 3);
Node node4 = new Node(node2, 4);
Node node5 = new Node(node2, 5);
Node node6 = new Node(node3, 6);
Node node7 = new Node(node3, 7);
Node node8 = new Node(node4, 8);
Node node9 = new Node(node4, 9);
Node commonAnce = commonAncestor(node4, node8);
System.out.println(commonAnce.data);
}
}
Please review my code and provide some feedback.
public static Node commonAncestor(Node nodeOne, Node nodeTwo){
if(nodeOne==null || nodeTwo==null)
return null;
if(nodeOne == nodeTwo) {
return nodeOne;
}
Set<CNode> parent1 = new HashSet<CNode>();
while(nodeOne.parent != null && nodeTwo.parent != null && !nodeOne.isRoot() && !nodeTwo.isRoot()) {
parent1.add(nodeOne.parent);
if(parent1.contains(nodeTwo.parent)) {
return nodeTwo.parent;
}
nodeTwo = nodeTwo.parent;
nodeOne = nodeOne.parent;
}
return nodeOne;
}
Please review my code and provide feedback.
public static CNode commonAncestor(CNode nodeOne, CNode nodeTwo){
if(nodeOne==null || nodeTwo==null)
return null;
if(nodeOne == nodeTwo) {
return nodeOne;
}
Set<CNode> parent1 = new HashSet<CNode>();
while(nodeOne.parent != null && nodeTwo.parent != null && !nodeOne.isRoot() && !nodeTwo.isRoot()) {
parent1.add(nodeOne.parent);
if(parent1.contains(nodeTwo.parent)) {
return nodeTwo.parent;
}
nodeTwo = nodeTwo.parent;
nodeOne = nodeOne.parent;
}
return nodeOne;
}
1) Go from node to root simultaneously and until you reach the root for any node while traversing.
2) While traversing, keep adding the parents to the list
3) While traversing, keep checking while other node parents set contains my current parent, if yes then current parent is the answer
4) If any node reaches to root node while traversing, we come out of while loop.
5) We do similar way for the node who has not reached till root and keep doing step 2 and 3.
This is similar to the merging of an array, but here we don't merge into single set.
- Abhishek Kothari May 12, 2014