Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
The nodes on different levels is a trippy case...my code broke on this test case. Thanks for the hint.
Ah, great. I used the heights, but didn't think to skip up the extra height on the longer branch. Then it's simple
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;
}
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
}
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
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?
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;
}
}
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;
}
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
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.
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;
}
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;
}
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);
}
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;
}
}
}
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)
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;
}
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;
}
}
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;
}
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;
}
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;
}
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.
- Sergey January 17, 2015