Amazon.com

www.amazon.com
Work in HR? Unlock Free Profile

# Amazon.comSoftware Development Engineer In Test Interview Question

I interviewed in Seattle, WA and was asked:
"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"
 Tags: problem solving ,   See less 8

Part of a Software Development Engineer In Test Interview Review - one of 4,652 Amazon.com Interview Reviews

1
of 1
vote
Hint - detect the level at which the given nodes are present. Then travel upwards from that position.
- Interview Candidate on Dec 6, 2012
1
of 1
vote
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 Dec 8, 2012
1
of 1
vote
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 Dec 8, 2012
5
of 6
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 Dec 8, 2012
2
of 2
//correction

temp = node2;
while( temp.parent ! = null)
{
temp = temp.parent;
counter2++;
}
- Hamid Dadkhah on Dec 8, 2012
0
of 0
@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 Dec 8, 2012
0
of 0
I seems really like the question of finding intersection of two linked lists
- Anonymous on Dec 10, 2012
0
of 1
vote
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 Dec 12, 2012
0
of 3
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 Dec 16, 2012
1
of 1
vote
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 Jan 15, 2013
1
of 1
vote
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 < \$value1 && \$value < \$value2)
{
\$root = \$root->getRight();
}
else
{
return \$root;
}
}
return null; //the tree is empty
}
- Ja on Jan 26, 2014
0
of 0