28 ms·
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 pro
by apricot 2mo 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.
- salamanderman 2mo agoI 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.
- kccqzy 2mo agoOr it could just be someone who uses C++ instead of Python as their interview language. The std::nth_element is in the standard library.
- BobbyTables2 2mo agoOr 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…
- srean 2mo agoIn 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.
- kccqzy 2mo agoJust 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.