Goldman Sachs Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
1
of 5 vote

Start from root.
Check whether A and B are on the same side of the subtree.
if they are on the different sides, then the node is the common ancestor

- Jay October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How you gonna check A or B on same side?.. since it doesn't have data to compare.

- MrA October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote

oops! forgot to return prev Node at the end of the code

- MrA October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1- Root will be one of the Ancestor for sure.
Step 2- if nodeA is less than root and node B is greater and vice versa than root is the only Ancestor , if not than repeat the same process for descendent nodes you will get the Ancestor nodes.

- Ankit Garg October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how do you know greater or less if the node does not contain a value??

- RS October 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

valid iff BST

- sduwangtong December 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Lets say there are two node given 'F' and 'P'

-Find the traversing path for 'F'
[Path_1] Root => 'A' => 'B' => 'D' => 'F'

-Find the traversing path for 'P'
[Path_2] Root => 'A' => 'B' => 'G' => 'L' =>'P'

-Compare both of the path and find the last same node in both path
---- A and B are common in both of the path, hence B is the common parent for both node 'F' and 'P'

- PKT October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node commonAnsctr(Node nodeA,Node nodeB, Node root){

	if(root==null||nodeA==null||nodeB==null)
	   return null;

	//find node for A in the tree
	Queue q=new Queue();
	q.enqueue(root);
	
	int depthA=0;
	int depthB=0;
	
	Map<Node,Node> map=HashMap<Node,Node>();
	
	while(!q.isEmpty()){
	
		Node p=q.dequeue();
		
		if(p==A)
			nodeAfound=true;
		if(p==B)
            nodeBfound=true;
		
		if(!nodeAfound)
			depthA++;
		if(!nodeBfound)
			depthB++;
			
		if(nodeAfound&&nodeBfound)
			break;
		
		if(p.left!=null){
			map.put(p.left,p);
			q.enqueue(p.left);
		}
		
		if(p.right!=null){
			map.put(p.right,p);
			q.enqueue(p.right);
		}
	
	}
	
	//error condition if one of the node is not in the tree
	
	if(!nodeAfound||!nodeBfound)
		return null;
	
	Node backtrackNode=null;
	
	//which is one is the closest node
	if(depthA<depthB){
		//node a is closest node to root
			backtrackNode=nodeB;
	}else{
		backtrackNode=nodeA;
	}
	int min=Math.min(depthA,depthB);
	int max=Math.max(depthA,depthB);
	//backtrack they both come to the same level

	while(max!=min){
		backtrackNode=map.get(backtrackNode);
		max--;
	}
	
	//now when both are at the same level
	//independent of they are on both side or at the different side of their common ancestor, they will converge to the same point
	//case 1: they are at the same side
	if(backtrackNode==nodeA||backtrackNode==nodeB)
		return map.get(backtrackNode);
		
	else{
		//case 2 they are different side of the ancestor-node
		//backtrack there till they have common ancestor
		Node anotherBckTrckNode=(backtrackNode==nodeA)?nodeB:nodeA;
		
		while(anotherNode!=backtrackNode){
			
			backtrackNode=map.get(backtrackNode);
			anotherBckTrckNode=map.get(anotherBckTrckNode);
		
		}
		return anotherBckTrckNode;
	}
	
	return null;
}

- sumit-Dey October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about using Pre-order traversal of the tree..? The order of the tree does't really matter ..

So here's the really pseudo-code:

1. Start Pre-order traversal of the tree and traverse until you find an 'x' in [A,B].
2. When x is found record it as the tentative ancestor.
3. Continue traversal at 'x', if the other node is found within 'x', then 'x' is the common ancestor (assuming a node can be its own ancestor).
4. Else, update the tentative ancestor to a node's parent whenever backtracking from it using the stored parent-reference.
5. When the other node is found, the tentative-ancestor is the common ancestor.

Let us know if u see problems with this.

- pugachevsoul November 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Perform Breadth First search for the tree and keep appending the visiting nodes in an array.
child1 = indexOf(node1) & child2 = indexOf(node2)
///2. While ( child1 != child2)
{
child1=(child1-1)/2
child2=(child2-1)/2
}

return array[child1 or child2]

- Chetan Sharma March 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Find path from root to node A using DFS. Say it is 'root' -> P -> Q -> R -> S -> A
2. Find path from root to node B using same DFS. Say it is 'root' -> P -> Q -> R -> X -> B
3. Iterate both lists keeping two pointers, cur and prev.
4. Keep iterating until you reach a point where cur is different for path(A) and path(B).
5. prev is your answer.

- gs May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1) perform an inorder traversal and augment the data structure with order. it will become a BST tree.

2) after that, find Common Ancestor using the BST tree.

- xietangren October 30, 2013 | 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