Comments
Hacker News
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.
by dimview
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.
by joshdavham
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.
by keithnz
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
by ta93754829
> 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).
by nitwit005
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.
by apricot
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.
by cgearhart
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.
by lubujackson
Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- 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.
by dimview - 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.
by joshdavham - 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.by keithnz
- 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 jobby ta93754829
- > 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).
by nitwit005 - 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.by apricot
- 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.
by cgearhart - 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.
by lubujackson