A software engineering interview question I like: computing the median

by speckx • 15 days ago

74 93 15 days ago

apricot• 15 days ago

In addition to the points listed, it gives the algorithm nerds the opportunity to show their overqualification by whipping out the O(n) median algorithm and proving that it works in linear time.

salamanderman2• 15 days ago

I almost tanked an interview, and luckily turned it around, when the interviewer had never heard of QuickSelect and thought I was insane when I started writing it.

kccqzy5• 14 days ago

Or it could just be someone who uses C++ instead of Python as their interview language. The std::nth_element is in the standard library.

BobbyTables2• 14 days ago

Or do a bucket sort on 32bit integers for worst case O(n) time, not O(n^2)

Only half kidding…

Using just 16GB RAM for a task is practically resource-constrained programming these days…

srean• 14 days ago

In my interview, several decades ago, a binary search over the bitwise representation of integers is the solution that I came up with. To the interviewers credit, who was caught by surprise by a solution he had not anticipated, he played along very sportily. He was very intrigued and happy that we came up with a solution he hadn't encountered.

Later I felt stupid after reading about quick select.

kccqzy5• 14 days ago

Just do four bucket sorts, once on each byte of the 32-bit integer. (Bucket sorts are stable sorts.) I benchmarked this and it was faster than quick sort.

joshdavham• 15 days ago

I also like this question.

A fun follow up is asking a candidate how to compute the 25th and 75th percentiles or more broadly, the n-th percentile.

ismailmaj3• 15 days ago

I got that recently, I really didn't like that question.

For the n-th percentile version, the obvious solution is sorting and it takes 10 seconds to get to that point, 5 minutes of implementation with tests. Good. It's all downhill from here.

Then you get hit with the "it's a data stream" and you realize you have to implement a balanced tree on the spot which I wouldn't describe as fun.

You may or may not be able to implement that. I did not. Blabbered something about Rust having sorted B-Trees and I don't think Python has them -- they do not on the standard library.

Then the interviewer leaned heavily on the "reduce memory usage" and I couldn't come up with a solution (no shit it's Ω(n) and he didn't even tell me to go fetch for a randomized algorithm). I later understood he expected the reservoir sampling solution which is basically keeping a representative group of size K that is a good proxy of the whole stream, it goes like this: keep the K first elements, any elements after that replaces any element of our sample at random.

What I did after 10 minutes of weird silence is to assume the data stream follows a normal distribution and computing the P-percentiles by computing the running mean and standard deviation.

I felt frustrated at the end of the interview because it really felt like a big gotcha of either you know the reservoir sampling "leetcode trivia" or you don't.

eventualcomp• 15 days ago

Yeesh. Data streaming algorithms. Can I import [1] datasketches-python in the interview?

[1] https://github.com/apache/datasketches-python

dekhn2• 15 days ago

Literally the second I read "it's a data stream" I knew the answer was going to be reservoir sampling.

