Microsoft Amazon Interview Question 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).

- AV on October 31, 2010 | Flag Reply
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;
}

- abhijith on March 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous on July 09, 2010 | Flag Reply
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;
}

- nagpal_dce on August 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry but this real bs

- Anonymous on August 28, 2010 | Flag
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;
    }
}

- Jin on October 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aleksey.M on November 28, 2012 | Flag
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;
}

- coolpk on December 01, 2010 | Flag Reply
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.

- S on February 22, 2011 | Flag Reply
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.

- Mike on February 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aneesha on February 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on March 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Same as two linked list which are having common node

- anno on February 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Abhishek on July 27, 2011 | Flag
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 !

- Ashish Kaila on March 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- absolutely WRONG ! on June 07, 2011 | Flag
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...

- Anonymous on March 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This can never be the case with tree !

- Anon on April 03, 2011 | Flag
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.

- Karthick on July 11, 2011 | Flag Reply
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);
}

- iatbst on February 07, 2012 | Flag Reply
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);
}

- iatbst on February 07, 2012 | Flag Reply
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.....

- Anonymous on May 27, 2012 | Flag Reply
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.....

- Anonymous on May 27, 2012 | Flag Reply
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

- ashish.cooldude007 on June 30, 2010 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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