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.
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.
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.
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.
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.
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.
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.
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.
I'm pretty confident I would've been able to come up to the solution in better circumstances, maybe even without hints.
But it was clear in this case that the interviewer just took a question from the company's bank of questions and was alt-tabbed for half the interview, I have felt the energy early and I was also half-checked out.
I'm aware I'm saying this post factum, but I had a very fun first interview with that company and matched well with the first interviewer so my expectations were high, and then I got hit by the big tech style interview when it was an early stage startup.
Good point. I've ended interviews (as a candidate) when I believed the interviewer was being lazy (for example, administering a leetcode question and not even changing any of the details like input or output data). I ended up writing my own questions that aren't in leetcode because I interview candidates now. And I give 100% attention to the candidate.
>"it's a data stream" I knew the answer was going to be reservoir sampling.
But it's only an approximate percentile. Unless the interviewer mentions that an approximate solution is OK, you would be stuck. (And it's not fair to ask the candidate to ask whether an approximate solution is ok given that almost every problem has an easy "approximate" solution which is not explicitly not what they're looking for).
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.
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.
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).
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.
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.
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.
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.
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.
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.
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
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.
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.
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."
That's a good solution using existing tools, but I usually want it solved in whatever programming language is being tested. Not because command line tools aren't often an underutilized solution but because I am looking for their tendencies. Do they reach for a hashmap? Can they calculate it all in one pass? That kind of thing.
As for the why, it covers a class of issue that does come up; counting like items. Determining the frequency of things is pretty common. I run into variations on the problem a lot, even if word counting is a contrived example.
It also gives a good look at how someone might solve the "like" items - things like punctuation, casefolding, etc... - messing around with strings is something that happens all the time in the real world.
Also I might be tempted dock your shell solution for using cat unnecessarily
If I'm interviewing at a Python shop that actually does statistics t=ype stuff or text munging, I'd expect them to have preferred/existing solutions for these tasks in their standard dependencies. And if it were a Javascript/Nodejs shop, or a C/C++ shop, or a Rust shop, they'd also have "standard tooling" that'd be "the preferred option" to anything I could hand roll (either in an interview or during a regular workday).
My "sort | uniq | sort" pipeline (usually combined with grep/tr/awk/sed or similar) is a reasonable answer for an underspecified task with none of the obviously existing but as yet unstated requirements that'd come along with this task is "the real world". It's not an actual proposed piece of production code - it's a way to demonstrate "a" way of doing it without even committing to a language, never mind whatever is in the in house standard set of modules.
If you want to test how find the median in Python, my immediate question would be "what Python modules are you already using? It'd be foolish to invent it myself if the actual codebase already imports numpy or pandas or SciPy. And it's be equally foolish to import one of those if they are already not in use.
(Admittedly, it's been a _looooong_ time since I interviewed for a junior or mid level developer role where leetcode games might be part of the hiring hoop-jumping.)
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.
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.
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.
For sure. I mean, i think naturally you'll end up there if all goes well. Have some tricky questions prepared of course, but starting simple gives you so much so quickly and often tells you where their strengths and weaknesses will end up being.
I'm not sure if its best to focus on strengths of weaknesses, but i did prefer to focus on strengths. I found convincing myself why I do want to work with someone was a better experience than trying to find reasons not to. Also it just tended to get better buy in from the other team member that way, and i'd know how to assign work once they joined.
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.
ha, i'd have loved that. I'm out of the world where I hire people these days, solo founder life. Maybe i'll go back there, but it's a real mission objective to just be a one man show right now.
As with quicksort, quickselect is generally implemented as
an in-place algorithm, and beyond selecting the kth
element, it also partially sorts the data.
When the above is applicable, those quickselect implementations would violate the original assertion of:
Only the median (or pair around the median) needs to be
sorted, the other numbers can be unsorted
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.
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.
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.
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.
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.
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?
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
And what of the likelihood that the original collection is modified when using the quickselect algorithm, thus introducing observable side effects in what could reasonably be considered a "read-only" computation?
And there lies the tradeoffs you need to consider as part of an interview question.
But if the best alternative is to sort the whole collection, then Quickselect doesn't introduce a new problem. You either accept that modifying the collection in place is an acceptable behaviour (and describe that in your API docs) or you make a copy of the collection and operate on that.
Given a choice between quickselect and quicksort, quickselect will get the answer with less overhead and no additional constraints (because it's essentially the same algorithm with unnecessary steps removed).
There are alternative approaches that don't require a full copy/sort, but they either require a partial copy + partial sort, or multiple passes through the collection.
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)
Quickselect implementations can, and often do, partially sort the underlying collection:
As with quicksort, quickselect is generally implemented as
an in-place algorithm, and beyond selecting the kth
element, it also partially sorts the data.[0]
If you are aware of a quickselect implementation having O(n) average performance which does not modify the underlying collection, I would very much appreciate a reference to same.
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).
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.
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
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).
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).
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.
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.
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
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.
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.
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…
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.
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.
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.
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.
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.
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.
I'm pretty confident I would've been able to come up to the solution in better circumstances, maybe even without hints.
But it was clear in this case that the interviewer just took a question from the company's bank of questions and was alt-tabbed for half the interview, I have felt the energy early and I was also half-checked out.
I'm aware I'm saying this post factum, but I had a very fun first interview with that company and matched well with the first interviewer so my expectations were high, and then I got hit by the big tech style interview when it was an early stage startup.
Good point. I've ended interviews (as a candidate) when I believed the interviewer was being lazy (for example, administering a leetcode question and not even changing any of the details like input or output data). I ended up writing my own questions that aren't in leetcode because I interview candidates now. And I give 100% attention to the candidate.
>"it's a data stream" I knew the answer was going to be reservoir sampling.
But it's only an approximate percentile. Unless the interviewer mentions that an approximate solution is OK, you would be stuck. (And it's not fair to ask the candidate to ask whether an approximate solution is ok given that almost every problem has an easy "approximate" solution which is not explicitly not what they're looking for).
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.
Yeesh. Data streaming algorithms. Can I import [1] datasketches-python in the interview?
[1] https://github.com/apache/datasketches-python
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.
Please tell me this was not interview for a SaaS CRUD app role
> 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
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.
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.
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…
https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
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.
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.
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.
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.
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.
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
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.
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.
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."
That's a good solution using existing tools, but I usually want it solved in whatever programming language is being tested. Not because command line tools aren't often an underutilized solution but because I am looking for their tendencies. Do they reach for a hashmap? Can they calculate it all in one pass? That kind of thing.
As for the why, it covers a class of issue that does come up; counting like items. Determining the frequency of things is pretty common. I run into variations on the problem a lot, even if word counting is a contrived example.
It also gives a good look at how someone might solve the "like" items - things like punctuation, casefolding, etc... - messing around with strings is something that happens all the time in the real world.
Also I might be tempted dock your shell solution for using cat unnecessarily
tr ' ' '\n' < textfile | sort | uniq -c | sort -r
Or even:
< textfile tr ' ' '\n' | sort | uniq -c | sort -r
Yeah - I think we're on the same page here?
If I'm interviewing at a Python shop that actually does statistics t=ype stuff or text munging, I'd expect them to have preferred/existing solutions for these tasks in their standard dependencies. And if it were a Javascript/Nodejs shop, or a C/C++ shop, or a Rust shop, they'd also have "standard tooling" that'd be "the preferred option" to anything I could hand roll (either in an interview or during a regular workday).
My "sort | uniq | sort" pipeline (usually combined with grep/tr/awk/sed or similar) is a reasonable answer for an underspecified task with none of the obviously existing but as yet unstated requirements that'd come along with this task is "the real world". It's not an actual proposed piece of production code - it's a way to demonstrate "a" way of doing it without even committing to a language, never mind whatever is in the in house standard set of modules.
If you want to test how find the median in Python, my immediate question would be "what Python modules are you already using? It'd be foolish to invent it myself if the actual codebase already imports numpy or pandas or SciPy. And it's be equally foolish to import one of those if they are already not in use.
(Admittedly, it's been a _looooong_ time since I interviewed for a junior or mid level developer role where leetcode games might be part of the hiring hoop-jumping.)
> ... 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
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.
> Your answer is that of someone that googled some answer and went with it.
My answer was one from experience and supported by a resource which provides details as to why medians are needed in real-world scenarios.
> This problem belongs to selection algorithms and quickselect is the common approach.
I responded to a specific comment in this discussion, not to what "this problem belongs."
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.
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.
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.
For sure. I mean, i think naturally you'll end up there if all goes well. Have some tricky questions prepared of course, but starting simple gives you so much so quickly and often tells you where their strengths and weaknesses will end up being.
I'm not sure if its best to focus on strengths of weaknesses, but i did prefer to focus on strengths. I found convincing myself why I do want to work with someone was a better experience than trying to find reasons not to. Also it just tended to get better buy in from the other team member that way, and i'd know how to assign work once they joined.
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.
Interesting approach. Thanks for sharing. I should send my students your way for internships!
ha, i'd have loved that. I'm out of the world where I hire people these days, solo founder life. Maybe i'll go back there, but it's a real mission objective to just be a one man show right now.
Only the median (or pair around the median) needs to be sorted, the other numbers can be unsorted :)
How does one determine the median wherein "the other numbers can be unsorted"?
To wit, given the unordered set:
How would "Only the median (or pair around the median) needs to be sorted" be satisfied?https://en.wikipedia.org/wiki/Quickselect
From the Wikipedia page cited:
When the above is applicable, those quickselect implementations would violate the original assertion of: When the collection involved is immutable.> Right out the gate: the numbers must be sorted.
if you are not aware of quickselect algorithm.
without thinking about it or looking at the article, this feels rather radixy
Id screw this up assuming that sort and pick the middle is to obvious and do something dumb lol
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.
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.
> # 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.
Correct, it’s a common misconception/sloppy wording.
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.
I thought this was going to be about computing (a+b)/2 avoiding overflows
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.
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?
Indeed: https://research.google/blog/extra-extra-read-all-about-it-n...
P.S. I can’t believe this happened over 20 years ago, I must be old.
> 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.
There's also an interesting relationship to variance when you only have mean and median
...and it can lead to parallel processing discussions for very large arrays
Who does a sort for this D:
You need the middle value. You cannot be certain what is the middle value without a sorted array, unless I am mistaken.
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
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 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
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 4And what of the likelihood that the original collection is modified when using the quickselect algorithm, thus introducing observable side effects in what could reasonably be considered a "read-only" computation?
And there lies the tradeoffs you need to consider as part of an interview question.
But if the best alternative is to sort the whole collection, then Quickselect doesn't introduce a new problem. You either accept that modifying the collection in place is an acceptable behaviour (and describe that in your API docs) or you make a copy of the collection and operate on that.
Given a choice between quickselect and quicksort, quickselect will get the answer with less overhead and no additional constraints (because it's essentially the same algorithm with unnecessary steps removed).
There are alternative approaches that don't require a full copy/sort, but they either require a partial copy + partial sort, or multiple passes through the collection.
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)
> You can definitely do this without sorting.
> QuickSelect is ...
Quickselect implementations can, and often do, partially sort the underlying collection:
If you are aware of a quickselect implementation having O(n) average performance which does not modify the underlying collection, I would very much appreciate a reference to same.0 - https://en.wikipedia.org/wiki/Quickselect
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).
[flagged]
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.
Don't be mean!
> 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
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.
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).
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).