2 ms·
> 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 o
by dgacmu 3mo ago
> 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 3mo agoCan 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 3mo agoSorry - 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=48839767 https://news.ycombinator.com/item?id=48840261 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 3mo agoI 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&query=by%3Adang%20rebound&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...)
- mcmoor 3mo agoWith 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 3mo agoDepends 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 3mo ago* introselect implementation often worst case n log n, typo