Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
4
of 4 vote

Interviewer gave me a hint: it's better to consider the case when n1 and n2 lays on the same level of tree (in my example b, c, h lays on same level of trees)

Case 1.
Let's assume that n1 and n2 lays on the same level.
In this case we can just go up over the tree simultaneously.
Then we face situation when n1 == n2 we done.

Case 2.
1) We need to count level for both nodes.
2) Align levels by following parent on node with higher level.
3) Do Case 1 solution.

int node_level(Node* node) {
    int level = 0;
    while (node->parent != NULL) {
        node = node->parent;
        level++;
    }
}

Node* closest_common_ancestor(Node* n1, Node* n2) {
    n1level = node_level(n1);
    n2level = node_level(n2);

    while (n1level < n2level) {
        n2 = n2->parent;
        n2level--;
    }
    
    while (n1level > n2level) {
        n1 = n1->parent;
        n1level--;
    }

    // in different tree situation we stop at 
    // n1 == n2 == NULL and it's still a correct result
    while (n1 != n2) {
        n1 = n1->parent;
        n2 = n2->parent;
    }
    
    return n1;
}

- Sergey January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The nodes on different levels is a trippy case...my code broke on this test case. Thanks for the hint.

- smallchallenges January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ah, great. I used the heights, but didn't think to skip up the extra height on the longer branch. Then it's simple

- fungled January 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution. Couple notes in node_level function though:
- Should check if node is NULL before looping (so you don't dereference a NULL pointer on the first iteration of the loop)
- Need to add "return level;" at the end

- Nick March 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Node closetCommonAncestors(Node first, Node second) {
		int h1 = getHeight(first);
		int h2 = getHeight(first);
		
		
		//go to same LEVEL!!
		while (h1 < h2) {
			second = second.parent;
			h2--;
		}
		while (h2 < h1) {
			first = first.parent;
			h1--;
		}
		while(!first.equals(second)) {
			first = first.parent;
			second = second.parent;
		}
		return first;
		

	}
	int getHeight(Node p) {
		int height = 0;
		while (p != null) {
			height ++;
			p = p.parent;
		}
		return height;
	}

- jnk8843 March 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int getHeight(Node *p) {
  int height = 0;
  while (p) {
    height++;
    p = p->parent;
  }
  return height;
}
 
// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
  int h1 = getHeight(p);
  int h2 = getHeight(q);
  // swap both nodes in case p is deeper than q.
  if (h1 > h2) {
    swap(h1, h2);
    swap(p, q);
  }
  // invariant: h1 <= h2.
  int dh = h2 - h1;
  for (int h = 0; h < dh; h++)
    q = q->parent;
  while (p && q) {
    if (p == q) return p;
    p = p->parent;
    q = q->parent;
  }
  return NULL;  // p and q are not in the same tree
}

- xyz January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1) If nodes in different trees the answer is always NULL
2) Your solution seems like not optimal. Expected something like o(count of all nodes in all trees) e.g. O(log N) or O(sqrt N) etc

- Sergey January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't get your comment. His solution is the same as yours. It is just written in a bit different way.

- PP January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we just take one node, go up the tree and put each node to a hash table. Then take the other node and go up the tree starting from it, and at each node check if that node is in the hash table. The first node that can be found in the hash table is the closest common ancestor. Seems somewhat trivial, is there something wrong with this solution?

- Anonymous January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Look at the question: Constrains: O(1) additional memory

- gameboy1024 January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ohh i missed that one, that makes it more interesting

- Anonymous January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is to traverse the tree, There are two pointers p1 and p2 which hold the top most parent of given node value in sub tree. if p1 and p2 are equal, it means p1 node is least common ancestor.
Only one traversal is required to find LCA and takes O(1)
Code is given below :

static class Node<T> {
	
			public T data;
			public Node<T> left;
			public Node<T> right;
			public Node<T> parent;
			