RS is really interesting to me. many people you talk to can realize you can compute the mean of a data stream (https://www.geeksforgeeks.org/web-tech/expression-for-mean-a...) without knowing the exact formulation. And it's not far from that to think of a sampling strategy to decide if a new sample should go into a fixed-size reservoir. (for all of these, I know specific hints that will usually help people get to the next step).

The only reason I know RS is because it was in the google3 monorepo and I was looking for interesting codes to use and found it. There was an associated Sharding class, LexicographicRangeSharding (https://www.mongodb.com/docs/manual/core/ranged-sharding/) which you could use to find near-optimal split points in sorted string tables so your mappers didn't end up with hotspots. If you had shown me Algorithm R in a stats class, I don't think I would have appreciated it at all, but seeing the code implementation and a useful example made it click.

2muchcoffeeman• 14 days ago

That sort of stuff is bullshit I assume meant to boost the interviewer’s ego. Anyone can come up with shit like that given time to prepare or the internet.

Unless you work in some highly specialised field maybe.

bulbar2• 14 days ago

Yeah, you basically have to grind leetcode or get lucky - having a interviewer giving you enough hints or come up with a (for you) novel idea on the fly.

gedy2• 14 days ago

Please tell me this was not interview for a SaaS CRUD app role

ukoki• 15 days ago

Only the median (or pair around the median) needs to be sorted, the other numbers can be unsorted :)

AdieuToLogic7• 15 days ago

How does one determine the median wherein "the other numbers can be unsorted"?

To wit, given the unordered set:

  [ 5, 1, 3 ]

How would "Only the median (or pair around the median) needs to be sorted" be satisfied?

salamanderman2• 14 days ago

https://en.wikipedia.org/wiki/Quickselect

wewewedxfgdf• 15 days ago

[flagged]

DonHopkins• 15 days ago

Don't be mean!

recursive• 14 days ago

I'm tired of this. What the job does require is weeks of training before writing any meaningful code. Median has a simple definition that's a proxy for all the domain specific stuff in the real job.

floxy• 15 days ago

https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

ta93754829• 15 days ago

I don't know... I've been coding for ~30 years, and I've never had to write code to compute the median so it doesn't seem that useful unless it's somehow relevant to the job

Induane2• 15 days ago

One interview question I like that's simpler and more applicable is to code a function that outputs the frequency count of each word in a string of text. Bonus for outputting the count in most to least order.

bigiain2• 14 days ago

Is that really a "more applicable" task that finding the median? Are there actually software development jobs where either of those tasks are a regular/common part of the work, where people don't "just know" how to do them using whatever tools the job already uses?

I'm guessing I'd flunk your interview, because my initial response would be something like "No, I wouldn't write code for that. Unless there are unstated requirements, I'll just reach for the simplest possible solution, which for me would be something like cat textfile | tr ' ' '\n' | sort | uniq -c | sort -r That doesn't handle punctuation, probably doesn't handle unicode the way you might expect, and has a bunch of other things that additional requirements might rule out. But that'd be my starting point."

AdieuToLogic7• 14 days ago

... I've never had to write code to compute the median so it doesn't seem that useful unless it's somehow relevant to the job

A binary search[0] of a sorted collection requires the median of each region being considered for each iteration.

0 - https://en.wikipedia.org/wiki/Binary_search

halayli2• 14 days ago

Not picking on you but your answer prove the parent comment's point. Your answer is that of someone that googled some answer and went with it. This problem belongs to selection algorithms and quickselect is the common approach.

oreally• 14 days ago

Psychologists have been saying for ages that a good job interview is a small version of what the job requires them to do. But as always with most professions with people (and hence ego) involved, these people either mimic what the trending company in their sector does or test irrelevant academia knowledge.

Maybe for such changes to happen the whole profession to go down a notch in prestige. Not sure if people can stomach that.

Traster2• 14 days ago

I'm not certain the point of an interview is to ask you to write the exact lines of code that you would write during the job.

meltyness• 15 days ago

without thinking about it or looking at the article, this feels rather radixy

hirvi74• 15 days ago

# Python is pass-by-reference, what are the
# implications of sorted() vs numbers.sort()?

I thought references were passed by value in languages like Python? I am not particularly fond of Python, so my experience with and knowledge of the language are quite limited. But, I understand what the question is asking: mutation vs. the creation of a new object.

minitech• 15 days ago

Correct, it’s a common misconception/sloppy wording.

AdieuToLogic7• 15 days ago

A mental exercise I perform when "reference" is used in this context is to substitute it with "pointer." I find it clarifying and rarely, if ever, incorrect.

NooneAtAll3• 15 days ago

I thought this was going to be about computing (a+b)/2 avoiding overflows

foobar1962• 15 days ago

That's average or mean. Median is the middle value.

From the article:

It can lead to some discussion about statistics and why you might prefer a median to a mean in most cases.

My best example for median vs mean is property prices, where very expensive properties will skew the mean (average value) upwards but the median (middle value) will remain about the same.

SeanSullivan863• 15 days ago

The overflow thing would be about computing the median of some sub-range of a sorted array. It is an often-quizzed thing that comes up as an edge case in binary search of a large array, but could apply to anything where you need to select the middle element of a sub-range of an array and the sum of the start/end indices could overflow.

I think the lore is that it was a bug in Java?'s binary search lib decades ago?

justinpombrio• 14 days ago

That's average or mean. Median is the middle value.

The median of an even number of values is typically defined to be the mean of the two middle-most values.

godelski• 14 days ago

There's also an interesting relationship to variance when you only have mean and median

strstr3• 15 days ago

Who does a sort for this D:

marseysneed• 15 days ago

You need the middle value. You cannot be certain what is the middle value without a sorted array, unless I am mistaken.

strstr3• 15 days ago

You can definitely do this without sorting.

QuickSelect is average case n, and is, roughly, quick sort where you throw away one of the sides each time and recurse on the other. This has a fat tail for cases where you pick a bad pivot (similar to quicksort), but you can median-of-medians your way out of that problem if someone cares. (Median of medians being where you subdivide the array into, say, 5 arrays, recursively compute the median on those, and pick the middle median as your pivot, which guarantees linear progress per iteration)

scarmig• 15 days ago

You can solve it with two heaps, which don't need to maintain a complete order. Or selection algorithms, as in the sibling comment (asymptotically better).

timv2• 15 days ago

You can use Quickselect (https://en.wikipedia.org/wiki/Quickselect) or Floyd-Rivest (https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm)

Quickselect is fairly simple to understand if you already understand Quicksort. You use use a binary division but you avoid sorting sections where the order doesn't matter.

Let's start with a 7 element array

    [ 2, 4, 7, 5, 3, 6, 1 ]

We pivot on the mid-point (5) so that values less than end before it in the array and numbers larger end up after it

    [ 2, 4, 3, 1, 5, 7, 6 ]

Since 5 is now at an index greater than the midpoint, you know the median must be less than 5, so you don't care that 7 and 6 aren't sorted.

We pivot the first partition (first 4 elements) on 3 and get

   [ 2, 1, 3, 4, 5, 7, 6 ]

We don't care that 2 and 1 are unsorted, because we know that the median is > 3 (3 is at index #2 and we want index #3), so the median must be 4

dreamcompiler• 15 days ago

Even better question: Compute the moving median.

Computing a moving average with samples being pumped through an n-element buffer is easy. Doing so for the median requires more thought. It's also very useful e.g. for removing single-sample noise from an audio track, so it's not a meaningless exercise.

strstr3• 15 days ago

I used to translate classic interview questions into not-spoiled-on-the-internet ones by doing this kind of batch to incremental conversion. The count-the-islands one was fun but hard to fit into a 45minute interview.

Eventually most of those started getting spoiled too lol.

tayo42• 15 days ago

Id screw this up assuming that sort and pick the middle is to obvious and do something dumb lol

SeanSullivan863• 15 days ago

Huh, feels overly simple to me.

How about something like the beginnings of a spreadsheet engine?

Or.. count the number of distinctly shaped black regions in a bitmap image.

verelo4• 15 days ago

So for about 10 years my main interview question was:

"Write me a function in any language of your choosing, that takes an array of integers and returns the sum."

I loved it. Here is why:

1. I'd get to see them write code, in a low pressure way, but they'd have to write something

2. A shocking number of people would struggle to write the code. That was my signal to end the interview early.

3. I'd get to ask "So tell me how it works" and they'd sometimes look at me like I'm a moron, but others would be respectful and kind, and that would tell me how they'd answer other people who ask questions they felt had obvious answers.

4. I'd ask "what could go wrong at runtime?" - this would be where most people got surprised by their own responses, but it was a fun conversation to have about a seemingly simple function.

5. I'd ask how they would fix any potential runtime exceptions or potential undesirable behaviours

6. I'd try break it, and ask how they would handle that (if i could, i often could)

7. If we got this far, then we could move onto other questions and they're warmed up and generally feeling safe about how the conversation would go. I'd like to switch from coding into data structure related questions normally.

I hate high pressure coding interviews, also, who the hell doesn't just sit there and Google / LLM the answer anyway. The real question I want to know is "How curious are you? Do you want to learn? What kind of person are you? Will I enjoy working with you when things get hard". That's hard to figure out, but you're not going to do that if you just try stump someone in an interview. I think it's on the interviewer to find a way to ask questions that are revealing and accessible in an interview environment...and frankly, I think you get more out of it if you make the effort to keep it simple.

raddan2• 14 days ago

Interesting approach. Thanks for sharing. I should send my students your way for internships!

SeanSullivan863• 14 days ago

Interesting approach, thanks. Yeah, I don't mind a question and conversation like that to start things off. But I do think getting into something a little deeper (which you also mentioned) later in the interview is important, too.

rokob• 14 days ago

I used to do phone screens with a similarly simple question. I am still blown away that something like 60% would fail to write working code. I had more parts for the 40% that got it the first one, but it was crazy how many people couldn't do the most trivial task.

eudamoniac• 14 days ago

My front end interview question is "ping this api and display the response on the page. Add a button to ping again and replace the data on the page with the new response."

This filters out approximately 80% of "Front End Engineers" in their framework of choice.

dimview• 15 days ago

You can do it a bit faster by not quicksorting the entire array, as you don't really care about the order of the lowest and highest numbers as long as they are not close to the middle.

There is also an approximate algorithm that does not keep all the data in memory at the same time.

raddan2• 14 days ago

The rabbit hole goes deep fast with this one!

https://rcoh.me/posts/linear-time-median-finding/

I vaguely recall learning a randomized (approximate) streaming median algorithm in grad school, but the details have left my brain…

keithnz• 15 days ago

I find this kind of thing too limited and you can't do much with it. I like to take problems from our domain. We work with all kinds of measurement data for agriculture / mining / utilities, I'll usually work through the problem of coming up with an alarm/alert system given a timeseries. It has relatively straight forward programming problems like simple on off threshold alerting and more complex issues like making predictors to decide when to irrigate for example. Depending on the level of the person we can do different things, talk about our domain and some of the problems in that domain. So we can go through specifying things, making design decisions, implementing an interesting aspect (usually not too complex with limited scope), next steps to build the system out, how to validate, logging, etc, feeling out how they'd approach making it production ready basically.

ycui7• 14 days ago

there is an algorithm called quick-select. getting median of an array should not require full sort of the whole array, only a partial sort is needed to get the median. quick-select does this.

karmakaze• 14 days ago

I just discovered the name of this. I visualized that you can do a quicksort but only recurse one of the partitions each time--the one that contains the median index. It has the same worst-case O(n^2) and can be fixed the same way choosing the median pivot of 3 potential pivots. Apparently C++'s `std::nth_element` uses quick-select and since if you choose a different target index can find any percentile not just the median.

AndrewDucker2• 14 days ago

I assume that "index" in this case is for the index in the fully sorted list? i.e. if you're looking for the 50th place in a 100 item list, then it's 50th place in the sorted list you want.

But as you don't know what value that is, how do you know which partition it's in?

(I am feeling very stupid today and hoping someone can explain this to me)

kccqzy5• 14 days ago

After the candidate has finished this, you could then ask them to compute the weighted median. Chances are, the candidate has never heard of this term and yet the term is simple enough that without prior knowledge they can use their intuition to give a definition for this term and implement it. Good candidates can define and implement it for weights that are natural numbers, and better candidates can implement it for any weights that are nonnegative.

Candidates who could implement an O(n) median algorithm but chose to implement an O(n log n) weighted median algorithm might be someone who rote remembered the O(n) algorithm. Truly excellent strong hires can adapt their O(n) algorithm to weighted median too.

bulbar2• 14 days ago

How do you know they didn't just have heard about weighed median before and how to implement it?

Or did just more grinding on leetcode in general.

I am not convinced that what you call "strong" can be tested by something like that.

kccqzy5• 14 days ago

Interviews are just collecting circumstantial evidence anyways. I do not really think a single interview can conclusively prove that a candidate is strong. Within the limit of one interview, this candidate is strong enough. And I'd be happy to hear contrary opinions from the other interviewers.

dgacmu4• 14 days 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

dang2• 14 days ago

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.

dgacmu4• 14 days ago

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.

mcmoor• 14 days ago

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).

dgacmu4• 14 days ago

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.

nitwit005• 14 days ago

Right out the gate: the numbers must be sorted.

I was somewhat pained by this, as this is an interview question I've gotten, and I clearly annoyed the interviewer by knowing this isn't true, and you can avoid a full sort (which, at least two others have noted).

https://en.wikipedia.org/wiki/Quickselect

halayli2• 14 days ago

Right out the gate: the numbers must be sorted.

if you are not aware of quickselect algorithm.

cgearhart• 14 days ago

We used to use this, but it was a broader conversation around tradeoffs to meet different constraints. If the expected array is small, then sort + index is probably fine. If it’s big (bigger than main memory?) and latency is the most important then maybe you want median-of-medians. If it’s a stream and you want to keep memory fixed then you might want a sketching algorithm. If I suggest that we can bound the error of the median estimate with constant additional space and the same complexity, would you believe me? (Just track the mean and standard deviation.)

Honestly, when I ran this interview I didn’t care much about the specifics of what you memorized beforehand. I care if you can read and write code a bit. I care more whether we can have a productive conversation. If you learn something new from me or the problem, how does that look and feel? If I make a mistake, how do you react? Are we able to communicate technical ideas to each other? Are we able to productively work through conflict?

We’re not computing many medians day-to-day, but we’re doing all those other things constantly.

lubujackson• 14 days ago

This question, and many "but make it a bit more challenging!" comments always strike me as CS101 navelgazing type questions. The best part of this question is that it is simple and can be used to swing into deeper concerns but it is still at odds with actual job responsibilities - even more so with LLMs in the mix.

Maybe this is because I have only worked at startups, but I am much more interested in if someone can read and understand code, where they feel logic is brittle, overly complex or badly designed. If they understand, even conceptually, how adding an optional field to an endpoint may be fine but removing one needs to be phased out or considered for active users. If they consider downstream risks, if they understand business goals and how to communicate limitations or opportunities.

Instead, every single tech interview seems to focus on how well you paid attention in your CS seminar which might be a reasonable screen for junior employees but is awfully irrelevant for anyone >3 years in the industry.

There are far too many corners of logic for everyone to know. Maybe someone has never dealt with data streams, or even forgets what a median is. You want to know if they are sharp with statistics? Great for some roles, wholly irrelevant for many others.

Engineers need to communicate, read and understand logic and how things connect. And the golden skill: willing and able to learn something new.

gedy2• 14 days ago

No no, see those are all softball questions, and the only way to prove they are not coasting fakers or liars is to quiz them like this. /s

strken• 14 days ago

Hiring funnels at big companies are funny because they're all about stacking filters together in a way that optimises some random grab bag of metrics in the candidates who make it through.

One of those metrics is "number of people hired who literally can't write code". You'd be able to give these candidates a full description of what the median is and they still wouldn't be able to finish this question, and you're not going to get too many false positives, so you add it to your rotation as the first question and have an enthusiastic mid-level engineer do it as the first half-hour round of an interview.

Then you design a few more rounds to test for the positive things you want, like pair refactoring, architecture, lunch with the team, or whatever floats your boat. That way your senior engineers don't need to interview people who can't write code and you stand a lower chance of accidentally hiring some of them.

Traster2• 14 days ago

I think there's two elements to this. First - all the things you list are important too, and we'll get to that. But there's no point in getting to those things if the candidate can't write 5 lines of python and has no idea how the language operates.

Second, hiring at startups is massively different to hiring at big companies. At big companies you have a website and a linkedin and a recruiter and external recruiters and they're all funnelling CVs to you dozens at a time. You're glancing over a CV and if it looks roughly right you'll do a phone screen. People lie on their CVs. So you need a few questions like this just drop the 90% of candidates who have literally no chance at getting the job. Keep in mind, the external recruiters will interview the candidates you reject, find out your interview questions, find the answers and tip off future candidates.

We're also hiring for a different set of skills. At a start up everyone is doing everything. Does it matter how well you can talk to customers? Maybe! That could be useful. In a large company if you ever talk to a customer as an engineer you will have been at the company for years, you'll have a Sales guy, Technical Sales guy, an Account Manager, your manager, and maybe a Project Manager all in the room if you ever get to see a customer.

kccqzy5• 13 days ago

There are far too many corners of logic for everyone to know. Maybe someone has never dealt with data streams, or even forgets what a median is.

Bad interviewers expect candidates to know things. I don’t. It’s okay for a candidate to have never worked on data streams or to forget what a median is. I simply provide the definition and continue. I care about the quality and effectiveness of thinking. If the candidate can be given a definition and then immediately turn that into code, that already shows that they are good at logical reasoning. It’s basically the same kind of thinking required when there is an urgent request at a startup and an engineer is pulled in to come up with a solution quickly; all the business logic will be new and you want someone who can learn quickly, internalize quickly, and produce results based on these learnings quickly. Therefore in my opinion asking these interview questions are actually a good indicator of how they will perform in a hectic startup environment.

harrouet• 14 days ago

...and it can lead to parallel processing discussions for very large arrays

aldanor• 14 days ago

A pretty good related question is - compute a running median (or window median).

OutOfHere• 14 days ago

Given `data`, here's a one liner:

  median = statistics.median(data)  # `import statistics` first

Here's another one-liner:

  median = (lambda x: (lambda s,n: s[n//2] if n%2 else (s[n//2-1]+s[n//2])/2)(sorted(x), len(x)))(data)

A software engineering interview question I like: computing the median

Related Stories