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 2 days ago | parent | next [-]

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.

▲

BobbyTables2 2 days ago | parent | prev | next [-]

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…

	▲	srean a day ago \| parent \| next [-]
		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.
	▲	kccqzy a day ago \| parent \| prev [-]
		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.

▲

kccqzy 2 days ago | parent | prev [-]

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.