Amazon Interview Question for Software Engineer in Tests


Team: Kindle
Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
8
of 10 vote

node* findLCABinaryTree(node* head, node* a, node* b)
{
	if(head == NULL)
		return NULL;
	if(head == a || head == b) return head;
	node *L, *R;
	L = findLCABinaryTree(head->left, a, b);
	R = findLCABinaryTree(head->right, a, b);
	
	if(L != NULL && R!= NULL)
		return head;
	if(L == NULL && R!= NULL)
		return R;
	if(R == NULL && L!= NULL)
		return L;
	return NULL;
}

Slightly different version to sonny.c.patterson!!
Please comment, if anything is wrong.

- praveen November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very nice. You don't really need R==null in the last if. You also can change R==null to !R and R!=null to just R, etc., because null evaluates to false.

- sonny.c.patterson November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't work if just one of the nodes is not in the tree. In that case it returns the node that is in the tree. But I think the original question allows the assumption that they are in the tree.

- sonny.c.patterson November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

succinct and elegant

- startup November 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simple but not elegant..

What if one of the input nodes is a child of another?
For example Say node *a is same as head and node *b exists somewhere in the left or right branches;

- Satya December 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In that case "head == a" and so it will return the head as the LCA, which is correct.

The code is indeed quite clean, but can be a little confusing too because the method the intent of this recursive method is different between the main call and the recursive ones. The main call finds the LCA while the recursive one just finds whatever node is equal to "a" or "b". But no big deal.

- Sunny December 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's covered.

- sonny.c.patterson December 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 8 vote

Very simple solutiion ^^

int find_node2( Node *node, int value1, int value2 ) {
    int ret = 0;
    if( node->data == value1 || node->data == value2 ) {
        ret++;
    }

    if( node->left ) {
        ret += find_node2( node->left, value1, value2 );
    }

    if( node->right ) {
        ret += find_node2( node->right, value1, value2 );
    }

    if( ret == 2 ){
        printf("this node is common parent: %d(%d,%d)\n",
            node->data, value1, value2);
    }

    return ret > 0 ? 1 : 0;
}

- charsyam November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1 Nice. Very minimal solution. This assumes data is an identifier, which I wasn't assuming, but should have. I like the return counter... slick!

- armorrison November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This assumes that the values are unique, which seems like an unreasonable solution.

- Anonymous November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Have you read the original question ? You have to find (and presumably return it) the LCA node, while your code just returns integers.

- ashot madatyan November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ashot madatyan, yes it just returns integer, if it finds valid node, it is easy to return the node itself.

- charsyam November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It functions for non-unique values, it just uses the nodes closest to the root.

- armorrison November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's the lca of two nodes, not the lca of two values. If you wanted to find the lca of nodes with values that duplicate ancestor nodes this would give incorrect results. You need to compare addresses, no values.

- sonny.c.patterson November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. let A and B are the nodes
2. traverse from A to the root node using the parent link and hash each traversed node
3. traverse from B to the root node using the parent link and same time check in the hash table
4. if a node found in the hash table, that is the least commmon Ancestor


Here complexity is: T -> O(n) & S -> O(n) since it a binary tree.

- Vinod November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But the Node class doesn't record parent links. How would you solve this if you can only go down the tree from a given node? I assume you would be given the root node of the tree as well as the two nodes A and B.

- MikeO November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

strucy Node *tmp=root;
while(tmp!=NULL)
{
 if(tmp->data > fisrtNode->data && tmp->data > secondNode->data)
  tmp=tmp->leftChild;
 else if(tmp->data < firstNode->data && tmp->data < secondNode->data)
  tmp=tmp->rightChild;
 else
  {
     if(firstNode->parent == secondNode)
        return secondNode->parent;
     else if(secondNode->parent == firstNode)
       return firstNode->parent;
      else
         return tmp;
  }
}

- Anonymous November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not a BST and I do not see parent in the given structure, so it won't work.

- Anon November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The complexity of the above code is O(lgn)

- Anonymous November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A slight variation I was given stated that the desired nodes might not be in the Binary Search Tree, and that duplicates values in the BST are allowed, and will be put on the left.

- trevie November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not a BST

- sonny.c.patterson November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let Node A and B the nodes in question.

1. Search for a Node A in the binary tree. Record a path to A as you search it.
2. Repeat above for Node B.
3. At this point you have a path from root to A and a path from root to B.
4. Search through these paths and find the least common nodes that appear in the paths.

- Anonymous November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if I am breaking rules of the asker with this solution. (I added params to track the parent as you look for the child)

