a software engineering interview question I like: computing the median
50 points by sunflowerseastar
50 points by sunflowerseastar
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:
Right out the gate: the numbers must be sorted.
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.
Maybe they expected you to know that you can sort integers in linear time? Idk, I would probably have given the nlogn answer too.
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.
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.
This is getting into interviewing philosophy, and I don't claim that mine is correct. But if you ask me, the point is to have an excuse to talk about code.
If the interviewee knows about quickselect: Great! Since they have some background, let's talk about how it works. If they just memorized a bit of trivia, then that will quickly become apparent. But if I pretend to not know it, can they explain to me why it's faster than sorting? (Communication skills.) If they forgot part of it, can they deduce the missing parts? (Reasoning skills.) Can they explain to me how they would find the missing info? (Research skills—kind of trivial but missing surprisingly often.)
If the interviewee doesn't know about quickselect: Some (IMO bad) interviewers would dock points here, but I wouldn't. We can still chat about how cheap or expensive a call to list.sort() is and why. We can still reason about whether it's likely to be a bottleneck, and ways we might speed up the overall program, even if we can't improve the algorithm. More importantly, I'll get signal about their general skill level, how easily they get stuck, and whether I'd enjoy working with them.
It's not a perfect system. You're still extrapolating years of job performance from an hour-long chat. But if a hypothetical interviewee crossed their arms and said, "My program is already perfect because sorting is always O(n log n), stop wasting my time," their ignorance of quickselect wouldn't be the reason for my thumbs-down.
Thanks for sharing that rationale. The reason I prefer to use "smooth" questions for interviews is to prevent the situation that you describe—having to drop candidates into buckets that you must interview differently. When you have multiple buckets, you effectively have different interview questions, and that makes it harder to consistently rate candidates across buckets. You must "calibrate" yourself on each bucket before you can reliably rate all candidates fairly. With smooth questions, everyone is in the same bucket, so calibration is easier and faster, and ratings are fairer and more reliable.
Makes sense—what would be an example of such a smooth question? I want to better understand how "smooth" looks to you.
With the disclaimer that I don't ask this particular median question, I don't think the discrete buckets require different interview techniques for each bucket. Whether or not the interviewee knows "the trick", the questions you ask are the same: Why do you say that? Can you explain that to me? How do we get unstuck here?
I think calibrating grading is still a hard problem, but for me it's more about seeing the candidate's thought process and communication style, rather than whether this choice of algorithm checks those boxes. But if the rubric has lots of qualifications for different types of solutions, I can see how that would make it harder to come up to speed on a problem.
Makes sense—what would be an example of such a smooth question? I want to better understand how "smooth" looks to you.
Smooth questions are those whose answers don't hinge on specific pieces of knowledge—an algorithm, a library function, a bit-manipulaion trick—but rather broad knowledge. For example, I've had good luck offering candidates novel data structures extracted from my area of work. That way, all candidates stay in a single bucket since they all have the same prior experience with the data structure: zero experience. Then I ask them to solve related problems (again, extracted from actual work) that I know cannot be solved by applying the right combo of off-the-shelf algorithms or library calls. The candidates have to build something from the ground all the way to the end solution, with no off ramps for candidates that know a magic algorithm or function.
I don't think the discrete buckets require different interview techniques for each bucket.
They don't require different interviewing techniques, but they do beg for different rating scales. Even if you ask the same questions, the difficulty and importance of answering them changes based on bucket. The difficulty and importance of "Can you explain that to me?" is markedly different for people in the buckets "uses sort then midpoint," "uses quickselect", "knows how to dissect and analyze quickselect", etc.
I think calibrating grading is still a hard problem, but for me it's more about seeing the candidate's thought process and communication style, rather than whether this choice of algorithm checks those boxes.
Agreed 100%. I just try to eliminate as many off ramps as I can, so everybody has to drive the same highway. Makes it easier to measure how far each candidate actually was able to go.
Aha! I was going to say that I remembered something about a constant choice of 5 or greater to actually make the algorithm expected linear, but I didn't see that in Quickselect. It was median of medians.
Ignoring that the answer exists somewhere online (or in the weights of a model), I think these kinds of questions are dumb because algorithms aren't the bottleneck for most jobs. So yeah I agree that algorithmic puzzles aren't it.
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).
I don't expect candidates to produce code better than the python standard library.
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
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.)
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.
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.
This was the answer I got from the LLM, with the added bonus of an immutable variation to chose from if needed.
I don’t use interview problems like the one suggested by the OP because I require smoothness: the ease of solving the problem should scale smoothly with the candidate’s ability and experience. In particular, if knowing the existence of a library function or of an algorithm such as quickselect or radix sort sharply changes the outcome of the problem, the problem is not good for measurement. It's not measuring the candidate’s experience and ability; it’s testing whether they know about particular magic relics. You can try to compensate with follow-up questions, but it’s better to offer a smooth problem from the outset.
I’d be very interested in a concrete example of a “smooth” problem if you’re willing to share.
Sure. I offered an example (in broad strokes, I don't want to burn a question that may still be in use) in https://lobste.rs/c/1uas1f.
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):
>>> import sys
>>> import numpy
>>> numpy.median([sys.float_info.max, sys.float_info.max])
.../venv/lib64/python3.11/site-packages/numpy/_core/_methods.py:132: RuntimeWarning: overflow encountered in reduce
ret = umr_sum(arr, axis, dtype, out, keepdims, where=where)
np.float64(inf)
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.
Same old maths algorithm type question best suited to a high school student. Can we do no better than mathematics in a world where the largest category of software is not transformational, but instead representational, i.e. the modeling of an external system?
When I was learning programming I definitely spent some time implementing median and percentile as Postgres aggregate functions. It was fairly tricky at that time because Postgres wanted aggregates to complete in a single linear scan. Of course these days it’s just built in and you wouldn’t bother to do that.