alt Hacker News> 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
Replies
mcmoor • today at 5:28 AM
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).
➕ show 1 reply
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.