Hacker News new | ask | show | jobs
by apricot 20 days ago
In addition to the points listed, it gives the algorithm nerds the opportunity to show their overqualification by whipping out the O(n) median algorithm and proving that it works in linear time.
3 comments

I almost tanked an interview, and luckily turned it around, when the interviewer had never heard of QuickSelect and thought I was insane when I started writing it.
Or do a bucket sort on 32bit integers for worst case O(n) time, not O(n^2)

Only half kidding…

Using just 16GB RAM for a task is practically resource-constrained programming these days…

In my interview, several decades ago, a binary search over the bitwise representation of integers is the solution that I came up with. To the interviewers credit, who was caught by surprise by a solution he had not anticipated, he played along very sportily. He was very intrigued and happy that we came up with a solution he hadn't encountered.

Later I felt stupid after reading about quick select.

Just do four bucket sorts, once on each byte of the 32-bit integer. (Bucket sorts are stable sorts.) I benchmarked this and it was faster than quick sort.
Or it could just be someone who uses C++ instead of Python as their interview language. The std::nth_element is in the standard library.