			public Node(T data,Node<T> parent) {
				this.data=data;
				this.parent = parent;
			}
       }

	
	static Node<?> parent1,parent2,ancestor;
	
	static Node<?>[] forest;
	

	
	public static Node<?> closest_common_ancestor(Node<?> n1, Node<?> n2) {
	    
		for (Node<?> root : forest) {
			leastCommonAncestor(root, n1, n2);
			if(ancestor!=null){
				return ancestor;
			}
		}
		
		return null;
	}
	
	
	public static void leastCommonAncestor(Node<?> root
			,Node<?> n1,Node<?> n2){
		if(root==null || (parent1!=null && parent2!=null)){
			return;
		}
		if (root==n1) {
			parent1 = root;
		}
		if(root==n2){
			parent2 = root;
		}
		
		leastCommonAncestor(root.left, n1, n2);
		leastCommonAncestor(root.right, n1, n2);
		
		if(parent1==parent2){
			ancestor = parent1;
			return;
		}
		if(parent1==root){
			parent1=root.parent;
		}
		if(parent2==root){
			parent2 = root.parent;
		}
	}

- akshay January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

When I start coding I did not consider there was a parent attribute in the node. This might not be the best solution...

public Node commonAncestor(Node n1, Node n2) {
		return commonAncestorDFS(this, n1, n2).result;
	}
	
	private commonAncestorResult commonAncestorDFS(Node root, Node n1, Node n2) {
		if (root == null) return new commonAncestorResult(0, null);
		commonAncestorResult leftResult = commonAncestorDFS(root.left, n1, n2);
		commonAncestorResult rightResult = commonAncestorDFS(root.right, n1, n2);
		// Left/Right found both nodes, so direct return
		if (leftResult.result != null) return leftResult;
		if (rightResult.result != null) return rightResult;
		
		int state = leftResult.state + rightResult.state;
		if (state == 2) return new commonAncestorResult(state, root);
		if (root == n1 || root == n2) state++;
		if (state == 2) return new commonAncestorResult(state, root);
		return new commonAncestorResult(state, null);
	}
	
	private class commonAncestorResult {
		private final int state;
		private final Node result;
		
		private commonAncestorResult(int state, Node result) {
			this.state = state;
			this.result = result;
		}
	}
	public String toString() {
		return "" + content;
	}

- Anonymous January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node {
public:
	wchar_t c;
	Node* parent; // == null for root of tree
	Node* left;
	Node* right;
	Node(wchar_t c)
	{
		this->c = c;
	}
	void AddLeftChild(Node* left)
	{
		this->left = left;
		left->parent = this;
	}
	void AddRightChild(Node* right)
	{
		this->right = right;
		right->parent = this;
	}

};

Node* tree_forest[]; // array of pointers which points to roots of each tree respectively

Node* closest_common_ancestor(Node* n1, Node* n2) 
{
	Node* ccs = NULL;
		
	if (n1 == n2)
	{
		return n1;
	}
	else if (n1 != NULL && n1->parent == n2)
	{
		return n2;
	}
	else if (n2 != NULL && n2->parent == n1)
	{
		return n1;
	}
	else
	{	
		if (n1!=NULL)
			ccs = closest_common_ancestor(n1->parent, n2);
		if (ccs == NULL && n2 != NULL)
		{
			ccs = closest_common_ancestor(n1, n2->parent);
		}
	}

	return ccs;
}

void BuildTreeAndPrint()
{
	Node* a = new Node(L'a');
	Node* b = new Node(L'b');
	Node* c = new Node(L'c');
	Node* d = new Node(L'd');
	Node* e = new Node(L'e');
	Node* f = new Node(L'f');

	Node* j = new Node(L'j');
	Node* h = new Node(L'h');

	a->AddLeftChild(b);
	b->AddLeftChild(d);
	a->AddRightChild(c);
	c->AddLeftChild(e);
	c->AddRightChild(f);

	j->AddLeftChild(h);

	Node* ccs=closest_common_ancestor(e, d);
	wprintf(L"CCS of e and d is %c\n", ccs->c);

	ccs = closest_common_ancestor(e, f);
	wprintf(L"CCS of e and f is %c\n", ccs->c);

	ccs = closest_common_ancestor(e, c);
	wprintf(L"CCS of e and c is %c\n", ccs->c);

	ccs = closest_common_ancestor(h, d);
	wprintf(L"CCS of h and d is %c\n", ccs!=NULL ? ccs->c:L'0' );
}

Output:

CCS of e and d is a
CCS of e and f is c
CCS of e and c is c
CCS of h and d is 0

