Amazon.com
3.3 of 5 3,202 reviews
www.amazon.com Seattle, WA 5000+ Employees

Amazon.com Software 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
Add Tags [?]
Answer Flag Question

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

Answers & Comments

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 Flag Response
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 Flag Response
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 Flag Response
5
of 6
votes
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 Flag Response
1
of 1
vote
//correction

temp = node2;
while( temp.parent ! = null)
{
   temp = temp.parent;
   counter2++;
}
- Hamid Dadkhah on Dec 8, 2012 Flag Response
0
of 0
votes
@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 Flag Response
0
of 0
votes
I seems really like the question of finding intersection of two linked lists
- Anonymous on Dec 10, 2012 Flag Response
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 Flag Response
0
of 3
votes
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 Flag Response
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 Flag Response
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 Flag Response
0
of 0
votes
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 Jun 22, 2014 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Amazon.com interview questions and advice. All interview reviews posted anonymously by Amazon.com employees and interview candidates.