Hacker News Reader

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.