Amazon Interview Question Software Engineer / Developers
I doubt if it's possible in linear time. lol's solution works for some specific case. Here's an example to show the difference:
______________10______________
/ \
_______3______ ______14
/ \ /
0 ___6__ 12
/ \
4 7
\ \
5 8
_______8______
/ \
___3__ 10__
/ \ \
1 _5 14
/ \ /
4 7 12
largest common BST exists at node : 10 of size 3
However, lol's solution gives output subtree rooted at 14 (of size 2). It depends what interviewer exactly asked for. To achieve above output, it's straight forward to get the solution in O(nm) time.
Well, there are basically 4 cases to handle:
Let, r1 = current node of 1st tree
r2 = current node of 2nd tree
Case 1 : r1->data < r2->data
2 subproblems to solve:
first, solve r1 and r2->left
second, solve r1->right and r2
Case 2 : r1->data > r2->data
similar
Case 3 : r1->data == r2->data
2 cases to consider here:
(a) current node is part of largest common BST
compute common subtree size rooted at r1 and r2
(b)current node is NOT part of largest common BST
2 subproblems to solve:
first, solve r1->left and r2->left
second, solve r1->right and r2->right
Why case (a) and (b) are different? Look at below 2 examples: ______________10______________
/ \
_______3______ ______14______
/ \ / \
0 ___6__ 12 18
/ \
4 7
\ \
5 8 ______________10______________
/ \
_______2______ 14______
/ \ \
1 ___6__ __18
/ \ /
4 7 16
\
8
largest common BST exists at node : 6 of size 4
Here, root (10) is not part of largest common BST ______________10______________
/ \
_______3______ ______14______
/ \ / \
0 ___6__ 12 18
/ \
4 7
\ \
5 8 ______________10______________
/ \
_______2______ 14______
/ \ \
1 ___5__ __18
/ \ /
4 7 16
\
8
largest common BST exists at node : 10 of size 3
Here, root (10) is part of largest common BST
Awesome Solution !!!!
Here is the code :
int countCommonNodes(node *head1,node *head2){
if(head1==NULL || head2 ==NULL){
return 0;
}
if(head1->data == head2->data){
return 1 + countCommonNodes(head1->left,head2->left) + countCommonNodes(head1->right,head2->right);
}
else{
return 0;
}
}
void findMaxSubBST(node *head1,node *head2,int *ans){
if(head1 == NULL || head2 == NULL){
*ans = max(*ans,0);
return ;
}
else if(head1->data > head2->data){
findMaxSubBST(head1->left,head2,ans);
findMaxSubBST(head1,head2->right,ans);
}else if(head1->data < head2->data){
findMaxSubBST(head1,head2->left,ans);
findMaxSubBST(head1->right,head2,ans);
}else{
*ans = max(*ans,countCommonNodes(head1,head2));
findMaxSubBST(head1->left,head2->left,ans);
findMaxSubBST(head1->right,head2->right,ans);
}
}
Overall nice solution and code as well.
However, I have a small doubt, do we need the second function "countCommonNode()" at all?
when current head1 == head2, recursively solve left and right? Isn't this enough?
Can someone please answer my doubt?
oops got it now.
When 2 nodes match, from then onwards processing will be different unlike the current function. So we definitely need another function.
nice solution...:)
but this will give the size of common bst's, how to find the nodes for that?
complexity seems to be exponentials ... is this the optimal solution ??.. so far i guess !!!
Do u think that : countCommonnodes() method check for real common BST nodes.What i mean is , a BST must have some internal and some external nodes. But above mentioned function counts for similar nodes no matter whether largest ans till now contains leaves or not. ans in above solution may contain internal nodes of both trees which satisfy BST property but what about leaves??
Correct me if i am wrong.
Do u think that : countCommonnodes() method check for real common BST nodes.What i mean is , a BST must have some internal and some external nodes. But above mentioned function counts for similar nodes no matter whether largest ans till now contains leaves or not. ans in above solution may contain internal nodes of both trees which satisfy BST property but what about leaves??
Correct me if i am wrong.
The code return both nodes and count:
struct item
{
TNode* node1, *node2;
int count;
}
;
item func(TNode* r1, TNode* r2)
{
if(r1 == NULL || r2 == NULL) { item it; it.node1 = NULL; it.node2 = NULL; it.count = 0; return it; }
if(r1->id < r2->id)
{
item i1 = func(r1, r2->left);
item i2 = func(r1->right, r2);
item it = i1; if(i1.count < i2.count) it = i2;
return it;
}
if(r1->id > r2->id)
{
item i1 = func(r1->left, r2);
item i2 = func(r1, r2->right);
item it = i1; if(i1.count < i2.count) it = i2;
return it;
}
item left = func(r1->left, r2->left);
item right = func(r1->right, r2->right);
item it = left; if(left.count < right.count) it = right;
if(left.node1 == r1->left && left.node2 == r2->left && right.node1 == r1->right && right.node2 == r2->right)
{
it.node1 = r1; it.node2 = r2;
it.count = left.count + right.count + 1;
}
return it;
}
int main()
{
TNode* r1 = initbst(); TNode* r2 = initbst(); r2->id = 100;
item it = func(r1, r2);
}
Time: O(nlogn)
void maxCommonBST(node* root1, node* root2, node* curRoot, node** comRoot, int curCount, int* totalCount)
{
if(root1&&root2)
{
if (root1->data==root2->data)
{
curCount+=1;
if(curRoot==0)
{
curRoot=root1; /*could be assigned to root2 also*/
}
maxCommonBST(root1->left,root2->left,curRoot,comRoot,curCount,totalCount);
maxCommonBST(root1->right,root2->right,curRoot,comRoot,curCount,totalCount);
if(curCount>(*totalCount))
{
*totalCount=curCount;
*comRoot=curRoot;
}
}
else if (root1->data<root2->data)
{
maxCommonBST(root1,root2->left,0,comRoot,0,totalCount);
}
else
{
maxCommonBST(root1,root2->right,0,comRoot,0,totalCount);
}
}
}
@anonymous: I don't think your solution is correct at all. how could you extract the STRUCTURE of tree from 2 BSTs just by their inorder traversal.
@codemonkey: Did you really feel it's a sound solution. Then pls explain.
3
/
2
/
1
inorder : 1-2-3
2
/ \
1 3
inorder : 1-2-3
1
\
2
\
3
inorder : 1-2-3
Now, if I give you first and last BST, output should be single node which is common (by dafault). How do you get it?
@anon:it can be done just use place holders like l for left r for right for all the intermediate null pointers while doing the inorder traversal...in ur case that wud be l1r2r3r and l1r2l3r
As I interpret this question as "finding the common subtree among given BSTs", we can do following steps:
1. make preorder traversal of each BST.
2. find largest common substring of 2 preorder traversals.
Here the assumption is that keys in each tree are unique. Using suffix tree, above problem can be solved in O(n) time. Otherwise, we could use DP that takes O(n^2).
another clarification: I use this definition for subtree (from wikipedia)
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T
If a subtree may exclude some of its descendants, then above approach fails.
Yes, I read the question. I never reply to a question without reading it (and trying to understanding to the best of my knowledge). Would you mind to elucidate me at which point I missed the original question? Thanks.
Just to clarify, I meant suffix tree can be used to find largest common substring problem(step 2). Though, suffix tree usually considers alphabet set to be ASCII chars, I don't see any problem to adapt it to BST where keys are integers. What's your thoughts/doubts here?
srry dude. i was too rude.
actually the question is asking for subtree that is common for both the tress. i.e. nodes orientation should be preserved in that subtree as shopno later pointed out.
secondly i guess its not kinda possible to code whole suffix tree stuff during the interview. i guess u better not mention it during the interview coz the very next thing he got gonna ask u to code the suffix tree LOL(my personal exp :P )
srry dude. i was too rude.
actually the question is asking for subtree that is common for both the tress. i.e. nodes orientation should be preserved in that subtree as shopno later pointed out.
secondly i guess its not kinda possible to code whole suffix tree stuff during the interview. i guess u better not mention it during the interview coz the very next thing he got gonna ask u to code the suffix tree LOL(my personal exp :P )
No problem :)
Thanks for your suggestion. I agree it's too hard to code complete suffix tree stuff (correctly) during an interview period. I agree with buried.shopno's idea. In his mentioned case, I think we could come up some recursive approach that would take O(n^2) time.
you both are gone mad.. how can you say that both tress are similar if preorder is same? check the above comments..
-----2
---1---3 (tree1)
----3
--2
-1 (All are left childs, tree2)
Tree1 and tree2 produce the same preorder but they are not same..
@swathi: before terming someone "mad" check out your understanding of BST definition. Your 2nd tree is NOT a BST.
FYI, BST serialization/deserialization can be done using only preorder traversal.
Sorry, I did a stupid mistake there. Both of the trees are VALID. But the preorder traversals are different :
tree 1 : 2 1 3
tree 2 : 3 2 1
Hence, max common is of size 1.
@lol u don't have to pay attention when a girl is talking about programming,just ignore her LOL
baghel and lol, i made a silly mistake in drawing the trees but that should be a common sense to graspe..
---3
--2-1 (tree1)
---3
--2
-1 (tree2)
both the trees has the same preorder.. so you can't tell that if preorder is same then trees are similar..
again :D.... Check out your definition of BST. Your first input is INVALID. How could 1 go to right of 3!
Rather finding if someone is wrong, it's always better to first think deeply, and re-check oneself. As I already told you that "BST serialization/ deserialization can be done using only preorder traversal" - did you ever try to understand why it holds?
I stand CORRECT. Your understanding is pretty wrong. For above case preorder gives "3-1-2". It says
3 is root
1 is left child of 3
2 < 3, so go to left, 2 > 1, so 2 is right child of 1
If you wanna challenge, give more complex examples.
First write a function that determines whether a tree is a subtree of another. Then recursively apply it on both trees: 1 subtree of 2 or 2 subtree of 1. If the function evaluates to false, do the same with left child of 1 with 2 and left child of 2 with 1 and same with right subtrees..
- Ashish Kaila June 22, 2011