3 ms·
Since no computational bound has been placed, this problem could be solved in n^2 by an insertion sort and keeping the list of numbers sorted in memory as they
by damienkatz 14y ago
Since no computational bound has been placed, this problem could be solved in n^2 by an insertion sort and keeping the list of numbers sorted in memory as they are received. Then the problem then boils down to encoding a list of sorted 8 digit decimal #s, where it's possible to insert new #s.
Since the #s are stored sorted and bounded in size, they can be encoded as deltas which will be more space efficient than storing absolute values. Now we just need to figure out the worst case encoding and will 1 million values fit?
- andrewcooke 14y agoi think that's the clearest answer i've seen. really, it's pretty much equivalent to the other answers, but at least for me it's by far the easiest to grasp. although i guess that may be because the idea is simply becoming familiar after reading the others. the best "high level" explanation, i think, is that you are compressing the sorted numbers, which are therefore not random, and so concerns about the incompressibility of random streams are completely irrelevant.
- mlvljr 14y agoOr, rather, this is about compressing random sets == compressing random arrays with w/o being order precise. Is the number of all possible distinct sets of 1 million 1..10^8 numbers less or equal to 2^(8 * 1024 * 1024)? And if yes, is there a way to transform the buffer from one intermediate state (representing the "not yet fully" received stream) into another utilizing a small amount of registers?
- eru 14y agoMerge sort would work better. But yes, the secret sauce is in the compression, not the sorting.