## 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)``````

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.

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

That should have been depth first search.

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

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));``````

Comment hidden because of low score. Click to expand.
0

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

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;
}

}

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){
return true;
}
if(getNodePath(root.left, node, path)){
return true;
}
if(getNodePath(root.right, node, path)){
return false;
}
return false;``````

}

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.

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;
}``````

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;
}

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.

Comment hidden because of low score. Click to expand.

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.

### 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.