- SilentWaters January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Check if both nodes are in the same tree by going up the tree till reaching root and compare the root for n1 and the root for n2. If not the same - no common ancestor, return null.
2. Go up the tree from node n1 and break all the node->parent connections as you go up. Till you reach the root.
3. Go up the tree from node n2 and break all node->parent connections as you go up. Till you reach the "root"m a node that has no parent. Since for n1 we broke all parent connections, this node'll be the closes ansector.
4. If needed can go back down the tree from root to leaves and fix all the connections we broke.

- Anna January 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Couldn't try run it, so it might be not perfect... And I didn't implement 4.

Node* find_root(Node *n) {

	if(n == null) return n;
	
	Node* currentNode = n;
	while(currentNode->parent != null) {
		currentNode = currentNode->parent;
	}

	return currentNode;
}

Node* upAndBreak(Node *n) {
	if(n == null) return n;

	Node* prevNode = n;
	Node* currentNode = n->parent;
	while(currentNode != null) {
		prevNode->parent = null;
		currentNode = currentNode->parent;
	}

	return prevNode;

}

Node* closest_common_ancestor(Node* n1, Node* n2) {

	if((n1 == null) || (n2 == null)) return null;
	
	// find out if they are in the same tree
	Node *n1_root = findRoot(n1);
	Node *n2_root = findRoot(n2);

	if(n1_root != n2_root){
		return null;
	}

	
	//Go up a tree and break all the edges you used to go up
	upAndBreak(n1);
	Node *commonAncestor = upAndBreak(n2);

	return commonAnsector;
	 
}

- Anna January 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Clever solution! I like it

- fungled January 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Found this is a little weird to do. Obviously can be done very efficiently with some extra storage, so this is more of a procedural sort of task.

1. Traverse both nodes up to their roots, at the same time calculate the height of each branch.
2. If the roots are different we know that there's no ancestor, so return NULL
3. Otherwise the approach is to traverse up the tree at varying "rates", in a similar way to how loops in linked lists are found, to see if we encounter an ancestor deeper in the tree. We start by stepping one level at a time, but the step size of the deeper node then increases until we've exhausted all the possibilities.
4. If we didn't find a deeper ancestor then the root is the only shared ancestor.

Time O(h ^ 2)
Space O(1)

Node* closest_common_ancester(Node *n1, Node *n2)
{
	int n1Height = 1, n2Height = 1;
	Node *n1Root = n1, n2Root = n2;
	
	// find height and roots
	while (n1Root.parent) {
		n1Root = n1Root.parent;
		n1Height++;
	}
	while (n2Root.parent) {
		n2Root = n2Root.parent;
		n2Height++;		
	}
	
	// don't have same roots; bail early
	if(n1Root != n2Root) {
		return NULL;
	}
	
	Node *deepest, *other;
	int deepestHeight;
	
	if (n1Height >= n2Height) {
		deepest = n1;
		other = n2;
		deepestHeight = n1Height;
	} else {
		deepest = n2;
		other = n1;
		deepestHeight = n2Height;
	}

	for (int step = 1; step < deepestHeight; ++step) {
		Node *bigStep = deepest;
		Node *smallStep = other;
		
		while (bigStep.parent && smallStep.parent) {
			for (int i = 0; i < step; ++i) {
				bigStep = bigStep.parent;
			}
			smallStep = smallStep.parent;
			
			if(bigStep = smallStep) {
				return bigStep;
			}
		}
	}
	
	// root is only ancestor
	return n1Root;
}

- fungled January 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function Node(parent, left, right) {
	this.parent = parent;
	this.left = left;
	this.right = right; 
}

Node.prototype.getHeight = function() {
	var counter = 0,
		currNode = this;

	while (currNode.parent !== undefined) { //root is then depth 0
		currNode = currNode.parent;
		counter++;
	}

	return counter;
}

Node.prototype.getAncestor = function(height) {
	var node;
	while (height > 0) {
		node = this.parent;
		height--;
	}

	return node;
}

