3 ms·
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 cou
by hwayne 7y ago
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?"
- amptorn 7y agoOther than sorting by birth date, what's your intended solution to this?
- hwayne 7y agoAlmost 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).
- sethammons 7y agoThat 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.