Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

dff

- explorer.bit January 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You mean BFF? Yes, once tree in UNORDERED then it worth considering the tree as directed (we can traverse it only downwards) graph.

Complexity is linear from the amount of tree nodes.

- Igory January 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

struct node{
	int data;
	struct node* left;
	struct node* right;
};

struct node* leastCommonAncestor(struct node* root,struct node* p,struct node* q){
	
	if(root==NULL){
		return NULL;  //If no root  leastCommonAncestor is NULL.
	}

	if(root==p || root==q){
		return root; // Check if the current root is equal to any of the desired node.
	}else{
		struct node* l=leastCommonAncestor(root->left, p, q); // Find LCA in left of the tree
		struct node* r=leastCommonAncestor(root->right, p, q); // Find LCA in right of the tree
		
		if(l!=NULL && r!=NULL){
			return root; 
		}else if(l!=NULL && r==NULL){
			return l;
		}else if(l==NULL && r!=NULL){
			return r;
		}else{
			return NULL;
		}
	}	
}

- CrYPtO January 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 vote

http://bestinterviewsquestions.blogspot.in/2013/02/find-least-common-ancestorlca.html

- Learn Android: http://learnandroideasily.blogspot.in/ February 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algorithm only finds if two nodes have a LCA, it doesn't return the node which is LCA

- north_remembers February 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

private static void leastCommonAncestor(final TreeNode root, TreeNode n1, TreeNode n2) {
		Stack<TreeNode> leftPath = getPath(root, n1);
		Stack<TreeNode> rightPath = getPath(root, n2);
		while (!leftPath.isEmpty() && !rightPath.isEmpty()) {
			int lca = 0;
			if ((lca = leftPath.pop().value) == rightPath.pop().value) {
				System.out.println(lca);
			}
		}
	}

	private static Stack<TreeNode> getPath(TreeNode root, TreeNode n) {
		HashMap<TreeNode, Object> visitedMap = new HashMap<>();
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		visitedMap.put(root, null);
		while (!stack.isEmpty()) {
			TreeNode t = stack.peek();
			if (t.value == n.value) {
				return stack;
			} else if (t.left != null && !visitedMap.containsKey(t.left)) {
				visitedMap.put(t.left, null);
				stack.push(t.left);
			} else if (t.right != null && !visitedMap.containsKey(t.right)) {
				visitedMap.put(t.right, null);
				stack.push(t.right);
			} else {
				stack.pop();
			}
		}
		return stack;

}

- Rocko January 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Corner case missing .. Question hasn't mentioned it is a binary tree.. Infact the question Says its an UNORDERED tree. So a Child may hv 5 children and another hv only 1... your code fails here

- hprem991 January 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

struct TreeNode {
TreeNode(int in_value = 0) : parent(0), left(0), right(0), value(in_value)
{
}

TreeNode *parent;
TreeNode *left;
TreeNode *right;
int value;
};

int GetNodeLevel(TreeNode *node)
{
int level = 0;

if ( node ) {
TreeNode *parentNode = node->parent;
while(parentNode) {
++level;
parentNode = parentNode->parent;
}
}

return level;
}

TreeNode* GetLeastCommonAncestor(TreeNode *node1, TreeNode *node2)
{
if ( node1 && node2 ) {
int n1level = GetNodeLevel(node1);
int n2level = GetNodeLevel(node2);

while( n1level!=n2level ) {
if ( n1level>n2level) {
--n1level;
node1 = node1->parent;
}
else {
--n2level;
node2 = node2->parent;
}
}

while ( node1 && node2 && node1!=node2 ) {
node1 = node1->parent;
node2 = node2->parent;
}
}

return (node1 && node1==node2) ? node1 : 0;
}

- Anonymous January 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its Not a Binary tree

- hprem991 January 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It doesn't matter. The same approach can be applied to any tree.

- Anonymous January 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

find node2 in the sub-tree of node1's parent, parent's parent recursively

- Bin January 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int LCA(int value1,int value2){
		Node node1 = find(value1);
		Node node2 = find(value2);
		int depth1 = depth(value1);
		int depth2 = depth(value2);
		if(depth1>depth2)
		{
			while(depth1>depth2)
			{
				node1 = node1.getParent();
				depth1--;
			}
		}else if(depth2>depth1)
		{
			while(depth2>depth1)
			{
				node2 = node2.getParent();
				depth2--;
			}
		}
		  while(node1 != null|| node2!= null){
				  if( node1 == node2)
					  break;
				  node1 = node1.getParent();
				  node2 = node2.getParent();
					
			 }
		
		 return node1.getValue();
	}

- jerry January 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A single node can have multiple children.

The idea is to find two paths from the root to the two nodes separately and then find the least common nodes from the two lists.
One possible downside is that we go through the nodes twice for each query node we consider.
However, the space and time [O(number of nodes) both for time and space] complexity remains the same.

Feel free to point out any flaws. :-)

import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;

class Node {
    Node children[];
    int value;
}

// The recursive method
private boolean findTrail(Node curr, Node node, List trail){
        if(curr == node ){
            trail.add(curr);
            return true;
        }
        
        boolean found = false;
        for(Node child : curr.children){
            found = findTrail(child, node, trail);
            if(found){
                trail.add(curr);
                return true;
            }
        }
        return false;
    }
//.................

// Method using the recursive method.
public Node findLeastComAns(Node root, Node A, Node B){
        if(root == null || A == null || B == null){
            return null;
        }
        
        List list1 = new ArrayList();
        List list2 = new ArrayList();
        
        boolean found = findTrail(root, A, list1);
        if(!found){
            return null;
        }
        found = findTrail(root, B, list2);
        if(!found){
            return null;
        }
        
        Iterator<Node> itr1 = list1.listIterator();
        Iterator<Node> itr2 = list2.listIterator();
        Node common;
        Node least = null;
        while(itr1.hasNext()&&itr2.hasNext()){
            common = itr1.next();
            if(common == itr2.next()){
                if(least == null){
                    least = common;                    
                }
                else if(least.value > common.value){
                    least = common;
                }
            }
        }            
        return least;
    }

- nik January 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pseudo-code:

int traverse(node n) {
if(n is either of the given nodes) {
return 1;
}
if (n is leaf node) {
return 0;
}
else {
value = 0;
foreach (node m : children of n) {
value += traverse(m);
if (value>1) {
node n is the least parent;
exit; // r return 0 if you cannot exit

}

}
}

}

- Gourab January 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

algo:

1# find path to both of the nodes from root lets say pPath and qPath.
2# compare paths till the both start getting on different way. the previous node where the are departing will be least common ancestor.

Note: space complexity will be high but as i know time complexity will be maximum O(n+n+n) i.e. O(n)

comments and improvements are welcome.

- Crazy Tesla January 23, 2013 | 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