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
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).
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.
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.
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.
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.
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.
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.
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.
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.
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?
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.
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
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 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 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
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."
> 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
> 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
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.
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.
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.
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.
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…
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.
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.
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.
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.
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.
https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
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
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.
without thinking about it or looking at the article, this feels rather radixy
> # 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.
> 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.
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.
There's also an interesting relationship to variance when you only have mean and median
Great question! Assuming the job requires calculating a lot of medians.
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!
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 4You 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 solve it with two heaps, which don't need to maintain a complete order. Or selection algorithms, as in the sibling comment (asymptotically better).
> High-quality candidates …
Oh, you … ;-)
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
> ... 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
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."