## Amazon Interview Question for Software Engineer / Developers

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

1. Create two sorted arrays by inorder traversing two trees - linear time
2. Merge two sorted arrays - linear time
3. Build BST from sorted array

Last step can be done in linear time by taking root node from the middle of array, and calling taking left and right chilfren recursively from left and right sub-arrays.

So the overall complexity is O(n)

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

hmm, I even think that last step will be logN, so the complexity is O(N) + O(logN)

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

I might be wrong but I think each insert operation takes O(logn) and hence for n elements (n1 + n2) to be inserted in the new BST it takes O(n1+n2)log(n1+n2) ?

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

O(n) is correct. Think of mergesort, the complexity is O(nlogn) because of the merge operation(which is O(n)). In this case, you are creating a BST using something similar to mergesort but without the merge operation, so compexity is O(n).

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

@gevorgk : Question says binary tree not BST so inorder traversal will not guarantee you a sorted result...

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

Question says a very few things about the tree. It doesn't say wether the tree is sorted, wether the resulted tree have to be balanced etc. So assuming taht tree is not BST and the resulting tree shall not be balanced, the solution is just att the root of one tree as child to any leaf of another. I don't think that amazon could ask such a stupid question.

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

Is this right?

Do inorder traversal of both lists and store result in additional lists which will create 2 lists and then use merge sort to sort them. Time complexity will be O(nlogn).

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

Forgot to add then do insert operation for each node of the list to recreate the merged tree

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

but this approach without any preorder/postorder traversal, the tree formed eikk not be a balanced. rather it will be a right oriented subtree where each node with be right child of its parent

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

Two binary search trees: T1 & T2

- I choose to break and insert T2 in T1.
- Find the max & min of T2
- Now run a insert in T1 with range (min, max) and if you are able to reach a leaf node then stick T2 as child of that leaf node
- If you are not able to find such a leaf noe and the search terminates at some internal node (whose value should be greater than 'min' and less than 'max') then
- break T2 into root, left sub-tree, right sub-tree
- insert T2's root in T1
- call recursively for left sub-tree
- call recursively for right sub-tree

Best case running time : O(log n1) + O(log n2)
Worst case - didnt compute

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

code?

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

Worst case will be N1logN2 (in case if you stuck in root node of the tree)

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

I dont know if you can stick a root of a tree as a child of a leaf node just like that. If you do so , its possible that the resulting tree is not a BST.

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

Why not we directly traverse each node of T2 using inorder and insert it in T1 using binary tree creation method?
its simples isnt it?

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

It's VERY simple, but running time will be N1logN2 :))

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

@ Swarp..

I feel its correct ...

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

its binary tree...not a bst...
make root of one the child of other

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

Here tree is ordinary binary tree and not the binary search tree. So we can attach the second tree to any of the node in which left child or right child is null.
Here assume that we will attach the second tree as a left child in first tree.

tree_node_type * merge_tree(tree_node_type *t1 , tree_node_type *t2)
{
tree_node_type *temp;
if(t1==NULL)
return t2;
if(t2==NULL)
return t1;
temp=t1;
while(temp->left)
temp=temp->left;

temp->left=t2;

return t1;
}

for complete c program see
"goursaha.freeoda.com/DataStructure/MergeTwoTree.html"

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

Assume the trees are BST. We are not told anything else, we dont know how balanced they are. How many nodes there are. To merge them, why not just do an inorder on one tree and insert on the second tree as we go?
Yes the inorder will give you sorted elements but by inserting directly to the second tree, you should get a fairly good result meaning, that we wont affect the second tree as much...

I dont know, I see so many complicated solutions, using extra structures, but I still dont see how those solutions are good if we are not given more information about the trees.

I know the big O is bad for this solution, since you have O(Nx log(N+M)) or something like that. But at the same time we are not using any extra space.... what do you think? I just want to know.

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.