Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A software engineering interview question I like: computing the median

krisshamloo.com

Post reply on HN
Print view View original

61–70 of 97 posts

Re: A software engineering interview question I like: computing the median

#61

Post by AdieuToLogic »

strstr wrote: post #24
marseysneed wrote: post #20

Earlier quoted context omitted.

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

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, recursive…

> You can definitely do this without sorting.

> QuickSelect is ...

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.

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

Re: A software engineering interview question I like: computing the median

#62

Post by AdieuToLogic »

timv wrote: post #33
marseysneed wrote: post #20

Earlier quoted context omitted.

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 [ 2, 4, 7, 5, 3, 6, 1 ] We pivot on the mid-point (5) so that…

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?

Re: A software engineering interview question I like: computing the median

#63

Post by BobbyTables2 »

apricot wrote: post #2

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 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…

Re: A software engineering interview question I like: computing the median

#64

Post by lubujackson »

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.

Re: A software engineering interview question I like: computing the median

#65

Post by karmakaze »

ycui7 wrote: post #36

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.

Re: A software engineering interview question I like: computing the median

#66

Post by bulbar »

ismailmaj wrote: post #18
joshdavham wrote: post #3

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…

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.

Re: A software engineering interview question I like: computing the median

#67

Post by bulbar »

kccqzy wrote: post #38

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…

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.

Re: A software engineering interview question I like: computing the median

#68

Post by timv »

AdieuToLogic wrote: post #62
timv wrote: post #33

Earlier quoted context omitted.

You can use Quickselect ( https://en.wikipedia.org/wiki/Quickselect ) or Floyd-Rivest ( https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm ) Quickselect is fairly simple to understand if you already understand Quicksort. You use use a binary division but you avoid sorting sections where the order doesn't matter. Let's start with a 7 element array [ 2, 4, 7, 5, 3, 6, 1 ] We pivot on the mid-point (5) so that…

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.

Re: A software engineering interview question I like: computing the median

#69

Post by krackers »

dekhn wrote: post #25
ismailmaj wrote: post #18

Earlier quoted context omitted.

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…

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…

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

Re: A software engineering interview question I like: computing the median

#70

Post by dang »

dgacmu wrote: post #40

> 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.
Post reply on HN