function closestCommonAncestor(n1, n2) {
	var d1 = n1.getHeight(),
		d2 = n2.getHeight(),
		delta = Math.abs(d1 - d2);

	if (delta > 0) {
		if (d1 < d2) {
			n2 = n2.getAncestor(delta);
		} else {
			n1 = n1.getAncestor(delta);
		}
	}

	while (n1 && n2) {
		if (n1 === n2) {
			return n1;
		}
		n1 = n1.getAncestor(1);
		n2 = n2.getAncestor(1);
	}

- shysta February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* Closest_common_ancestor(Node* n1 node* n2)
{
	node* root1, *root2;
	int d1 = distance_to_root(n1, &root1);
	int d2 = distance_to_root(n2 , &root2) ;
	if(root1 != root2)
		return NULL; 
	if(d1 > d2)
	{
		int i = 0;
		while(i < d2-d1	)
		{
			n1 = n1->parent;
			i++;
		}
	}
	else if(d2 > d1)
	{
		int i = 0;
		while(i < d2-d1)
		{
			n2 = n2->parent;
			i++; 
		}		
	}
	while(n1 != n2)	
	{
		if(n1 == n2)
			return n1; 
		else
		{
			n1 = n1->parent;
			n2 = n2->parent;
		} 
		
	}
}

- Anonymous March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python version
space: O(1)
time: O(log(h))

class Node:
  def __init__(self, name = "", left = None, right = None, parent = None):
    self.name = name
    self.left = left
    self.right = right
    self.parent = parent

tree_forest = []

def is_common(node, start):
  while (start != None):
    if (start.name == node.name):
      return True
    start = start.parent
  return False

def cca(node1, node2):
  tmp = node1
  while(tmp != None):
    if (is_common(tmp, node2)):
      print "CCA for " + node1.name + ", " + node2.name + " is: " + tmp.name
      return True
    tmp = tmp.parent
  print "NO CCA for " + node1.name + ", " + node2.name
  return None


d = Node("d")
e = Node("e")
f = Node("f")

c = Node("c", e, f)
e.parent = f.parent = c

b = Node("b", d)
d.parent = b

a = Node("a", b, c)
b.parent = c.parent = a

j = Node("j")
h = Node("h", j)
j.parent = h


cca(e, d)
cca(e, f)
cca(e, c)
cca(h, d)

- misterX April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the solution in c++.
Running time will be O( log n)

int get_depth(node * n)
{
  int d = 0;
  node *cur = n;
  while(cur)
  {
    cur = cur->parent;
    d++;
  }
  return d;
}

node * find_cca(node * l, node * r)
{
  int ld = get_depth(l);
  int rd = get_depth(r);
  node * lparent = l;
  node * rparent = r;
  while (lparent && rparent)
  {
    if (lparent->value == rparent->value)
      return lparent;
 
    if (ld >= rd)
    {
      lparent = lparent->parent;
      ld--;
    } else {
      rparent = rparent->parent;
      rd--;
    }
  }
  return 0;
}

- hankm2004 July 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my Java implementation.

Since we have a parent attribute we can compare the path to root node and find the colsest ancestor between 2 nodes instead of a recursive solution. There are 2 createTree() methods to test with different trees.

import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Solution {
  static Node[] treeForest;
  int level = 0;
  static List<Node> pathToRoot1;
  static List<Node> pathToRoot2;
  
  
  public static void main(String[] args) {
    
    //createTree1();
    createTree2();
    
    Node ancestor = findClosestAncestor(treeForest[7],treeForest[1]);
    
    if (ancestor != null){
      System.out.println("closest ancestor is: " + ancestor.data);  
    }else{
      System.out.println("there is no common ancestor");
    }
    
    
    
  }
  
  public static void createTree(){
    Node nodeA = new Node("a");
    Node nodeB = new Node("b");
    Node nodeC = new Node("c");
    Node nodeD = new Node("d");
    Node nodeE = new Node("e");
    Node nodeF = new Node("f");
    Node nodeJ = new Node("j");
    Node nodeH = new Node("h");
    
    nodeA.left = nodeB;
    nodeA.right = nodeC;
    nodeB.left = nodeD;
    nodeB.parent = nodeA;
    nodeC.left = nodeE;
    nodeC.parent = nodeA;
    nodeC.right = nodeF;
    nodeD.parent = nodeB;
    nodeE.parent = nodeC;
    nodeF.parent = nodeC;
    nodeH.parent = nodeJ;
    
    treeForest = new Node[8];
    treeForest[0] = nodeA;
    treeForest[1] = nodeB;
    treeForest[2] = nodeC;
    treeForest[3] = nodeD;
    treeForest[4] = nodeE;
    treeForest[5] = nodeF;
    treeForest[6] = nodeJ;
    treeForest[7] = nodeH;
    
  }
  
  public static void createTree2(){
    Node node1 = new Node("1");
    Node node2 = new Node("2");
    Node node3 = new Node("3");
    Node node4 = new Node("4");
    Node node5 = new Node("5");
    Node node6 = new Node("6");
    Node node7 = new Node("7");
    Node node8 = new Node("8");
    Node node9 = new Node("9");
    
    node1.parent = null;
    node1.left = node2;
    node1.right = node3;
    
    node2.parent = node1;
    node2.left = node4;
    node2.right = node5;
    
    node3.parent = node1;
    node3.left = node6;
    node3.right = node7;
    
    node4.parent = node2;
    node4.left = node8;
    node4.right = node9;
    
    node5.parent = node2;
    node5.left = null;
    node5.right = null;
    
    node6.parent = node3;
    node6.left = null;
    node6.right = null;
    
    node7.parent = node3;
    node7.left = null;
    node7.right = null;
    
    node8.parent = node4;
    node8.left = null;
    node8.right = null;
    
    node9.parent = node4;
    node9.left = null;
    node9.right = null;
    
    treeForest = new Node[9];
    treeForest[0] = node1;
    treeForest[1] = node2;
    treeForest[2] = node3;
    treeForest[3] = node4;
    treeForest[4] = node5;
    treeForest[5] = node6;
    treeForest[6] = node7;
    treeForest[7] = node8;
    treeForest[8] = node9;
    
  }
  
  public static Node findClosestAncestor(Node n1, Node n2){
    
    
    
    pathToRoot1 = pathToRoot(n1);
    pathToRoot2 = pathToRoot(n2);
    
    System.out.println("path n1: " + pathToRoot1.toString());
    System.out.println("path n2: " + pathToRoot2.toString());
    
    for (Node node1 : pathToRoot1){
      for (Node node2 : pathToRoot2){
        if (node1 == node2){
          return node1;
        }
      }
    }
    
    return null;
  }
  
  public static List<Node> pathToRoot (Node startNode){
    ArrayList<Node> path = new ArrayList<Node>();
    Node nodeToEval = startNode;
    while (nodeToEval.parent != null){
      path.add(nodeToEval);
      nodeToEval = nodeToEval.parent;
    }
    
    path.add(nodeToEval);
    
    return path;
  }
  
  
  
  
}

class Node{
  Node parent;
  Node left;
  Node right;
  String data;
  public Node (String data){
    this.data = data;
  }
  
  @Override
  public String toString(){
    return data;
  }
}

- eliel.development April 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node cca(Node n1, Node n2) {

int d1 = depth(n1);
int d2 = depth(n2);

if (d1 < d2) {
n2 = nUp(n2, d2 - d1);
} else {
n1 = nUp(n1, d1 - d2);
}

Node p1 = n1.parent;
Node p2 = n2.parent;
while(p1 != p2) {
p1 = p1.parent;
p2 = p2.parent;
}
return p1;
}

Node nUp(Node n, int n) {
while(n > 0) {
n--;
n = n.parent;
}
}

int depth(Node n) {
int c = 0;
while(n != null) {
n = n.parent;
c++;
}
return c;
}

- Rus July 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node cca(Node n1, Node n2) {

  int d1 = depth(n1);
  int d2 = depth(n2);
  
  if (d1 < d2) {
     n2 = nUp(n2, d2 - d1);    
  } else {
     n1 = nUp(n1, d1 - d2);
  }

  Node p1 = n1.parent;
  Node p2 = n2.parent;
  while(p1 != p2) { 
    p1 = p1.parent;
    p2 = p2.parent;
  } 
  return p1;
}

Node nUp(Node n, int n) {
  while(n > 0) {
    n--;
    n = n.parent;
  }
}

int depth(Node n) {
  int c = 0;
  while(n != null) {
    n = n.parent;
    c++;
  }
  return c;
}

- Rus July 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Got this with several children down:

public static Node closestCommonAncestor (Node a, Node b) {
	if(a != null && b != null) {
		//meaning root
		if(a.parent == null && b.parent == null) {
			return a.value.equals(b.value) ? a : null;
		}

		//check if they have the same parents so not go up
		else if((a.parent != null && b.parent != null) && (a.parent.value == b.parent.value)) {
			return a.parent;
		}

		return closestCommonAncestor(a.parent == null ? a : a.parent, b.parent == null ? b : b.parent);
	}

	return null;
}

- anna banana November 04, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More