## Microsoft Amazon Interview Question for Software Engineer / Developers

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

This problem reduces to finding the point of intersection of two linked lists (because parent pointers are given).

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

``````node* LCA(node *x,node *y)
{
int d1=0,d2=0;
for(node *i=x;i!=NULL;i=i->parent) d1++;
for(node *i=y;i!=NULL;i=i->parent) d2++;

if(d1!=d2)
{
while(d1<d2) {
y=y->parent;
d2--;
}
while(d1>d2) {
x=x->parent;
d1--;
}
}
while(x!=y)
{
x=x->parent;
y=y->parent;
}
return x;
}``````

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

ttp://geeksforgeeks.org/?p=1029

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

The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side.

Implementation:
view source
print?
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* newNode(int );

/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
{
/* If we have reached a leaf node then LCA doesn't exist
If root->data is equal to any of the inputs then input is
not valid. For example 20, 22 in the given figure */
if(root == NULL || root->data == n1 || root->data == n2)
return -1;

/* If any of the input nodes is child of the current node
we have reached the LCA. For example, in the above figure
if we want to calculate LCA of 12 and 14, recursion should
terminate when we reach 8*/
if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;

if(root->data > n1 && root->data < n2)
return root->data;
if(root->data > n1 && root->data > n2)
return leastCommanAncestor(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return leastCommanAncestor(root->right, n1, n2);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}
/* Driver program to test mirror() */
int main()
{
struct node *root = newNode(2);
root->left = newNode(1);
root->right = newNode(4);
root->right->left = newNode(3);
root->right->right = newNode(5);

/* Constructed binary search tree is
2
/ \
1 4
/ \
3 5
*/
printf("\n The Least Common Ancestor is \n");
printf("%d", leastCommanAncestor(root, 3, 5));

getchar();
return 0;
}

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

sorry but this real bs

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

This makes the assumption that the tree is a BST. It could be unordered.

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

Here is a generic solution for finding LCA for two values in a general binary tree. Now for BST, we can do some simple trimming of the recursion so it will be fast. Leave to you to think:

``````// find least common ancestor in a binary treeu.
int max_level = -1;
int lca_value = 0;
// node: current node.
// a, b: two values we're looking their LCA for. they don't need to
//       to be ordered, that a not necessarily smaller than b.
// pa, pb: returns to call that whether value a and/or value b exists
//         in this sub tree with node as its root.
// level: how deep are we in the tree.
// assumption the all the values in the tree are unique.
void FindLca(NODE *node, int a, int b, bool *pa, bool *pb, int level)
{
*pa = *pb = false;

if (!node) goto exit;

if (node->value == a) { *pa = true; }
if (node->value == b) { *pb = true; }

bool la = false, ra = false, lb = false, rb = false;

if (node->left)
{
FindLca(node->left, a, b, &la, &lb, level + 1);
}
if (node->right)
{
FindLca(node->right, a, b, &ra, &rb, level + 1);
}

if (!*pa) { *pa = la || ra; }
if (!*pb) { *pb = lb || rb; }

exit:

if (*pa && *pb && level > max_level)
{
max_level = level;
lca_value = node->value;
}
}``````

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

The question is about specific tree - not about binary tree: there are no 'left' and 'right', but 'parent' instead of this.

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

Here is a simpler solution. As you find parent keep on inserting in a hash table. Look for other nodes parent in hash table. First point where its found is LCA.

``````Node* LCA(Node* root, Node* x, Node* y) {
if(x == root || y == root || x == NULL || y == NULL) { return NULL; }
hash_set<Node*> parents;
while(x->parent) {
parents.insert(x->parent);
x = x->parent;
}

while(y->parent) {
if(parents.find(y->parent) != parents.end()) { return y->parent; }
y = y->parent;
}

return NULL;
}``````

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

Start with one node and while navigate towards root, put the node into a hashtable.
Do the same for the second node but verify if the node is in the hashtable.

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

Find the depth of both nodes. Lets say depth of node X be 15 & node Y be 10. Then traverse node X (larger depth) towards parent by 5 (15-10) nodes. Lets say it comes out to be Z.
After this traverse both Z & Y towards parent node & keep on matching them. First common match is a LCA.

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

Mike...
To just make it clear-the node with greater depth should be designated as X.
It works!
Thankyou

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

This will work but you'll be making many more traversals through the tree since you need to now first find the depth of each node which is O(n) operation for each node.

It's a trade-off between space and time though - with your approach, at most constant extra space is required but 4 O(n) passes. With the hashtable approach above, you can do it with just 2 O(n) passes through the tree but you will need O(n) space.

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

Same as two linked list which are having common node

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

Yes, similar problem to that of finding intersection of two linked lists. :)

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

