[przemelek]

yeah, but in real world when this kind of problem will need to be solved people will most probably sort O(NlogN), or use priority queue O(NlogK), or even will go with something like O(N*K), almost no one will go with O(N) algo and because usually N and K are rather small and this code will not be called too often time complexity may be ignored. Still any solution shorter than O(N) will be called inefficient. And in real world they will know N and K from this what kind of problem they are solving, and this will not be hidden in mist of abstraction with assumption that "candidate should ask".

[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.

[Jorge1o1]

Moreover, with the micro-optimized SIMD quicksort algos that are perennially cropping up on this website... I would be willing to bet that "sort and take first N" is objectively faster than my crappy Python implementation -- even if it is linear time.