Bloomberg LP Interview Question
Country: United States
1. Move upto the root for both the nodes , store the paths.
2. Compare the path , the first common node is the required node
Not sure I covered all cases. But here are the basic idea I have.
namespace
{
struct Node
{
Node* parent;
};
//
// How to define solution ?
//
// return : Nearest Ancestor
//
// argument1 : Node1
// argument2 : Node2
//
int Depth(Node* n)
{
int d = 0;
while (n->parent)
{
n = n->parent;
++d;
}
return d; // for root, this will return 0
}
Node* CommonAncestor(Node* n1, Node* n2)
{
// trivial solutions
if (!n1 || !n2) return NULL;
if (n1 == n2) return n1; // itself
int d1 = Depth(n1);
int d2 = Depth(n2);
while (d1 > d2) { --d1; n1 = n1->parent; }
while (d2 > d1) { --d2; n2 = n2->parent; }
// d1 == d2
while (n1 != n2 && d1 > 0)
{
n1 = n1->parent;
n2 = n2->parent;
--d1;
}
if (n1 == n2) return n1;
return NULL; // we don't have any solution here !
}
}
Here are two solutions.
1) Using Parent pointer and HashTable.
If the tree is balanced:
Time:O(log n)
Space:O(log n)
else both time and space are of the order of O(n)
Node* commonAncestorWithParent(Node* p,Node* q){
unordered_map<Node*,Node*> HashTable;
while(p!=NULL){
HashTable.insert(make_pair(p,p));
p=p->pParent;
}
while(q!=NULL){
if(HashTable.find(q)!=HashTable.end())
return HashTable.find(q)->second;
q=q->pParent;
}
return NULL;
}
2) Solution without parent pointer and no other data structure. I think it's quite optimal.
Time: O(n)
Space: O(1)
Node* commonAncestorWithoutParent(Node*root,Node*p,Node*q){
Node *left=NULL,*right=NULL;
if(root==p||root==q)
return root;
if(root->pLeft!=NULL)
left=commonAncestorWithoutParent(root->pLeft,p,q);
if(root->pRight!=NULL)
right=commonAncestorWithoutParent(root->pRight,p,q);
if(left!=NULL){
if(right!=NULL)
return root;
return left;
}
else{
if(right!=NULL)
return right;
return NULL;
}
}
Here are two solutions.
1) Using Parent pointer and HashTable.
If the tree is balanced:
Time:O(log n)
Space:O(log n)
else both time and space are of the order of O(n)
Node* commonAncestorWithParent(Node* p,Node* q){
unordered_map<Node*,Node*> HashTable;
while(p!=NULL){
HashTable.insert(make_pair(p,p));
p=p->pParent;
}
while(q!=NULL){
if(HashTable.find(q)!=HashTable.end())
return HashTable.find(q)->second;
q=q->pParent;
}
return NULL;
}
2) Solution without parent pointer and no other data structure. I think it's quite optimal.
Time: O(n)
Space: O(1)
Node* commonAncestorWithoutParent(Node*root,Node*p,Node*q){
Node *left=NULL,*right=NULL;
if(root==p||root==q)
return root;
if(root->pLeft!=NULL)
left=commonAncestorWithoutParent(root->pLeft,p,q);
if(root->pRight!=NULL)
right=commonAncestorWithoutParent(root->pRight,p,q);
if(left!=NULL){
if(right!=NULL)
return root;
return left;
}
else{
if(right!=NULL)
return right;
return NULL;
}
}
My java like solution, it assumes there is a function "Parent" which returns parent node:
Node commonParent(Node n1, Node n2){
int deptN1, deptN2;
Node current=n1;
//find dept of node1
while(current!=root){
current=Parent(current);
deptN1++
}
current=n2;
//finde dept of node 2
while(current!=root){
current=Parent(current);
deptN2++
}
Node fromN1=n1, fromN2=n2;
//n1 was in lower level
if(deptN1>deptN2)
{
for(int i=0; i<(deptN1-deptN2); i++){
fromN1=Parent(fromN1);
}
Node x1=Parent(fromN1);
Node x2=Parent(n2);
if(x1==x2){
return x1;
}
else {
commonParent(x1,x2);
}
//n2 is in lower level
} else if(deptN1<deptN2){
for(int i=0; i<(deptN2-deptN1); i++){
fromN1=Parent(fromN1);
}
Node x1=Parent(n1);
Node x2=Parent(fromN2);
if(x1==x2){
return x1;
}
else {
commonParent(x1,x2);
}
// both node are in same level
else
{
Node x1=Parent(n1);
Node x2=Parent(n2);
if(x1==x2){
return x1;
}
else {
commonParent(x1,x2);
}
}
}
}
def commonAncestor(node1, node2)
ancestors1 = listAncestors(node1)
ancestors2 = listAncestors(node2)
common = null
while (ancestors1.isNotEmpty and ancestors2.isNotEmpty) do
a1 = ancestors1.dequeue
a2 = ancestors2.dequeue
if (a1!= a2)
break
common = a1 # or a2
end
return common
end
def listAncestors(node)
ancestors = Queue.new
current = node
while (true) do
if (current == rootNode)
break
ancestors.enqueue(current.parent)
current = current.parent
end
return ancestors
end
O(n) Time for initialization, O(logn) time to find LCA, O(n) Space
By doing a DFS:
1. Get the euler's tour path in a vector, v1.
2. Get the level of all the nodes in euler's path in second vector, v2.
3. Get the first occurrence of each node in euler's tour in a third vector, v3.
4. Build a segment tree out of v2.
For the given 2 vertices, to find the LCA:
1. Get the first occurrence of nodes from v3.
2. For the range returned by step 1, get the minimum level node from v2. Segment tree makes this operation logarithmic.
3. Match the idx of the minimum node with euler's tour path v1. This node is the LCA.
This method uses the fact that LCA is equal to the one and only one node that's closest to the root that occurs in the euler's path between the two given nodes.
def find_lca(self, node1, node2):
root_node = self.root
def lca(n1, n2, root):
"""
Lowest Common Ancestor
"""
if n1 > n2:
n1, n2 = n2, n1
if n1 <= root.value <= n2:
return root
if root.value <= n1 and root.value <= n2:
return lca(n1, n2, root.right)
if root.value >= n1 and root.value >= n2:
return lca(n1, n2, root.left)
raise Exception("Elements not in tree")
return lca(node1, node2, root_node).__dict__['value']
Time: O(log n)
Memory: O(log n)
Given: Two nodes: n1, n2 and root: r
Solution:
Step 1: Move up from n1 to r --> store the ids in a list, list1
Step 2: Move up from n2 to r --> store the ids in a list, list2
Step 3: Reverse list1 and list2
Find the id till ids are common in list1 and list2. This "id" will be the solution
I don't understand your last sentence.
If you construct both lists as LIFO stacks, i.e. add each parent node to the front of the list as you work your way up the tree, you end up with two lists that both start with root and are identical for their first one or more elements. Step through the lists together, and the last element before you find two non-matching elements is the nearest common ancestor.
//getCommonAncestor.cpp
#include <iostream>
#include <vector>
#include <cstddef>
using namespace std;
class Node
{
int id;
Node* parent;
public:
Node(int iid, Node* prnt = NULL):id(iid),parent(prnt){}
Node* getParent(){return parent;}
void setParent(Node* n){parent = n;}
int getId(){return id;}
};
Node* commonAncestor(Node* n1, Node* n2)
{
vector<Node*> rootPath1, rootPath2;
Node* np=n1;
while(np != NULL)
{
rootPath1.push_back(np);
np = (*np).getParent();
}
np=n2;
while(np != NULL)
{
rootPath2.push_back(np);
np = (*np).getParent();
}
vector<Node*>::iterator it1 = rootPath1.end()-1;
vector<Node*>::iterator it2 = rootPath2.end()-1;
while((**it1).getId() == (**it2).getId())
{
if ((**it1).getId() != (*n1).getId() && (**it1).getId() != (*n1).getId())
{
it1--; it2--;
}
else
return *it1;
}
return *(++it1);
}
void printAncestor(const vector<Node*>& tree, int nodeId1, int nodeId2)
{
Node* n1 = tree[nodeId1];
Node* n2 = tree[nodeId2];
Node* np = commonAncestor(n1, n2);
cout << "Common ancestor of nodes " << nodeId1 << " and " << nodeId2;
cout << " has Id " << (*np).getId() << '\n';
}
int main()
{
vector<Node*> trie;
for (int id=0; id<19; id++)
trie.push_back(new Node(id));
(*trie[1]).setParent(trie[0]);
(*trie[2]).setParent(trie[0]);
(*trie[3]).setParent(trie[0]);
(*trie[4]).setParent(trie[1]);
(*trie[5]).setParent(trie[1]);
(*trie[6]).setParent(trie[1]);
(*trie[7]).setParent(trie[2]);
(*trie[8]).setParent(trie[3]);
(*trie[9]).setParent(trie[3]);
(*trie[10]).setParent(trie[4]);
(*trie[11]).setParent(trie[4]);
(*trie[12]).setParent(trie[5]);
(*trie[13]).setParent(trie[6]);
(*trie[14]).setParent(trie[7]);
(*trie[15]).setParent(trie[8]);
(*trie[16]).setParent(trie[9]);
(*trie[17]).setParent(trie[9]);
(*trie[18]).setParent(trie[9]);
printAncestor(trie, 0, 0);
printAncestor(trie, 0, 1);
printAncestor(trie, 4, 14);
printAncestor(trie, 4, 12);
printAncestor(trie, 8, 18);
printAncestor(trie, 16, 18);
for (int id=0; id<18; id++)
delete trie[id];
}
Assume the given two nodes are x and y.
- samuel February 22, 20141) find the depths of x and y, call the dx and dy, since we have parent function, this should be easy
2) move deeper node up abs(dy-dx) steps first,
3) move both nodes up until the pointer are the same.