## Interview Question

Software Development Engineer In Test Interview

-Seattle, WA

Amazon## Most of them were expected. Almost all are problem solving questions. 1. Given a BST with following property find the LCA of two given nodes. Property : All children has information about their parents but the parents do not have information about their children nodes. Constraint - no additional space can be used

## Interview Answers

15 Answers

function findLCA(Node node1, Node node2) { int counter1 = 0; int counter2 = 0; Node temp; //Find the level for each node, use a temp node to //traverse so that we don't lose the info for node 1 and node 2 temp = node1; while( temp.parent ! = null) { temp = temp.parent; counter1++; } temp = node2; while( node2.parent ! = null) { node2 = node2.parent; counter2++; } /* * We wanna make them at the same level first */ if(counter1 > counter2) { while(counter1 != counter2) { node1 = node1.parent; counter1--; } } else { while(counter2 != counter1) { node2 = node2.parent; counter2--; } } while (node1.parent != node2.parent) { node1 = node1.parent; node2 = node2.parent; } System.out.println("Found the LCA: " + node1.parent.info); }

Hamid Dadkhah on

//correction temp = node2; while( temp.parent ! = null) { temp = temp.parent; counter2++; }

Hamid Dadkhah on

Consider this is a BST, where max node is always on the right of min node, we can traverse max upward one node at a time while comparing min nodes as it traverse upward toward root. BinaryNode findBSTLCA( BinaryNode min, BinaryNode max ) { BinaryNode tempMax = max; BinaryNode tempMin = min; while( tempMax != null ) { while( tempMin != null ) { if( tempMin.element == tempMax.element ) return tempMin; tempMin = tempMin.parent; } tempMin = min; // reset tempMin tempMax = tempMax.parent; // traverse tempMax upward 1 node } return null; // no LCA found }

howardkhl on

Consider that the lowest common ancestor in a binary search tree means the node value would be between the two values passed in. Because everything left is less than and everything right is greater than, we can traverse the tree using this knowledge. Here's the solution in PHP for something different: function findLowestCommonAncestor(Node $root, $value1, $value2) { while ($root != null) { $value = $root->getValue(); if ($value > $value1 && $value > $value2) { $root = $root->getLeft(); } else if ($value getRight(); } else { return $root; } } return null; //the tree is empty }

Ja on

howardkhl - your solution works, but this is O(n^2) complexity, making it too slow for large enough trees. Ja - your solution might work (haven't thoroughly checked it) but it violates the restriction that a parent node does not know about the child node. So this answer is invalid. The correct answer is the one given by Hamid Dadkhah, which, just like an anonymous responsder said, is the same problem as an intersecting list.

gman on

you can use the following method *Node getLCA(Node *n1, Node* n2){ while(n1.parent!=null){ Node * p= n2; while(p.parent!=null){ if(n1.parent!=p.parent) p=p.parent; else return p.parent; } } }

Anonymous on

Pick one of the nodes in random. Keep traversing up until the property: new node is greater than one of the nodes and lesser than the other is satisfied.

Shishir on

I was also interviewed with same question. They not only ask the solution they also ask for the time complexity of the solution. Make sure you to ask different questions and confirm the type of tree. They could give you binary search tree, binary tree, sorted binary tree. Solution will greatly depend on the type of the tree.

Anonymous on

@chmielsen : your solution would work... but as said by Hamid, due to the constraint of space, you have to consider some other technique.

interview candidate` on

I seems really like the question of finding intersection of two linked lists

Anonymous on

Hint - detect the level at which the given nodes are present. Then travel upwards from that position.

Anonymous on

How about traversing from one node to root, adding each node to hashset, Then try do the same with second one, on collision return node.

chmielsen on

No, you cannot do that since you need extra space for hashset which is not allowed, I am going to post my solution in a min

Hamid Dadkhah on

1)consider node1 as p1. see if p1=p2 , p1->parent=p2, p2->parent=p1 2)now for a value p1 try to see recursively if p2->parent ever becomes equal to p1 or p2=root 3)set p1=p1->parent and continue till p1=p2 or p1= root

Anonymous on

temp1 = node1; temp2 = node2; while( temp1.parent != null && temp2.parent != null){ if(temp1.value == temp2.value){ return temp1; // temp1 and temp2 point to same node so pick one } temp1 = temp1.parent; temp2 = temp2.parent; } System.out.println("no such ancestor");

Anonymous on