For this reason, it's not really such a great interview question, since the optimal solution is a complicated algorithm that nobody can be expected to produce quickly on the spot (unless they know it by heart, which is also not helpful for testing the candidate).
I guess you could ask the candidate to produce the "naive" solution (using some library function to sort the array, then return the middle).
I was getting ready to be very upset, since I still remember getting filtered from a phone screen for giving an n*log(n) solution to this problem.
I later learned about quickselect in my algorithms class, and I thought, "there's no way they expected me to come up with that on the spot." But hey, guess I wasn't fit for the job.
I asked Claude about this, and it gave me quickselect as the fastest, median of medians as the best theoretical performance (but with a large constant that makes it practically slower), and that library functions typically use introselect, which is quickselect with fallback to median of medians. It mentioned numpy.partition() as an implementation, but it looks like it returns a copy of the array rather than operating in place. I didn't press on it for other implementations.
What is the point of these interview questions these days? All they're doing is testing if you've memorized the interviewer's favorite bit of trivia. You can more than ever "just Google" the answers to most of these kinds of questions.
In practice, the problem with anything more substantial is all the edge conditions as the algorithm is implemented from the theoretical description. Tearing apart something like numpy.partition() to see how it actually works is much more interesting, and also much more difficult to ask in an interview question--although this question may be too simple to have lots of interesting edge cases in a well-designed modern language.
Author here, I would be very impressed if a candidate mentioned quickselect! I don't think that makes this a poor question - the straightforward algorithm still offers lots of good discussion.
I guess you could ask the candidate to produce the "naive" solution (using some library function to sort the array, then return the middle).
As a bonus point you get to know immediately if someone has studied algorithms (or at least prepared for the interview) and proposes to use quick select https://en.wikipedia.org/wiki/Quickselect
It really doesn't though. I would see this question as a basic "can they actually program?" aka "did the screeners really do their job?" question. Even if I could regurgitate quick select off the top of my head (which I'm sure I wouldn't do perfectly) I would choose the naive solution so I didn't waste the interviewer's time.
The case of an even length array is interesting here, as it seems there are 2 (maybe more?) ways to go about it: running generic quick select twice on the middle two indecies, or somehow adapting quick select to deal with the task (which may or may not amount to the same thing)
Yes. I was confused that the requirement that the list be sorted was there, as it's not necessarily the case rather intuitively.
I suppose it's still an interesting question, even if OP perhaps phrased it in the wrong terms. If the caller already has sorted data, you can get the median in O(1) time, and even quickselect's O(n) (TIL!) is a waste of time.
Looks like python's int type doesn't overflow, but if you're using C or C++ or Go, don't you also need to worry about overflowing the addition in the even-length-array branch?
That addition is on floats, not ints. You still have the possibility of an overflow turning into inf. If the two elements of the array are both sys.float_info.max then the answer should also be sys.float_info.max. However the addition will produce inf and then dividing that by 2 will still be inf.
You could try to fix this by distributing the division by 2 over the addition. But then it will produce the wrong answer for denormals. I think most people just assume that numbers large enough to produce this problem will never happen in their program. Even numpy produces inf here (with a warning):
vrolfs | 5 hours ago
I don't really understand this post. I think the author is not aware that the median can be computed in O(n). See here: https://rcoh.me/posts/linear-time-median-finding/
So this is wrong:
For this reason, it's not really such a great interview question, since the optimal solution is a complicated algorithm that nobody can be expected to produce quickly on the spot (unless they know it by heart, which is also not helpful for testing the candidate).
I guess you could ask the candidate to produce the "naive" solution (using some library function to sort the array, then return the middle).
cole-k | an hour ago
I was getting ready to be very upset, since I still remember getting filtered from a phone screen for giving an n*log(n) solution to this problem.
I later learned about quickselect in my algorithms class, and I thought, "there's no way they expected me to come up with that on the spot." But hey, guess I wasn't fit for the job.
cmcaine | 55 minutes ago
Maybe they expected you to know that you can sort integers in linear time? Idk, I would probably have given the nlogn answer too.
dualvariable | 36 minutes ago
I asked Claude about this, and it gave me quickselect as the fastest, median of medians as the best theoretical performance (but with a large constant that makes it practically slower), and that library functions typically use introselect, which is quickselect with fallback to median of medians. It mentioned numpy.partition() as an implementation, but it looks like it returns a copy of the array rather than operating in place. I didn't press on it for other implementations.
What is the point of these interview questions these days? All they're doing is testing if you've memorized the interviewer's favorite bit of trivia. You can more than ever "just Google" the answers to most of these kinds of questions.
In practice, the problem with anything more substantial is all the edge conditions as the algorithm is implemented from the theoretical description. Tearing apart something like numpy.partition() to see how it actually works is much more interesting, and also much more difficult to ask in an interview question--although this question may be too simple to have lots of interesting edge cases in a well-designed modern language.
kris | 14 minutes ago
Author here, I would be very impressed if a candidate mentioned quickselect! I don't think that makes this a poor question - the straightforward algorithm still offers lots of good discussion.
I don't expect candidates to produce code better than the python standard library.
msangi | 11 hours ago
As a bonus point you get to know immediately if someone has studied algorithms (or at least prepared for the interview) and proposes to use quick select https://en.wikipedia.org/wiki/Quickselect
Boojum | 9 hours ago
I was surprised that wasn't mentioned! If I was asked this and was using C++, I'd be using nth_element.
(And if I had to write out quickselect from scratch, I could do that too; it's basically just partition + bisection.)
dvogel | 4 hours ago
It really doesn't though. I would see this question as a basic "can they actually program?" aka "did the screeners really do their job?" question. Even if I could regurgitate quick select off the top of my head (which I'm sure I wouldn't do perfectly) I would choose the naive solution so I didn't waste the interviewer's time.
baetylboy | 6 hours ago
The case of an even length array is interesting here, as it seems there are 2 (maybe more?) ways to go about it: running generic quick select twice on the middle two indecies, or somehow adapting quick select to deal with the task (which may or may not amount to the same thing)
zipy124 | 8 hours ago
Yes. I was confused that the requirement that the list be sorted was there, as it's not necessarily the case rather intuitively.
Gaelan | 7 hours ago
I suppose it's still an interesting question, even if OP perhaps phrased it in the wrong terms. If the caller already has sorted data, you can get the median in O(1) time, and even quickselect's O(n) (TIL!) is a waste of time.
HugoDaniel | 6 hours ago
This was the answer I got from the LLM, with the added bonus of an immutable variation to chose from if needed.
bediger4000 | 4 hours ago
Looks like python's
inttype doesn't overflow, but if you're using C or C++ or Go, don't you also need to worry about overflowing the addition in the even-length-array branch?abbeyj | 2 hours ago
That addition is on
floats, notints. You still have the possibility of an overflow turning intoinf. If the two elements of the array are bothsys.float_info.maxthen the answer should also besys.float_info.max. However the addition will produceinfand then dividing that by 2 will still beinf.You could try to fix this by distributing the division by 2 over the addition. But then it will produce the wrong answer for denormals. I think most people just assume that numbers large enough to produce this problem will never happen in their program. Even numpy produces
infhere (with a warning):Yomguithereal | 6 hours ago
And then there are many ways to actually choose the median itself. Linear interpolation? Upper bound, lower bound?
And then you can discuss for hours about quantiles, as selecting a single of them and a bunch of them at once require different angles.