5 ms·

Am I missing something, or couldn't you just merge the lists like you would in merge sort? Begin with a pointer at the start of each list, find the minimum of

Am I missing something, or couldn't you just merge the lists like you would in merge sort? Begin with a pointer at the start of each list, find the minimum of the elements being pointed at and increment that pointer, until all pointers are at the end of their respective lists. You could possibly even do it in place. That was my first thought anyway.

jaredsohn 9y ago
> find the minimum of the elements being pointed at Can you describe how you would do this and talk about how it would impact the time complexity of the algorithm?
- unsatchmo 9y ago
  You have to do K comparisons unless you keep track of the ordering of the other K-1 indices every time you pick a new element. Keeping a heap makes this log(K), yielding a KNlog(K) instead of K^2N. The naive solution is probably better when the number of lists to merge is small.
- btschaegg 9y ago
  I would guess the time complexity is the crux with this issue: Without knowing the nature of what the algorithm is used for in practice, you're left guessing. If you assume continuous memory "lists", cheap comparisons and a relatively small set of lists, you're not necessarily wrong to pick a brute-force approach, since maintaining the heap will result in much bigger constant factors in the complexity formula (even due to prefetching and so on). It's basically the same problem that peeks its head in every std::vector vs linked list discussion (and it's really amazing how many items you need before std::vector ceases to be a good pick for almost any problem).
- deleted 9y ago
  [deleted]
hendzen 9y ago
"find the minimum of the elements being pointed at" - doing that efficiently (e.g. with a heap) is the 'trick' to the problem.
- Vendan 9y ago
  Nah, the trick is knowing that merging and then sorting isn't the best way.
deleted 9y ago
[deleted]
Karliss 9y ago
It can be done on O(nk log k) if you always merge two shortest list. If all the lists have length k initially it can be easily done with couple of loops as all the lists will have the same length - n in the beginning, 2n after fist iteration, 4n after second.
- Karliss 9y ago
  Here is a quick implementation https://gist.github.com/karliss/ebc27b0b2baa3e6fc0f50fadda733554 https://gist.github.com/karliss/ebc27b0b2baa3e6fc0f50fadda73...
urgoroger 9y ago
This is correct, and I think it's mentioned in the article. I think this is probably what most people would think of too rather than the heap based solution. Using the heap solution also requires you to know how to use a heap in whatever language your interviewing in, or you could implement one (which would probably a lot more effort), so I prefer this one. EDIT: Ah, I didn't read your comment carefully enough. I thought you were referring to a divide and conquer approach when you meant 'like merge sort', where you the list of lists in half for each recursion, the recombine the sorted halves using a standard merge sort list merge. What you describe is basically the same as the solution given by the author. However, you don't give a way to find the minimum pointer, in the case of the author, a heap is used. Using a more naive data structure/algorithm (e.g. just finding the min over all pointers every time) will probably give worse asymptotic complexity than using a heap to maintain the least element

jaredsohn 9y ago

> find the minimum of the elements being pointed at Can you describe how you would do this and talk about how it would impact the time complexity of the algorithm?

unsatchmo 9y ago
You have to do K comparisons unless you keep track of the ordering of the other K-1 indices every time you pick a new element. Keeping a heap makes this log(K), yielding a KNlog(K) instead of K^2N. The naive solution is probably better when the number of lists to merge is small.
btschaegg 9y ago
I would guess the time complexity is the crux with this issue: Without knowing the nature of what the algorithm is used for in practice, you're left guessing. If you assume continuous memory "lists", cheap comparisons and a relatively small set of lists, you're not necessarily wrong to pick a brute-force approach, since maintaining the heap will result in much bigger constant factors in the complexity formula (even due to prefetching and so on). It's basically the same problem that peeks its head in every std::vector vs linked list discussion (and it's really amazing how many items you need before std::vector ceases to be a good pick for almost any problem).
deleted 9y ago
[deleted]

hendzen 9y ago

"find the minimum of the elements being pointed at" - doing that efficiently (e.g. with a heap) is the 'trick' to the problem.

Vendan 9y ago
Nah, the trick is knowing that merging and then sorting isn't the best way.

deleted 9y ago

[deleted]

Karliss 9y ago

It can be done on O(nk log k) if you always merge two shortest list. If all the lists have length k initially it can be easily done with couple of loops as all the lists will have the same length - n in the beginning, 2n after fist iteration, 4n after second.

Karliss 9y ago
Here is a quick implementation https://gist.github.com/karliss/ebc27b0b2baa3e6fc0f50fadda733554 https://gist.github.com/karliss/ebc27b0b2baa3e6fc0f50fadda73...

urgoroger 9y ago

This is correct, and I think it's mentioned in the article. I think this is probably what most people would think of too rather than the heap based solution. Using the heap solution also requires you to know how to use a heap in whatever language your interviewing in, or you could implement one (which would probably a lot more effort), so I prefer this one. EDIT: Ah, I didn't read your comment carefully enough. I thought you were referring to a divide and conquer approach when you meant 'like merge sort', where you the list of lists in half for each recursion, the recombine the sorted halves using a standard merge sort list merge. What you describe is basically the same as the solution given by the author. However, you don't give a way to find the minimum pointer, in the case of the author, a heap is used. Using a more naive data structure/algorithm (e.g. just finding the min over all pointers every time) will probably give worse asymptotic complexity than using a heap to maintain the least element