[dgacmu]

> Right out the gate: the numbers must be sorted.

But they don't. I hope you, as an interviewer, have the grace to learn when one of your interviewees points out your mistake. :-) Median is O(n), not nlogn

[dang]

Can you please make your substantive points neutrally, without being a jerk? There's no need for the latter, even if you're 100% correct.

[dgacmu]

Sorry - I really wasn't trying to be a jerk, but I do acknowledge that directly addressing the author is aggressive.

I was mostly trying to emphasize the importance of avoiding the negative experiences of people interviewing when the interviewer was wrong about something and won't flex, as exemplified in a couple of comments in this thread:

https://news.ycombinator.com/item?id=48839767

https://news.ycombinator.com/item?id=48840261

So to clarify my point in a more general way: We _all_ have some concepts wrong in our head, and we should all strive to be not only graceful but delighted if an interviewee is correct when we're wrong.

[dang]

I appreciate the reply! and yes, that's a much better way to express the point.

(Btw this is an interesting phenomenon - I call it the rebound effect: https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...)

[mcmoor]

With worst case of O(n^2) though? In hindsight it should be possible, since if we use insertion sort, we also get best of O(n) and worst of O(n^2). Though quick select do have average O(n).

[dgacmu]

Depends if you're talking theory or practice. introselect is worst case O(n) but a lot of implementations implement it with avg case O(n) and worst case O(log n). Median of medians is worst case O(n) but it's slow so mostly avoided.

[dgacmu]

* introselect implementation often worst case n log n, typo