4 ms·

It reminds me of the classic interview problem, attributed to Google: sort 1 million 32 bit integers (provided as a stream) using 2 megabytes of memory. Most pe

It reminds me of the classic interview problem, attributed to Google: sort 1 million 32 bit integers (provided as a stream) using 2 megabytes of memory. Most people's first instinct is that it can't be done, you need almost 4 megabytes to store the input, but of course it can be, you keep the sorted list in compressed form. I haven't found a really good writeup, most of the hits on Google (SO, earlier HN stories) fail to get the answer.

tyingq 5y ago
Guido van Rossum's answer, of course with Python: http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html http://neopythonic.blogspot.com/2008/10/sorting-million-32-b... It sounds like "break up into smaller sorted sets, then do a merge sort". Does the Google interview question allow for temp file storage?
- raphlinus 5y ago
  There are two versions of the question. One allows external storage (Guido's answer and the top hit on SO), the other does not.
sltkr 5y ago
I think there are two difficulties here. 1. How to even represent 1,000,000,000 sorted integers in only 2 megabytes, which means you can use (slightly more than) 2 bytes per integer. The central observation is that the sum of the deltas is no more than 4294967296. 4294967296 / 1000000 = 4295 which is about 13 bits, so it seems like it should be possible, but it's not easy. For example, if you use a standard variable length encoding where the highest bit indicates continuation, you would have 7 data bits per byte, but you could have 743,665 times 128 and 256,335 times 16384, which would require 743,665*2 + 256,335*3 = 2,256,335 bytes, which is slightly over 2 megabyte. If you use the first two bits of the initial byte (so that K bytes encode 8*K - 2 bits). You could have 740,749 times 64 259,251 times 16384, for a total of 259251*3 + 740749*2 = 2,259,251 bytes, slightly worse even. With 1 continuation bit per nibble the math similarly doesn't work out. So this is starting to look, if not impossible, at least very hard. 2. Imagine that you could represent 1,000,000 sorted integers in 2 megabytes somehow. Then the next problem is to actually create such a sorted sequence from the input. - Insertion sort works, but O(N^2) time complexity is not great with a million elements. - Quick sort doesn't work since you'd start with an unsorted array which you cannot represent in memory. - Heap sort doesn't work because it requires random access to the array, which doesn't work with a variable-length encoding. - Merge sort works in the beginning, but you need temporary space equal to the size of your input, so towards the end you're in trouble. I think you could make merge sort work if the requirement is "output the elements in sorted order" rather than actually constructing a sorted representation of the array. In that case, you could create sorted sequences of the first 500,000, 250,000, 125,000 etc. elements, and do a 20-way merge in the end, which is O(N log N) overall. This is still somewhat tricky because the average delta of e.g. 500,000 elements can be twice as large as for the overall array, so you might need slightly more space to encode it, so we would need a really efficient compression scheme to make this work. All in all I'm gravitating towards: this problem isn't generally solvable under the given constraints. With 3 megabytes I think the scheme outlined above works.
- raphlinus 5y ago
  It's doable. First, you use a Golomb coding for the deltas. Tuning the parameters just right, you can get it to fit inside your budget with a little room to spare. Then, to get reasonably good time complexity, you use that extra space as a scratch buffer - read in a chunk of input, sort in place (heapsort is good for worst-case time complexity), and merge with the compressed stream. It's not simple to implement, but it does work.
  - GistNoesis 5y ago
    Can you explain how you merge a compressed sorted stream with the sorted chunk, to obtain a bigger compressed stream (without extra memory, or quadratic complexity) ? I can see a solution with memory usage : size of( compressed sorted stream ) + size of( compressed sorted chunk ) + size of(compressed stream merge output) This would work but it means you need to fit your compressed sorted stream in less than a single MB instead of 2MB (and I'm ignoring memory fragmentation problems)
    - raphlinus 5y ago
      There are a bunch of ways to do this. One of the more straightforward is to use a temporary buffer big enough to hold both the new values and the existing stream, and start by shifting the existing stream to be right aligned (using memmove or the equivalent). Then read bits from the old stream while writing bits into the new stream. Using Elias-Fano coding (which I believe is an instance of Golomb coding), the write position will never overtake the read position, so the merge can be done in-place.
      - GistNoesis 5y ago
        Thanks. I think I understood it now : https://news.ycombinator.com/item?id=27553076 https://news.ycombinator.com/item?id=27553076 In my solution though when the extra temporary buffer is very small,in the worst case, we need to make sizeof(compressedStream)/sizeof(temporaryBuffer) memmove which can potentially make the algorithm quadratic.
ChrisLomont 5y ago
When that problem came out I solved it quickly (it was 1 million 8 digit numbers in sorted in 1MB of RAM, which I think is the original problem that gained notoriety) with basically arithmetic compression of the delta stream, since the number of possible states sits decently inside the required RAM. I also saw I can sort it it using zero bytes of storage using a lot of code :) Think nested switches that eventually print a lot of numbers.
tastyface 5y ago
Er... is it just me, or is this a terrible interview question? Assuming no external storage, I can imagine spending a few hours working out this problem for fun, but to do it in 45 minutes on a whiteboard seems exceptionally difficult if you're not familiar with it already. (Or is this one of those "let's talk it through, you don't need to arrive at a perfect answer" deals?) I could be wrong. Maybe I should just sit down and try it, but timed problems stress me out in general, even if nothing's at stake.

tyingq 5y ago

Guido van Rossum's answer, of course with Python: http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html http://neopythonic.blogspot.com/2008/10/sorting-million-32-b... It sounds like "break up into smaller sorted sets, then do a merge sort". Does the Google interview question allow for temp file storage?

raphlinus 5y ago
There are two versions of the question. One allows external storage (Guido's answer and the top hit on SO), the other does not.

sltkr 5y ago

I think there are two difficulties here. 1. How to even represent 1,000,000,000 sorted integers in only 2 megabytes, which means you can use (slightly more than) 2 bytes per integer. The central observation is that the sum of the deltas is no more than 4294967296. 4294967296 / 1000000 = 4295 which is about 13 bits, so it seems like it should be possible, but it's not easy. For example, if you use a standard variable length encoding where the highest bit indicates continuation, you would have 7 data bits per byte, but you could have 743,665 times 128 and 256,335 times 16384, which would require 743,665*2 + 256,335*3 = 2,256,335 bytes, which is slightly over 2 megabyte. If you use the first two bits of the initial byte (so that K bytes encode 8*K - 2 bits). You could have 740,749 times 64 259,251 times 16384, for a total of 259251*3 + 740749*2 = 2,259,251 bytes, slightly worse even. With 1 continuation bit per nibble the math similarly doesn't work out. So this is starting to look, if not impossible, at least very hard. 2. Imagine that you could represent 1,000,000 sorted integers in 2 megabytes somehow. Then the next problem is to actually create such a sorted sequence from the input. - Insertion sort works, but O(N^2) time complexity is not great with a million elements. - Quick sort doesn't work since you'd start with an unsorted array which you cannot represent in memory. - Heap sort doesn't work because it requires random access to the array, which doesn't work with a variable-length encoding. - Merge sort works in the beginning, but you need temporary space equal to the size of your input, so towards the end you're in trouble. I think you could make merge sort work if the requirement is "output the elements in sorted order" rather than actually constructing a sorted representation of the array. In that case, you could create sorted sequences of the first 500,000, 250,000, 125,000 etc. elements, and do a 20-way merge in the end, which is O(N log N) overall. This is still somewhat tricky because the average delta of e.g. 500,000 elements can be twice as large as for the overall array, so you might need slightly more space to encode it, so we would need a really efficient compression scheme to make this work. All in all I'm gravitating towards: this problem isn't generally solvable under the given constraints. With 3 megabytes I think the scheme outlined above works.

raphlinus 5y ago
It's doable. First, you use a Golomb coding for the deltas. Tuning the parameters just right, you can get it to fit inside your budget with a little room to spare. Then, to get reasonably good time complexity, you use that extra space as a scratch buffer - read in a chunk of input, sort in place (heapsort is good for worst-case time complexity), and merge with the compressed stream. It's not simple to implement, but it does work.
- GistNoesis 5y ago
  Can you explain how you merge a compressed sorted stream with the sorted chunk, to obtain a bigger compressed stream (without extra memory, or quadratic complexity) ? I can see a solution with memory usage : size of( compressed sorted stream ) + size of( compressed sorted chunk ) + size of(compressed stream merge output) This would work but it means you need to fit your compressed sorted stream in less than a single MB instead of 2MB (and I'm ignoring memory fragmentation problems)
  - raphlinus 5y ago
    There are a bunch of ways to do this. One of the more straightforward is to use a temporary buffer big enough to hold both the new values and the existing stream, and start by shifting the existing stream to be right aligned (using memmove or the equivalent). Then read bits from the old stream while writing bits into the new stream. Using Elias-Fano coding (which I believe is an instance of Golomb coding), the write position will never overtake the read position, so the merge can be done in-place.
    - GistNoesis 5y ago
      Thanks. I think I understood it now : https://news.ycombinator.com/item?id=27553076 https://news.ycombinator.com/item?id=27553076 In my solution though when the extra temporary buffer is very small,in the worst case, we need to make sizeof(compressedStream)/sizeof(temporaryBuffer) memmove which can potentially make the algorithm quadratic.

ChrisLomont 5y ago

When that problem came out I solved it quickly (it was 1 million 8 digit numbers in sorted in 1MB of RAM, which I think is the original problem that gained notoriety) with basically arithmetic compression of the delta stream, since the number of possible states sits decently inside the required RAM. I also saw I can sort it it using zero bytes of storage using a lot of code :) Think nested switches that eventually print a lot of numbers.

tastyface 5y ago

Er... is it just me, or is this a terrible interview question? Assuming no external storage, I can imagine spending a few hours working out this problem for fun, but to do it in 45 minutes on a whiteboard seems exceptionally difficult if you're not familiar with it already. (Or is this one of those "let's talk it through, you don't need to arrive at a perfect answer" deals?) I could be wrong. Maybe I should just sit down and try it, but timed problems stress me out in general, even if nothing's at stake.