Bloomberg LP Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
6
of 8 vote

Assume the given two nodes are x and y.
1) 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.

- samuel February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
5
of 7 vote

1. Move upto the root for both the nodes , store the paths.
2. Compare the path , the first common node is the required node

- Anonymous February 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We could reverse the two path and find the first different one. It will be easier.

- mayingjie116 January 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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

- sunkyu.hwang August 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1. move up one node until the root, hashmap<node, boolean>
2. move up the other node, hit the first hashmap pair -> nearest ancestor

- wangguanying6 March 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm assuming the function takes in the two nodes we need to find the ancestor for. Then just start BFS from those two nodes, move up the parents, first common node encountered will be the LCA (lowest common ancestor).

Modify BFS to fit N-ary tree.

- Anonymous February 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- navneetsingh5189 March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Second one is not O(1) space cause you use recursion.

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

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

- navneetsingh5189 March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- ATuring September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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.

- Object April 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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']

- arunprasath9586 February 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- shekhar2010us March 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- bobthrollop April 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

//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];

}

- igorfact June 30, 2014 | 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