31–40 of 63 posts
Its easy. 1kk numbers fit almost whole 1MB. So most of the numbers from the range will be there if we assume normal distribution. So we need to compress the data first in a way we can still count it. So we take a sinus function and mark multipliers where a number does not fit sinus. So we spare 0,5MB of RAM at least. Then we iterate the range, multiply sinus and output sorted numbers. Rest of the RAM can be used for…
I'm vaguely thinking set a TCP sequence number according to each number you want to sort, then use the out of order capability of TCP/IP to do it for you...
The accepted solution is some wizardry that works because 1M (just) fits into 1MB... I wonder if in the intervening years 1M hasn't become 2M or more? I'm not really smart enough to come up with such a solution, I'd probably just try and find a way to plug something in between the input or output Ethernet port that has a bit more memory.
1M (ordered) list of numbers requires 3.5MB of RAM(10^6*log_2(10^8) bits). The theoretical lower bound to store unordered numbers is 0.96MB(log_2(comb(10^8+10^6-1, 10^6)) bits)
Earlier quoted context omitted.
You can't because there's not enough RAM to hold all the numbers. So you'd be sorting the input as it arrives, yes, and then at some point you'd run out of RAM and have to stop processing new numbers.
There's enough RAM to hold all the numbers. You just have to invent the representation to store all the numbers in the available RAM. Naive representation using 27 bits per number won't hold them all indeed. But if you would store them ordered and store difference rather than number using variable bit encoding, it would take less space. Just simple math: imagine that you have to store numbers 0, 100, 200, ..., 99 999…
Example starting your base as zero if the first number 100 you can store that in 1 byte, use the high bit to flag a larger number so if the next number is say 10000 you can store it in two bytes. But let's say the next number is 3000, you need to update the first delta, insert the new number and continue on. You probably can store most numbers that way.
I'm a fan of the actual (in-RAM, no tricks) problem and its variants. The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 ), but I've not seen a good writeup of an actual algorithm. My personal favorite variant of this is sorting 1M 32-bit integers using 2MiB of RAM. This is possible and I coded it up for fun a few years ago. Here's the specific…
Earlier quoted context omitted.
I consider it not in-RAM. There's another variant, iirc sorting telephone numbers, in "Programming Pearls," but it requires a different approach.
The classic programming interview version of this question is to infer from "telephone numbers" that they're all unique and so you just allocate the provided memory as a big bitfield, mark all the numbers you have in your input list, then scan through and read them back in order.
Might you or someone else have a link that states the whole interview question?
I'm a fan of the actual (in-RAM, no tricks) problem and its variants. The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 ), but I've not seen a good writeup of an actual algorithm. My personal favorite variant of this is sorting 1M 32-bit integers using 2MiB of RAM. This is possible and I coded it up for fun a few years ago. Here's the specific…
Why is the entropy of the sorted list smaller?
I'm a fan of the actual (in-RAM, no tricks) problem and its variants. The entropy of the sorted list is 0.96MiB so it is theoretically possible (see https://news.ycombinator.com/item?id=4679756 ), but I've not seen a good writeup of an actual algorithm. My personal favorite variant of this is sorting 1M 32-bit integers using 2MiB of RAM. This is possible and I coded it up for fun a few years ago. Here's the specific…
Is it possible for you to share the code? Still don't quite get how that encoding related/helps in sorting the numbers.
Earlier quoted context omitted.
The classic programming interview version of this question is to infer from "telephone numbers" that they're all unique and so you just allocate the provided memory as a big bitfield, mark all the numbers you have in your input list, then scan through and read them back in order.
Interesting is this a counting sort then? Might you or someone else have a link that states the whole interview question?