## 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

Comment hidden because of low score. Click to expand.
0

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

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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

valid iff BST

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'

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

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.

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]

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).

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.

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.

### 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.