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.
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.
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.
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.
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.
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.
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 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.
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.
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).
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).
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.
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.
> 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.
37 comments
[ 3.7 ms ] story [ 67.2 ms ] threadOnly half kidding…
Using just 16GB RAM for a task is practically resource-constrained programming these days…
A fun follow up is asking a candidate how to compute the 25th and 75th percentiles or more broadly, the n-th percentile.
Maybe for such changes to happen the whole profession to go down a notch in prestige. Not sure if people can stomach that.
> # 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.
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.
How about something like the beginnings of a spreadsheet engine?
Or.. count the number of distinctly shaped black regions in a bitmap image.
This filters out approximately 80% of "Front End Engineers" in their framework of choice.
There is also an approximate algorithm that does not keep all the data in memory at the same time.
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.
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.
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).
https://en.wikipedia.org/wiki/Quickselect
if you are not aware of quickselect algorithm.
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.
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.
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.