## Microsoft Interview Question Interns

Team: idc
Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
10
of 10 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;
}
}``````

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

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.

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

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

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

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

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

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.

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

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

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

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

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

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

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

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.

Comment hidden because of low score. Click to expand.
4
of 4 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.

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

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?

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

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

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

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

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

@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).

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

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

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

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.

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

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

Comment hidden because of low score. Click to expand.
2
of 2 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);
}
}``````

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

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

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

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

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

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.

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.

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

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

Use stacks to traverse inorder 2 BST simultaneously.

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

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

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

yep same idea. +1

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

can you please explain this more clearly?

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

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

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

Bug fix

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

}

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

}

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.

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