Amazon Interview Question for Software Engineer / Developers


Country: India




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

I think, we can boil down this question to a simpler one.

Basic concept is that we need to find two extreme nodes (one furthest left, one furthest right) in between all the 'k' given nodes. So, any nodes which lie in between these nodes will be under those two's LCA i.e. divergent point of the paths connecting root and these two nodes will be the LCA of all 'k' nodes.

So, the algo is:

1. Do the inorder traversal of the tree.
2. Find two nodes, one extreme left of the tree and one extreme right.
3. Run normal LCA on that findLCA(node *root, node *left, node *right)

- Psycho January 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a breadth first search and collect the number of "target nodes" found at each node and below. the moment this count becomes the number of nodes to be searched at any node, store it's pointer and keep returning it all the way up and exit.

- Dheeraj January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

That should have been depth first search.

- Anonymous January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The stack method is the right one.

1. Construct k sets (array) and populate it with inorder traversal path of each node.
2. For each node in set 1 , see whether it is present in set 2... set n

- Pras January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a BFS you can find it. You don't care about the path but length of the path when performing the search.

function find_ancesstor (tree, a, b) {

    var shortest_distance = Infinity;
    var result = null;
    traverse(tree, []);

    return result.data;

    function traverse (node) {
        if(!node) return;

        var distance = find_distance(node, a, b);
        if(distance && distance < shortest_distance){
            shortest_distance = distance;
            result = node;
        }

        traverse(node.left);
        traverse(node.right);
    }
}

function find_distance (node, a, b) {
    var distance_a = null,
        distance_b = null;

    traverse(node, 0)

    function traverse (node, distance) {
        if(!node) return;

        if(node.data == a){
            distance_a = distance;
        }
        if(node.data == b){
            distance_b = distance;
        }

        distance += 1;

        traverse(node.left, distance);
        traverse(node.right, distance);
    }
    if(distance_a && distance_b){
        return distance_a + distance_b;
    }
    return null;
}



//                                  8
//              4                                       12
//      2               6                   10                      14
//  1       3       5       7           9       11              13      15
var tree = {"data":8,"left":{"data":4,"left":{"data":2,"left":
    {"data":1,"left":null,"right":null},"right":{"data":3,
    "left":null,"right":null}},"right":{"data":6,"left":
    {"data":5,"left":null,"right":null},"right":{"data":7,
    "left":null,"right":null}} },"right":{"data":12,"left":
    {"data":10,"left":{"data":9,"left":null,"right":null},
    "right":{"data":11,"left":null,"right":null}},"right":
    {"data":14,"left":{"data":13,"left":null,"right":null},
    "right":{"data":15,"left":null,"right":null}} }};


console.log(find_ancesstor(tree, 9, 11));

- Mocoder January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its not about finding LCA of two elements but LCA of k elements!

- Psycho January 08, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its a sample code for k=3 where n1, n2 and n3 are 3 nodes. Can be generalized further by taking n1, n2, n3 in array. Basic idea is when we find a node, parent is updated that node is found. So parent can see if total k nodes are found till now or not.

int LCA_(bt_ *root, int k, int n1, int n2, int n3)
{
	if(root==NULL)
		return 0;
	int total = 0;
	int found_l = LCA_(root->left,k,n1,n2,n3);
	int found_r = LCA_(root->right,k,n1,n2,n3);
	total = found_l+found_r;
	if(root->data == n1 ||
		root->data == n2 ||
		root->data == n3)
	{
		total++;
	}
	if(total == k)
	{
		printf("LCA %d ",root->data);
		total = 0;
	}
	return total;

}

- Anonymous January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the path for each node, and compare the path.

BinaryTreeNode getLatestCommonParent(BinaryTreeNode root, ArrayList<BinaryTreeNode> nodes){
		if(root == null){
			return null;
		}
		boolean[] boolResult= new boolean[nodes.size()];
		ArrayList<ArrayList<BinaryTreeNode>> pathList = new ArrayList<ArrayList<BinaryTreeNode>>();
		for(int i = 0; i < nodes.size(); i++){
			if(nodes.get(i) == null){
				return null;
			}
			boolResult[i] = getNodePath(root, nodes.get(i), pathList.get(i));
		}
		for(int i = 0; i < nodes.size(); i++){
			if(!boolResult[i]){
				return null;
			}
		}
		boolean mark = false;
		int loc = 0;
		BinaryTreeNode LCA = root;
		while(!mark){
			for(int i = 0; i < nodes.size(); i++){
				if(pathList.get(i).get(loc) == null || pathList.get(i).get(loc) != pathList.get(0).get(loc)){
					mark = true;
				}
			}
		}
		return LCA;
		
	}
	private boolean getNodePath(BinaryTreeNode root,
			BinaryTreeNode node, ArrayList<BinaryTreeNode> path) {
		if(root == null){
			return false;
		}
		if(root == node){
			path.add(node);
			return true;
		}
		path.add(node);
		if(getNodePath(root.left, node, path)){
			return true;
		}
		if(getNodePath(root.right, node, path)){
			return false;
		}
		return false;

}

- ZhenyiLuo January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this: walk the tree N times looking up for target nodes keeping a hash table with visited counter for each node in the order of when a node was first found. Once all nodes are found, traverse the hash table from the back and find the first node that has the counter of N.

- DS January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Function to find LCA of n1 and n2. The function assumes that both
   n1 and n2 are present in BST */
struct node *lca(struct node* root, int n1, int n2)
{
    if (root == NULL) return NULL;
 
    // If both n1 and n2 are smaller than root, then LCA lies in left
    if (root->data > n1 && root->data > n2)
        return lca(root->left, n1, n2);
 
    // If both n1 and n2 are greater than root, then LCA lies in right
    if (root->data < n1 && root->data < n2)
        return lca(root->right, n1, n2);
 
    return root;
}

- Nit January 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static TreeNode LCA(TreeNode root, TreeNode[] nodes) {
if (root == null) {
return null;
}

for(int i=0;i<nodes.length;i++) {
if (root == nodes[i]) {
findCount++;
return root;
}
}


TreeNode leftRoot = LCA(root.left, nodes);
TreeNode rightRoot = LCA(root.right, nodes);
if (leftRoot != null && rightRoot != null) {
// if child1 and child2 are on both sides
return root;
}

// either one of child1 or child2 is on one side
// OR child1 or child2 is not in L&R subtrees
return (leftRoot != null) ? leftRoot : rightRoot;
}

- Wenyu January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS/BFS is getting slower in the case of n ary tree.
if there is the pointer to the parent node available,
1) calculate the paths from the nodes to the root
2) there is the common path for all the paths, and the last node of the common path is the answer.

- nishikenster July 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.


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