<story><title>Sorting 1 million 8-digit decimal numbers in 1MB of RAM </title><url>http://stackoverflow.com/questions/12748246/sorting-numbers-in-ram</url></story><parent_chain><item><author>ChuckMcM</author><text>This was a Google interview question for a while (I know I got it as one) I think it has since made it to the banned question list. The &apos;trick&apos; was, as answer #2 elided, to use bits to store the fact that you had observed the number and then you could dump them back in sorted order.&lt;p&gt;So imagine you have a bit field where &apos;one bits&apos; indicate you have seen the number and &apos;zero bits&apos; indicate you haven&apos;t. And you compress it with run-length encoding.&lt;p&gt;Your initial data structure is &apos;99999999:0&apos; (all zeros, haven&apos;t seen any numbers) and then lets say you see the number 3,866,344 so your data structure becomes &apos;3866343:0,1:1,96133654:0&apos; as you can see the numbers will always alternate between number of zero bits and number of &apos;1&apos; bits so you can just assume the odd numbers represent 0 bits and the even numbers 1 bits. This becomes (3866343,1,96133654)&lt;p&gt;Anyway, as you get numbers you will split and coalesce the bit space until you&apos;ve either seen all numbers (0, 99999999) or you run out of memory because a hacker has sent you only the even numbers from the space.&lt;p&gt;Its a clever &apos;math trick&apos; which explores how you think about numbers (are they a thing or a representation). But I never thought it really gave a good indication of whether or not you would be a good candidate for the company.</text></item></parent_chain><comment><author>ChuckMcM</author><text>So as it turns out, this is wrong. Several folks have mentioned that in that the original Google interview question is &apos;sort the numbers&apos; / &apos;remove duplicates&apos; and the solution is to create a bitmap in a disk file to do a single pass sort. This question mixes that up a bit and my particular bitmap solution fails to meet the criteria of staying under a MB of memory.&lt;p&gt;With all the discussion I decided to code up a quick version in perl. The code is pretty straight forward, start with the tuple (99999999,0) and on each number do one of three actions:&lt;p&gt;1) Break the number representing a string of zeros into two segments.&lt;p&gt;2) Extend the length of an existing region of one bits.&lt;p&gt;3) Collapse two regions of one bits separated by a single zero bit.&lt;p&gt;Now the two key to the reasons it doesn&apos;t work are that one, it takes two 32 bit numbers to identify non-adjacent numbers, and two, for a uniform distribution random number generator the ratio of a million numbers to a space of 100 million means that most of the numbers won&apos;t be adjacent. So each 1 bit will cost 8 bytes to store. A million numbers * 8 bytes is 8 million bytes (7.6MB if you use 2^20th as 1MB). Its fun watching the algorithm because it gets slower and slower (its doing a linear search of segments to insert &apos;bits&apos; and memory goes up and up, until you have about 50M uniques and then it starts getting faster and faster again as it collapses more and more segments.&lt;p&gt;Storing it on disk with an uncompressed bitmap, runs in O(n) time, and of course you 12,500,000 bytes, just about 12MB (to count multiples you need to multiply that by the number of bits you want to reserve per-number) but doing it in memory only requires a better compression algorithm than simple run-length encoding.</text></comment>
<story><title>Sorting 1 million 8-digit decimal numbers in 1MB of RAM </title><url>http://stackoverflow.com/questions/12748246/sorting-numbers-in-ram</url></story><parent_chain><item><author>ChuckMcM</author><text>This was a Google interview question for a while (I know I got it as one) I think it has since made it to the banned question list. The &apos;trick&apos; was, as answer #2 elided, to use bits to store the fact that you had observed the number and then you could dump them back in sorted order.&lt;p&gt;So imagine you have a bit field where &apos;one bits&apos; indicate you have seen the number and &apos;zero bits&apos; indicate you haven&apos;t. And you compress it with run-length encoding.&lt;p&gt;Your initial data structure is &apos;99999999:0&apos; (all zeros, haven&apos;t seen any numbers) and then lets say you see the number 3,866,344 so your data structure becomes &apos;3866343:0,1:1,96133654:0&apos; as you can see the numbers will always alternate between number of zero bits and number of &apos;1&apos; bits so you can just assume the odd numbers represent 0 bits and the even numbers 1 bits. This becomes (3866343,1,96133654)&lt;p&gt;Anyway, as you get numbers you will split and coalesce the bit space until you&apos;ve either seen all numbers (0, 99999999) or you run out of memory because a hacker has sent you only the even numbers from the space.&lt;p&gt;Its a clever &apos;math trick&apos; which explores how you think about numbers (are they a thing or a representation). But I never thought it really gave a good indication of whether or not you would be a good candidate for the company.</text></item></parent_chain><comment><author>jules</author><text>It is extremely unlikely that you&apos;ll be able to sort a random sequence of 1 million 10 digit numbers like that, or ANY method for that matter, unless the particular sequence is highly compressible. You won&apos;t even be able to store the answer in the average case. You&apos;ll need 10^6*lg(10^10) bits to store the raw input, from which you&apos;ll be able to save about lg(10^6!) bits because it&apos;s sorted. That comes out to more than 1.7 megabytes.&lt;p&gt;Edit: the exact amount of bits necessary is ceil(log_2((1e10+1e6-1) choose 1e6)), which is ~1.756 megabytes.&lt;p&gt;Edit edit: see udiv&apos;s comment below: that 1e10 should be 1e8 of course.</text></comment>