class Program
    {
        static void Main(string[] args)
        {
            Node node5 = new Node(5, null, null);
            Node node4 = new Node(4, null, null);
            Node node3 = new Node(3, null, null);
            Node node2 = new Node(2, node4, node5);
            Node node1 = new Node(1, node2, node3);

            Node common = NodeHelper.ParentFinder(node1, node4, node3);
            Console.WriteLine(common.data);
            Console.ReadLine();
        }
    }

    class Node{
        public int data;
        public Node leftchild;
        public Node rightchild;

        public Node(int _data, Node _leftchild, Node _rightchild)
        {
            data = _data;
            leftchild = _leftchild;
            rightchild = _rightchild;
        }

        //adding some helper fields
        public Node parent; 
        public int level;        
    }

    static class NodeHelper
    {
        public static Node ParentFinder(Node root, Node node1, Node node2)
        {

            if (nodeParentPopulater(root, null, node1, 0) && nodeParentPopulater(root, null, node2, 0))
            {
                 //continue
            }
            else
            {
                //nodes not found
                return null; 
            }
            
            Node temp1 = node1;
            Node temp2 = node2;

            //find each nodes parent node that lives at the same level
            while (temp1.level > temp2.level)
            {
                temp1 = temp1.parent;
            }
            while (temp1.level < temp2.level)
            {
                temp2 = temp2.parent;
            }

            //now start checking if the nodes are the same
            while (!temp1.Equals(temp2))
            {
                temp1 = temp1.parent;
                temp2 = temp2.parent;
            }

            //parents are the same. return the parent node
            return temp1;
        }

        private static bool nodeParentPopulater(Node node, Node parentNode, Node nodeToFind, int level)
        {
            bool found = false;

            node.parent = parentNode;
            node.level = level;
                        
            if (node.Equals(nodeToFind)) return true;
                                   
            if (node.leftchild != null)
            {
                found = nodeParentPopulater(node.leftchild, node, nodeToFind, level + 1);
            }
            if (!found && node.rightchild != null)
            {
                found = nodeParentPopulater(node.rightchild, node, nodeToFind, level + 1);
            }

            return found;
        }
    }

- armorrison November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is the code without using parent link

public class LCABT {
	static BTNode lca = null;
	static BTNode foundNode = null;
	private static boolean findLCA(BTNode root,int a, int b, boolean inPath){
		if(root == null)
			return false;
		if(root.getData() == a || root.getData() == b){
			if(foundNode!=null && foundNode.getData()!=root.getData()){
				if(inPath)
					lca = foundNode;
				return true;
			}else{
				foundNode = root;
				inPath = true;
			}
		}
		boolean inLeft = false;
		boolean inRight = false;
		if(lca == null)
			inLeft = findLCA(root.getLeft(),a,b,inPath);
		if(lca == null){
			inRight = findLCA(root.getRight(),a,b,inPath);
			if(lca==null && inLeft && inRight){
				lca = root;
			}
		}
		
		if(lca == null && root == foundNode){
			inPath = false;
			return true;
		}
		
		
		return inLeft || inRight;
	}
	
	public static void main(String[] argv){
		BTNode n1 = new BTNode(5);
		BTNode n2 = new BTNode(2);
		BTNode n3 = new BTNode(3);
		BTNode n4 = new BTNode(9);
		BTNode n5 = new BTNode(11);
		BTNode n6 = new BTNode(50);
		BTNode n7 = new BTNode(7);
		n1.setLeft(n2);
		n1.setRight(n3);
		n2.setLeft(n4);
		n2.setRight(n5);
		n3.setRight(n6);
		n4.setLeft(n7);
		findLCA(n1,11,7,false);
		System.out.println("LCA : "+lca.getData());
	}
	

}

class BTNode{
	private int data;
	private BTNode left;
	private BTNode right;
	public BTNode(int data){
		this.setData(data);
	}
	public void setLeft(BTNode left) {
		this.left = left;
	}
	public BTNode getLeft() {
		return left;
	}
	public void setRight(BTNode right) {
		this.right = right;
	}
	public BTNode getRight() {
		return right;
	}
	public void setData(int data) {
		this.data = data;
	}
	public int getData() {
		return data;
	}
	
}

- jenish.shah November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This assumes the values in the tree are unique. That seems like an unreasonable assumption.

- Sonny November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is to search for the nodes in the left sub tree and the right sub tree starting at the root. Recursive calls to the function FindCommonAncestorInBinaryTree() checks if the nodes are found. If one of nodes is found, it is marked as found and the search will continue for the next node. More explanation and code can be found here:

linearspacetime.blogspot.com/2012/04/find-common-ancestor-of-two-nodes-in.html

- Anonymous November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

LCA of two nodes in a binary tree - complete implementation that also checks whether the nodes are in the tree at all. Algorithm description are inline, as well as inlined are the comments to help you understand the complete flow of the algo:

bool contains(Node *root, Node *sought)
{
    if (NULL == root)
        return false;
    
    if (root->data == sought->data)
        return true;
        
    return (contains(root->left, sought) || contains(root->right, sought));
}

