Re:Amazon software engineer interview
by SonOfLilit on Friday July 08, 2016 @08:28PM
(#12059485)
Ah, some googling got me here:
http://www.geeksforgeeks.org/merge-k-sorted-arrays/
Merge k sorted arrays. Obviously that's a job for a min heap (not heap sort though, just a heap to keep the values of the next item in each array).
Sorry I was not very precise there. Exact question is to merge K sorted arrays, size N each. A natural extension of that problem, is to have K streams.
First part can be solved with an extension of O(n+m) solution you proposed, but when it comes to streaming, Heap works better, with the same complexity, because you don't have to know the size of the arrays in advance: https://discuss.leetcode.com/topic/2780/a-java-solution-base...
Sorry, I'm confused. I love heaps, but... what's wrong with this simple O(n+m) time and space solution, that I can easily prove is the theoretical limit (because the output size is O(n+m))?