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

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 a day ago | parent [-]

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 20 hours ago \| parent [-]
		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 2 days ago | parent | prev [-]

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 a day ago | parent [-]

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 a day ago \| parent [-]
		* introselect implementation often worst case n log n, typo