/**
    Algorithm description:
    Find the subtrees where the two nodes are contained. 
    if either of the nodes is not found 
        return NULL
    else
        return the node starting from where the two nodes being sought are in different subtrees (the two nodes diverge)
*/
Node* LCA (Node *root, Node *firstnode, Node *secondnode)
{
    bool ffound_in_left, ffound_in_right, sfound_in_left, sfound_in_right;
    
    ffound_in_left = contains(root->left, firstnode);
    if (ffound_in_left) {
        sfound_in_left = contains(root->left, secondnode);
        if (sfound_in_left) {
            return LCA(root->left, first, second);
        }
        else {
            sfound_in_right = conatins(root->right, second);
            if (sfound_in_right) // the nodes diverge here (the first is in the left and the second is in the right, so return root)
                return root;
            return NULL; // the right node has not been found at all
        }
    }
    else { // the first node not in left, try to find it in the right subtree
        ffound_in_right = contains(root->right, first);
        
        if (ffound_in_right) {
            sfound_in_right = contains(root->right, second);
            if (sfound_in_right) {
                return LCA(root->right, first, second); // both the first and second nodes are in the right subtree, go to there
            }
            else { // the first found in the right and the second not found in the right, check to see whether the second exists in the tree at all
                sfound_in_left = contains(root->left, second);
                if (sfound_in_left == true) {  // second found in the left subtree, while the first is in the right, so they diverge
                    return root; // 
                }
                else { // second not found in the tree at all
                    return NULL;
                }
            }
        }
    }
    
    // first not found in the right subtree either, so it is not present in the tree at all
    return NULL;

}

- ashot madatyan November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What does the contains function do? Depth first search?
Whats the time complexity of the contains function?

- CameronWills November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ugh

- sonny.c.patterson November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@CameronWills
The "contains" function is very straightforward - starting from the input node it just looks for the node with the given value. First it checks the input node's value, if it is not the one being sought, it looks in the left and then in the right subtrees of the given node.
Time complexity of this function is O(N). The overall time complexity of the given solution is quadratic, with constant space.

@sonny.c.patterson
Would you please bother yourself commenting the "Ugh" - for me this term does not contain any logic, neither does it provide us with any counterarguments or some constructive reasoning.

- ashot madatyan November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I stand by my comment. This is the most horrible piece of code imaginable. My children cried when they saw it. My dog ran into the road an threw himself under the first passing car. Jesus wept.

- sonny.c.patterson November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sonny<...>
I'd suggest you to ask your late dog about how smart you are, you still may get some clever hints from it. Not sure about your kids - if they have gone after their father, then ... guess you already understood what they are in for. Live and learn (if you can)..

- ashot madatyan November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should stick to comedy. You clear have a sense of humor.

Let me just say about your code, since you don't seem to see the issue, that if the LCA node is one million levels down the tree, you are going to find the two nodes one million times. Why not find them just one time?

- sonny.c.patterson November 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Btw, the solution is not constant space. Every recursive call allocates multiple pointers. So it's O(n) space.

- sonny.c.patterson November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

BTW, are you familiar with the tail recursion paradigm?

- ashot madatyan November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Is this tail recursive? I don't think so because of the double call.

- sonny.c.patterson November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In any case the question only applies to the contains function, the LCA function certainly is not.

- sonny.c.patterson November 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* LCP(Node* tree, Node* node1, Node* node2, int* found = null)
{
    if (tree == null) return null;
    if (found == null) found = &0;
    Node* result;
    int rightFound = 0;
    int leftFound = 0;
    if (tree->rightchild) result = LCP(tree->rightchild, node1, node2, &rightFound);
    *found = 2;
    if (rightFound == 2)  return result;
    if (tree->leftchild) result = LCP(tree->rightchild, node1, node2, &leftFound);
    if (leftFound == 2) return result;
    *found = leftfound + rightfound;
    if (*found == 2) return tree;
    return null;

}

- sonny.c.patterson November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys how do you Turn the following class into a Singleton:

public class Earth {
public static void spin() {}
public static void warmUp() {}
}

public class EarthTest {
public static void main(String[] args) {
Earth.spin();
Earth.warmUp();
}
}

- guest Taro November 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Give it a private constructor and instantiate an object to a static member reference?

- sonny.c.patterson November 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Give it a private constructor and instantiate an object to a static member reference?

- sonny.c.patterson November 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My friend came up with this brilliant answer. He said :
1. List the pre and post order traversal of the tree.
(Now observe that the common parent of the two nodes will occur before both the nodes and after both the nodes in the pre and post order traversal listing respectively.)
2. In a pre-order traversal list place all the nodes occurring before n1 and n2 in a hash map h1
Preorder traversal P1: [....] n1....n2......
3. Now traverse the nodes which occur after both the Nodes n1 and n2. -
Postorder Traversal P2: ....n2....n1[....]
4. Return the first node which maps to the hash map h1 in the list P2

- teja.sbt November 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Explained here
In u tube / watch ? v = LFjCr2yDJdc

- hint December 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

In other words,It means to find the Least common Ancestor of two nodes in binary tree,which is by itself common to both :)

- Lucy Desouza November 07, 2012 | 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