2 ms·
After 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 d
by thrown_22 4y ago
After 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.