alejandragos
BAN USER
Questions (1)
Comments (5)
Reputation 15
- 0of 0 votes
AnswersGiven a sorted array of size N and a sorted array of size M+N, merge the first array into the second preserving order. There is enough space in the second array to hold all elements from the first one.
- alejandragos in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote
I think that is how I solved the problem, but in this case I think starting from the back of the arrays does it with less complication in the code and with better performance.
- alejandragos March 09, 2013Comment hidden because of low score. Click to expand.
0
of 0 vote
yeah! I see that ... now :( oh well
- alejandragos March 09, 2013Comment hidden because of low score. Click to expand.
0
of 0 vote
thanks, I now see that the problem has to solved starting from the end of the arrays which makes things way easier
- alejandragos March 09, 2013Comment hidden because of low score. Click to expand.
-1
of 1 vote
I know that it's the last step of a merge sort, but it was not allowed to used an extra structure. So the insert made it complicated. Can you provide solutions for this? thanks.
- alejandragos March 09, 2013Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
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?
- alejandragos March 09, 2013Yes 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.