Facebook Interview Question Interns
Team: Software Engineering
Country: United States
Interview Type: Phone Interview
1. For both n1 and n2, count the number of nodes on their paths till the root. Let them be c1 and c2.
2. Suppose c1 > c2.
3. Traverse the parent/ancestor nodes of n1 for (c1-c2) steps till we reach some ancestor a1.
4. Compare a1 and n2. If (a1 == n2) return n2; else go to step 5
5.Traverse the parents/ancestors of a1 and n2 till either you find same ancestors or reach the roots (and beyond)
public Tree commonAncestor(Tree root, Tree p, Tree q)
{
if (covers(root.left, p) && covers(root.left, q))
return commonAncestor(root.left, p, q);
if (covers(root.right, p) && covers(root.right, q))
return commonAncestor(root.right, p, q);
return root;
}
private boolean covers(Tree root, Tree p)
{
if (root == null)
return false;
if (root == p)
return true;
return covers(root.left, p) || covers(root.right, p);
}
1. Calculate depth of each node.
2. If depth is different, go up the tree the deeper node
3. Go up the tree with both nodes and compare if the next node is the same
The python code:
{{
class Node(object):
def __init__(self, parent=None, left=None, right=None):
self.parent = parent
self.left = left
self.right = right
class NodeCursor:
def __init__(self, node):
self.node = node
self.depth = 0
self.root = self.node
while self.root.parent is not None:
self.depth += 1
self.root = self.root.parent
def move_up(self):
self.depth -= 1
self.node = self.node.parent
class AncestorFinder(object):
def __init__(self, node1, node2):
self.cursor1 = NodeCursor(node1)
self.cursor2 = NodeCursor(node2)
self.ancestor = self.__find()
def __find(self):
if self.cursor1.root != self.cursor2.root:
return None
# make both cursors the same depth
while self.cursor1.depth != self.cursor2.depth:
if self.cursor1.depth > self.cursor2.depth:
self.cursor1.move_up()
else:
self.cursor2.move_up()
while self.cursor1.node != self.cursor2.node:
self.cursor1.move_up()
self.cursor2.move_up()
return self.cursor1.node
}}
class Node(object):
def __init__(self, parent=None, left=None, right=None):
self.parent = parent
self.left = left
self.right = right
class NodeCursor:
def __init__(self, node):
self.node = node
self.depth = 0
self.root = self.node
while self.root.parent is not None:
self.depth += 1
self.root = self.root.parent
def move_up(self):
self.depth -= 1
self.node = self.node.parent
class AncestorFinder(object):
def __init__(self, node1, node2):
self.cursor1 = NodeCursor(node1)
self.cursor2 = NodeCursor(node2)
self.ancestor = self.__find()
def __find(self):
if self.cursor1.root != self.cursor2.root:
return None
# make both cursors the same depth
while self.cursor1.depth != self.cursor2.depth:
if self.cursor1.depth > self.cursor2.depth:
self.cursor1.move_up()
else:
self.cursor2.move_up()
while self.cursor1.node != self.cursor2.node:
self.cursor1.move_up()
self.cursor2.move_up()
return self.cursor1.node
class Node(object):
def __init__(self, parent=None, left=None, right=None):
self.parent = parent
self.left = left
self.right = right
class NodeCursor:
def __init__(self, node):
self.node = node
self.depth = 0
self.root = self.node
while self.root.parent is not None:
self.depth += 1
self.root = self.root.parent
def move_up(self):
self.depth -= 1
self.node = self.node.parent
class AncestorFinder(object):
def __init__(self, node1, node2):
self.cursor1 = NodeCursor(node1)
self.cursor2 = NodeCursor(node2)
self.ancestor = self.__find()
def __find(self):
if self.cursor1.root != self.cursor2.root:
return None
# make both cursors the same depth
while self.cursor1.depth != self.cursor2.depth:
if self.cursor1.depth > self.cursor2.depth:
self.cursor1.move_up()
else:
self.cursor2.move_up()
while self.cursor1.node != self.cursor2.node:
self.cursor1.move_up()
self.cursor2.move_up()
return self.cursor1.node
1. I'm checking if n1 and n2 are on the same tree by comparing their roots.
2. Going from n1 to the root, I'm checking if current node is a parent for n2, if yes, this is our result.
<?php
$n = [
11 => new Node(1, 18),
12 => new Node(2, 15, 11),
13 => new Node(16, 17, 11),
14 => new Node(3, 8, 12),
15 => new Node(9, 14, 12),
16 => new Node(4, 5, 14),
17 => new Node(6, 7, 14),
18 => new Node(10, 11, 15),
19 => new Node(12, 13, 15),
21 => new Node(1, 18),
22 => new Node(2, 15, 21),
23 => new Node(16, 17, 21),
24 => new Node(3, 8, 22),
25 => new Node(9, 14, 22),
26 => new Node(4, 5, 24),
27 => new Node(6, 7, 24),
28 => new Node(10, 11, 25),
29 => new Node(12, 13, 25),
];
$result = (new Collection($n))
->findClosestCommonParent(16, 15);
var_dump($result);
class Collection
{
/** @var array */
protected $n;
/**
* @param array $n, an associative array of Nodes with theirs ID's as keys
*/
public function __construct(array $n)
{
$this->n = $n;
}
/**
* @param int id1
* @param int id2
*
* @return Node|null
*/
public function findClosestCommonParent($id1, $id2)
{
if (false === isset($this->n[$id1])) {
throw new InvalidArgumentException();
}
if (false === isset($this->n[$id2])) {
throw new InvalidArgumentException();
}
$node1 = $this->n[$id1];
$node2 = $this->n[$id2];
if (false === $this->isTheSameTree($node1, $node2)) {
return null;
}
$result = $node1;
while ($result instanceof Node && false === $result->isParentFor($node2)) {
$result = $this->findParent($result);
}
return $result;
}
/**
* @param Node $node1
* @param Node $node2
*
* @return bool
*/
protected function isTheSameTree(Node $node1, Node $node2)
{
return $this->findRoot($node1) === $this->findRoot($node2);
}
/**
* @param Node $node
*
* @return Node|null
*/
protected function findParent(Node $node)
{
return isset($this->n[$node->parent]) ? $this->n[$node->parent] : null;
}
/**
* @param Node $node
*
* @return Node
*/
protected function findRoot(Node $node)
{
while (null !== $node->parent) {
$node = $this->findParent($node);
}
return $node;
}
}
class Node
{
/** @var int */
public $parent;
/** @var int */
public $left;
/** @var int */
public $right;
/**
* @param int $left
* @param int $right
* @param int|null $parent
*/
public function __construct($left, $right, $parent = null)
{
if ($left + 1 > $right) {
throw new InvalidArgumentException();
}
$this->left = $left;
$this->right = $right;
$this->parent = $parent;
}
/**
* @param Node $node
*
* @return bool
*/
public function isParentFor(Node $node)
{
return $this->left < $node->left && $this->right > $node->right;
}
}
Find height (n1 ) and height(n2). Get their difference and traverse the deepest node with difference steps upward .In this was both nodes with equal height.
Then traverse both nodes n1 and n2 further till they reach to the first common node - this will be their parent, otherwise we return null because nodes are from different trees.
Complexity (log(n)), memory O(1)
class Node {
private Node parent;
private Node left;
private Node right;
Node (Node l, Node r, Node p) {
left = l;
right = r;
parent = p;
}
}
int getHeight(Node n) {
int h = 0;
while (n != null) {
n = n.parent;
h++;
}
return h;
}
Node getLowestParent(Node n1, Node n2) {
Node tmp = n1;
int s1 = getHeight(tmp);
tmp = n2;
int s2 = getHeight(tmp);
int min = Math.abs(s1 - s2);
while (min > 0) {
n1 = n1.parent;
min -= 1;
}
Node curr1 = n1;
Node curr2 = n2;
while (curr1 != null || curr2 != null) {
if(curr1 == curr2) {
return curr1;
}
curr1 = curr1.parent;
curr2 = curr2.parent;
}
return null;
}
public class Node
{
Node parent;
Node right;
Node left;
};
public class ParentFinder
{
private class DepthAndNode
{
public int depth;
public Node node;
}
Node FindCommonParent(Node n1, Node n2)
{
if (n1 == null || n2 == null)
{
return null;
}
DepthAndNode r1 = GetRoot(n1);
DepthAndNode r2 = GetRoot(n2);
// They dont have common root, so they dont have common parent
if (r1.node != r2.node)
{
return null;
}
// Bring n1 and n2 to the same level
while (r1.depth > r2.depth)
{
r1.node = r1.node.parent;
--r1.depth;
}
// Bring n1 and n2 to the same level
while (r2.depth > r1.depth)
{
r2.node = r2.node.parent;
--r2.depth;
}
while (n1 != n2)
{
n1 = n1.parent;
n2 = n2.parent;
}
return n1;
}
DepthAndNode GetRoot(Node n)
{
DepthAndNode r = new DepthAndNode();
r.depth = 0;
while (n.parent != null)
{
++r.depth;
r.node = n.parent;
n = n.parent;
}
return r;
}
}
typedef struct _node{
int data;
_node *left;
_node *right;
}node;
int getParent(int i){
if (i == 0) return i;
return (((i % 2) > 0) ? (i / 2) : ((i / 2) - 1));
}
node* getNode(node* root, int i){
if (i < 0) return NULL;
if (i == 0) return root;
queue<node*> q;
q.push(root);
while (1){
node *temp = q.front();
if (i == 0) return temp;
i--;
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
q.pop();
}
}
int findNode(node* root, int data){
if (root == NULL) return -1;
if (root->data == data) return 0;
queue<node*> q;
q.push(root);
int i = 0;
while (!q.empty()){
node *temp = q.front();
if (temp->data == data) return i;
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
q.pop(); i++;
}
return -1;
}
node* commonParent(node* root, int n1, int n2){
if (root == NULL) return root;
int p1 = getParent(findNode(root, n1));
int p2 = getParent(findNode(root, n2));
if (p1 < 0 || p2 < 0) return NULL;
while (p1 != p2){
if (p1 > p2) p1 = getParent(p1);
else p2 = getParent(p2);
}
return getNode(root,p1);
}
Tree* comAnces(Tree* n1, Tree* n2) {
Tree* a = n1, *b=n2;
int counterA = 0, counterB = 0;
while (a->parent != NULL && b->parent != NULL) {
a = a->parent; counterA++;
b = b->parent; counterB++;
}
if(a->parent == NULL && b->parent == NULL) {
if (a == b) return a; //reach root at the same time
} else if (a->parent == NULL) {
while(b->parent != NULL) {
b = b->parent; counterB++;
}
if(b != a) return NULL;
a = n1; b= n2; for(int i =0; i < counterB - counterA; i++) b = b->parent;
} else {
while(a->parent != NULL) {
a = a->parent; counterA++;
}
if (a != b) return NULL;
a = n1; b= n2; for (int i = 0; i < counterA-counterB; i++) a = a->parent;
}
while(a != b) {
a = a->parent; b= b->parent;
}
return a;
}
I want to understand why recursive solution will not work for this case?
Node findCommonParent(Node n1, Node n2){
if(n1.parent==null || n2.parent==null) return null;
if(n1.parent==n2.parent || n1.parent==n2) return n1.parent;
if( n2.parent==n1) return n1;
Node n3 = findCommonParent(n1.parent,n2);
Node n4 = findCommonParent(n1, n2.parent);
if(n3==null && n4==null) return null;
return n3!=null ? n3 : n4;
}
As per my understanding, the solution has nothing to do with "forest of binary trees". We can just crawl the parents of both nodes n1 and n2 upwards and see if their parents are same.
Sample code module below:
Please let me know if I missed anything:
Node* findCommonParent(Node* n1, Node* n2)
{
// Same nodes are passed
if (n1 == n2) return NULL;
// If both nodes are NULL
if(!n1 && !n2) return NULL;
// If one of the nodes is NULL
if(!n1 || !n2) return NULL;
Node* lca = NULL;
while(n1->parent && n2->parent)
{
if (n1->parent == n2->parent)
{
lca = n1->parent;
break;
}
n1 = n1->parent;
n2 = n2->parent;
}
return lca;
}
1) initialize 2 counters: one for each given node;
- zr.roman December 26, 20152) in 2 consecutive loops go from n1 to root, and from n2 to root, while incrementing respective counter in respective loop, and testing if n1 is placed on the way from n2 to root, and vice versa.
3) compare 2 obtained roots: if they are not same, then return NULL,
If the are the same then compare counters.
If any of them is 0, then the answer is root.
If n1 is placed on the way from n2 to root (or vice versa), then we take node to which the smaller counter corresponds and get its parent, and this will be the answer.
Otherwise subtract the smaller counter from the bigger one - this will be the number of steps upward, which are necessary to perform starting from node to which the bigger counter corresponds to reach the level of the other given node. Then, when we reach this level, we traverse starting from this level moving 2 pointers upward in 1 loop until we hit the common parent.
If the counters are equal and differ from 0, then it means that given nodes already lay on the same level, so we traverse from both nodes upward in 1 loop until we hit the common parent.
O(log n).
O(1).