Hacker News Reader

I like these a lot! I'm seeing them less as "interview questions", which they'd be terrible as, but as "annoy your friends questions" after you've all had a couple drinks.

One I heard a while back: "You have a list consisting of every college student in the US. What's the fastest way to sort them by age in years?"

View on HN

Other than sorting by birth date, what's your intended solution to this?

Almost all of the students are going to be somewhere between 17 and 23 years old, so you first do one pass as a bucket sort for each of those seven values. Then sort the remaining students however you want. While it's technically still O(n log n), almost everyone is sorted in that first pass, so it's practically indistinguishable from O(n).

That is actually a decent optimization. If you know the final cardinality, you just create that many buckets, and drop records in it. Not unlike how histograms work.

Reply on news.ycombinator.com