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

- gevorgk on May 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gevorgk on May 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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) ?

- swarp on May 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- cubic on May 23, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- AG on May 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gevorgk on May 27, 2010 | Flag
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).

- Anonymous on May 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on May 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anirban.datta.24 on March 13, 2012 | Flag
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

- Anonymous on May 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

code?

- NewStart on May 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gevorgk on May 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on May 20, 2010 | Flag
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?

- Anonymous on May 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gevorgk on May 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ Swarp..

I feel its correct ...

- Div on May 21, 2010 | Flag Reply
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

- confused on May 21, 2010 | Flag Reply
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"

- Anonymous on May 24, 2010 | Flag Reply
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.

- alejandragos on March 09, 2013 | 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