## Facebook Interview Question for Software Engineer / Developers

• 5

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;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

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
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Ohh i missed that one, that makes it more interesting

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;
}
}``````

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;
}``````

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;
}
{
this->left = left;
left->parent = this;
}
{
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');

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``````

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.

Comment hidden because of low score. Click to expand.
0

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;

}``````

Comment hidden because of low score. Click to expand.
0

Clever solution! I like it

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;
}``````

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);
}``````

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;
}

}
}``````

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)``````

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;
}``````

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,treeForest);

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;
treeForest = nodeA;
treeForest = nodeB;
treeForest = nodeC;
treeForest = nodeD;
treeForest = nodeE;
treeForest = nodeF;
treeForest = nodeJ;
treeForest = 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;
treeForest = node1;
treeForest = node2;
treeForest = node3;
treeForest = node4;
treeForest = node5;
treeForest = node6;
treeForest = node7;
treeForest = node8;
treeForest = 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){
nodeToEval = nodeToEval.parent;
}

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;
}
}``````

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;
}

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;
}``````

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;
}``````

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.

### 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.