3 ms·
On my laptop generating it takes ~1s and sorting takes ~280ms. As always, dependent on the power of the machine running things.
by vlovich123 4y ago
On my laptop generating it takes ~1s and sorting takes ~280ms. As always, dependent on the power of the machine running things.
- thrown_22 4y agoAfter thinking about it for a while, the reason why it was a hard problem back then is that the payroll wouldn't fit in memory and you'd need to do a sort on disk. In this day and age it would be like trying to sort 100 TB of data. Not a hard problem, but not exactly something you do daily either. And still dreadfully slow since you need to use disk memory while copying everything over. A more modern version of the question would be: >You have a list of integers, in random order, that is 20 times larger than the hard drive you have on your work station and 1,000 times larger than your work station ram....
- vlovich123 4y agoNaw. Sorting is a total waste here. I can read off an "infinite" amount of records of the wire with O(1) space usage and O(n) result. Even back then. Look at my radix sort solution: https://news.ycombinator.com/item?id=32684017 https://news.ycombinator.com/item?id=32684017 The intent behind the problem in the textbook is fine - think non-linearly about the problem. Just the example used has a trivial solution not mentioned (i.e. option 5).
- thrown_22 4y agoYes, that's why I changed it to having a list of arbitrary integers. You're also assuming integer ages when a more natural comparison would have date of birth. Which has 365 times the number of buckets. Something that was again problematic to fit into a 1980s memory.