Its easier than mentioned in the answers above. Find the shorted depth, let's call it s. Traverse the node with higher depth up s times to its parent and you are done !

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

What a crappy solution! What does it mean, if two nodes x and y lie on same level?

First, draw few trees on paper, and then come up with a solution, idiot!

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

What if traversing the larger depth node up 5 times(if 5 is the diff between the depth of two nodes) takes you past the LCA of the two nodes .... ??? IN this case the aboce solution wont work...

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

This can never be the case with tree !

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

Let us have two stacks S1 and S2. Let a and b be the two nodes for which LCA have to be found. Move up from 'a' and store the way(nodes) in S1. Move up from 'b' and store the way in S2.Now pop the stacks until a mismatch occurs or one of the path ends. The node before the first mismatch or the the last node before one of the stacks become empty is the LCA.

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

This code should do the trick :
1 traversal until encounter the first node;
2 check if second node is under the first node, if so, the first node self is LCA, otherwise ,go3
3. go back with parent pointer until found one which have right subtree and the second node is in it , then this node is LCA.

``````Node *	LCA(Node *root, Node *n1, Node *n2)
{
bool find = false;  // keep track of if lca is found or not
Node *lca = NULL;
DoLCA(root, n1, n2, find, lca);
Return lca;
}

Void 	DoLCA(Node *root, Node *n1, Node *n2, bool &find, Node *&lca)
{
if ( root == NULL)
Return ;

// encounter the first node
If ( root == n1 || root == n2)
{
Node *Second = root == n1 ? n2 : n1;
If (Cover(root, second))
Lca = root;
Else
{
While(root)
{
root = root->parenet;
If(root->Right && Cover(root->Right, second))
{
Lca = root;
Break;
}
}
}
Find = true;
Return;
}

// go left
DoLCA(root->Left, n1, n2, second, flag, lca);
If (find)
Return;    // lca found , just return, no need to go right
// go right
DoLCA(root->Left, n1, n2, second, flag, lca);
}``````

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

This code should do the trick :
1 traversal until encounter the first node;
2 check if second node is under the first node, if so, the first node self is LCA, otherwise ,go3
3. go back with parent pointer until found one which have right subtree and the second node is in it , then this node is LCA.

``````Node *	LCA(Node *root, Node *n1, Node *n2)
{
bool find = false;  // keep track of if lca is found or not
Node *lca = NULL;
DoLCA(root, n1, n2, find, lca);
Return lca;
}

Void 	DoLCA(Node *root, Node *n1, Node *n2, bool &find, Node *&lca)
{
if ( root == NULL)
Return ;

// encounter the first node
If ( root == n1 || root == n2)
{
Node *Second = root == n1 ? n2 : n1;
If (Cover(root, second))
Lca = root;
Else
{
While(root)
{
root = root->parenet;
If(root->Right && Cover(root->Right, second))
{
Lca = root;
Break;
}
}
}
Find = true;
Return;
}

// go left
DoLCA(root->Left, n1, n2, second, flag, lca);
If (find)
Return;    // lca found , just return, no need to go right
// go right
DoLCA(root->Left, n1, n2, second, flag, lca);
}``````

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

@all:simpler approach is to find the depth of x and y from top......then
pseudocode:
{while(p[x]!=p[y])
{
if(depth[x]>depth[y])x=p[x];
else
y=p[y];
}
return x;
if any mistake then crct me.....

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

@all:simpler approach is to find the depth of x and y from top......then
pseudocode:
{while(p[x]!=p[y])
{
if(depth[x]>depth[y])x=p[x];
else
y=p[y];
}
return x;
if any mistake then crct me.....

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

LCA is a binary search tree (BST) is simple. For any nodes x and y, the LCA is the first node which lies between x and y starting from root.

Node getLCA_BST(Node root, Node x, Node y):
Node curr = root
while !(x < curr && curr < y): // x.value < curr.value
if curr < x && curr < y:
curr = curr.right
else: //x < curr && y < curr
curr = curr.left
return curr // assume x and y are in the tree

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.