[grogers]

I mean, in the real world you probably use a library method. If I were an interviewer I would not be expecting the candidate know about median-of-medians (O(n) worst case). I wouldn't even expect they know a-priori about quickselect (O(n) avg). But I don't think it's unreasonable that given a few hints, a candidate could understand and implement quickselect in 30 mins. Most people know about quicksort already, and quickselect is not very different. You can even give them the partition and select_pivot function at the start and then if there's time have them fill those in. In the rare situation they haven't even heard of quicksort, you can even write the shell of the algorithm for them, and have them adapt it to quickselect.

Even then, all thats probably a bonus - a priority queue implementation, or many other possible solutions are probably good enough for me.