Microsoft Interview Question for Interns


Team: idc
Country: India
Interview Type: Written Test




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

Flawless code ... Enjoy!!
InOrder traversing both the trees iteratively and checking for any common elements...
Time O(n) ... Space O(n) where n > m

void dups(node* a, node* b)
{
	if(!a || !b)
		return;
	stack<node*> p,q;
	node* n1 = a, *n2 = b;
	while(true)
	{
		if(n1)
		{
			p.push(n1);
			n1 = n1->left;
		}
		else if(n2)
		{
			q.push(n2);
			n2 = n2->left;
		}
		else if (!p.empty() && !q.empty())
		{
			n1 = p.top();
			n2 = q.top();			
			if(n1->data < n2->data)
			{
				p.pop();
				n1 = n1->right;
				n2 = NULL;
			}
			else if(n2->data < n1->data)
			{
				q.pop();
				n2 = n2->right;
				n1 = NULL;
			}
			else
			{
				cout<<n1->data<<" ";
				p.pop();
				q.pop();
				n1 = n1->right;
				n2 = n2->right;
			}
		}
		else
			break;
	}
}

- Avinash September 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey Avinash, I am little confused at if condition where you checked if(n1->data < n2->data). shouldn't n2 be put back in q there and similarly n1 in p in next else if condition, then assign these to null? I feel, otherwise you will miss few comparisons. Please let me know if I am thinking wrong.

- Vannu September 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh my bad, you are accessing their top. sorry for spam!

- Vannu September 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

else
			{
				cout<<n1->data<<" ";
		------->		p.pop();
		------->		q.pop();
				n1 = n1->right;
				n2 = n2->right;
			}

Above two lines pointed by arrow in code will give Empty Stack exception.
As you have already poped top items to n1 and n2 at the beginnning.

Correct me if i am wrong.

- Amit Singh September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To Amit Singh: there is no exception:
1) Stacks are not empty since '!p.empty() && !q.empty()'.
2) Then the algo does 'if(...){pop()}else if(...){pop()}else{pop()}'. So the exception is not possible here.

- Aleksey.M September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just a remark: in case of the tree is balanced the required memory is O(log(n)).

- Aleksey.M September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Convert both trees to doubly linked list. O(n) space. And then find the intersection of these two linked lists. Much less space.

- Dinesh October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If the space is O(n) why don't you just use a hash map

- lala November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you think O(N+M) is better than O(M*logN) if N >> M?

your solution is good to some extent, but not ideal.

- anerky2002 December 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

traverse first tree INORDER. Store it in an array ( this is ascending order). Now traverse the other tree and do binary search on the array...Alternatively you can also start traversing the other tree and search the first tree itself..no need to do the initial inorder traversal.

- saurabh September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,

So, the worst case efficiency would be (when both have no common elements),
let's say the number of element in the first BST is n
and the number of elements in the second BST is m

You check the first element in first BST and then do a binary search on the other.
O(nlogm), since you are doing binary search n times on a BST of m elements.

Is that correct?

- belligerentCoder September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I was thinking of a similar solution but somehow maintaining an array (with inorder traversal) seems to be efficient. It has a space overhead of O(m+n) but saves us tail recursion overhead.

Which would be great in larger BSTs

- belligerentCoder September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@BelligerentCoder: no need for searching the other tree. You can do it with just in-order traversal on both trees. Think of how the merge step works in mergesort. You can use a similar technique here.

- eugene.yarovoi September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene: Yes, but if m is very large, for instance say n^100, then, a Theta(n log m) solution might fare better than a Theta(n+m) solution (assuming the trees are balanced).

- Anonymous September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous: Very true. No need to go that far -- the example applies even for n^2 or technically for n^(1+e) for any e > 0, for that matter.

I suppose a full answer would specify this tradeoff, and further specify that if we do search the second tree, we should be iterating through the smaller tree and searching the larger tree.

- eugene.yarovoi September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In worst case, a tree might be aligned linearly (already sorted data). In that case, the complexity won't be nlogm. It will be (n * m). logn search complexity of a tree is an average case scenario.

- Learner September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Leaner: Did you miss the comment about balanced trees in parentheses?

- Anonymous September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

Based on Johny's post:

void intersect(node* a, node* b) {
    if (!a || !b) return;
    if (a->value < b->value) {
        intersect(a, b->left);
        intersect(a->right, b);
    }
    else if (a->value > b->value) {
        intersect(a->left, b);
        intersect(a, b->right);
    }
    if (a->value == b->value) {
        printf("%d ", a->value);
        intersect(a->left, b->left);
        intersect(a->right, b->right);
    }
}

- pckben October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

Recursive version. Time O(n) and Space O(n) where n > m

void findCommon(Node* r1, Node* r2) {
  if (r1 == NULL || r2 == NULL) return;
  if (r1->data == r2->data) {
    cout << r1->data << "\n";
    findCommon(r1->left, r2->left);
    findCommon(r1->right, r2->right);
  }
  else if (r1->data < r2->data)
    findCommon(r1, r2->left);
  else 
    findCommon(r1->left, r2);
}

- Johny September 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is with the 'right' branches in 'else if' and 'else'? Seems the algo doesn't process them correctly.

- Aleksey.M September 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is wrong !! It will find only one common node !!

- Weirdo October 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we know the sizes of the trees, say m and n where m<n. I will take the inorder traversal of the smaller tree (the tree with m nodes) then search for the elements in the second tree. It will take O(m ln n) time. It is similar to sourabh's answer. There are other ways but I cant think of more efficient way than this.

- Vijay September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be sone in O(m+n) and O(m) space where m<=n
1. First find Inorder travelsal of smaller tree and store it in array. O(m).
2. Now Go through second tree inorder and start with the first element of array. If found print the element. If the element in array is less than the element on tree move to the next element of array.

- loveCoding September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

traverse both trees iteratively in inorder traversal fashion simultaneously by comparing values of both nodes firstly moving one node next with min value

- dev September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Use stacks to traverse inorder 2 BST simultaneously.

- m September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time = O(n), Space=O(logn), where n is the size of bigger tree.

- Anonymous September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yep same idea. +1

- GKalchev September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you please explain this more clearly?

- Rakesh September 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Do a BFS on the first tree and add the elements to an unordered_map
- Do a BFS on the second tree and check if those elements are present in the map [O(1) lookup]
- time/space =>O(m+n)/O(m) where m>=n

- Rahul Arakeri September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Do a BFS on the first tree and add the elements to an unordered_map
- Do a BFS on the second tree and check if those elements are present in the map [O(1) lookup]
- time/space =>O(m+n)/O(m) where m>=n

- Rahul Arakeri September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bug fix

inorder(Tree *T1,Tree*T2)
{
if(T1!=NULL)
{
inorder(T1->left,T2);
cout<<BinarySerach(T2,T1->data)
inorder(T1->right,T2);
}

}

- Kapil September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

inorder(Tree *T1,Tree*T2)
{
if(T1!=NULL)
{
inorder(T1->left);
cout<<BinarySerach(T2,T1->data)
inorder(T1->right);
}

}

- Kapil September 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think u should first push all leftmost branch into stack

- ashok September 04, 2014 | 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