5 ms·

A software engineering interview question I like: computing the median

74 points by speckx 4mo ago

ukoki 4mo ago
Only the median (or pair around the median) needs to be sorted, the other numbers can be unsorted :)
- AdieuToLogic 4mo ago
  How does one determine the median wherein "the other numbers can be unsorted"? To wit, given the unordered set: [ 5, 1, 3 ] How would "Only the median (or pair around the median) needs to be sorted" be satisfied?
  - salamanderman 4mo ago
    https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect
    - AdieuToLogic 4mo ago
      From the Wikipedia page cited: 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 When the collection involved is immutable.
apricot 4mo ago
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.
- salamanderman 4mo ago
  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.
- kccqzy 4mo ago
  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.
- BobbyTables2 4mo ago
  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…
  - srean 4mo ago
    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.
  - kccqzy 4mo ago
    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.
joshdavham 4mo ago
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.
- ismailmaj 4mo ago
  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.
  - eventualcomp 4mo ago
    Yeesh. Data streaming algorithms. Can I import [1] datasketches-python in the interview? [1] https://github.com/apache/datasketches-python https://github.com/apache/datasketches-python
  - dekhn 4mo ago
    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-and-variance-in-a-running-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/ 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.
wewewedxfgdf 4mo ago
[flagged]
- DonHopkins 4mo ago
  Don't be mean!
- recursive 4mo 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.
jagged-chisel 4mo ago
[flagged]
floxy 4mo ago
https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm
ta93754829 4mo ago
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
- Induane 4mo ago
  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.
  - bigiain 4mo ago
    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."
    - Induane 4mo ago
      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
meltyness 4mo ago
without thinking about it or looking at the article, this feels rather radixy
hirvi74 4mo ago
> # 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.
- minitech 4mo ago
  Correct, it’s a common misconception/sloppy wording.
  - AdieuToLogic 4mo ago
    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.
NooneAtAll3 4mo ago
I thought this was going to be about computing (a+b)/2 avoiding overflows
- foobar1962 4mo ago
  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.
  - SeanSullivan86 4mo ago
    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?
    - jrpelkonen 4mo ago
      Indeed: https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/ 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.
  - justinpombrio 4mo ago
    > 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.
  - godelski 4mo ago
    There's also an interesting relationship to variance when you only have mean and median
strstr 4mo ago
Who does a sort for this D:
- marseysneed 4mo ago
  You need the middle value. You cannot be certain what is the middle value without a sorted array, unless I am mistaken.
  - scarmig 4mo ago
    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).
  - strstr 4mo ago
    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)
    - AdieuToLogic 4mo ago
      > 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 https://en.wikipedia.org/wiki/Quickselect
  - timv 4mo ago
    You can use Quickselect (https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect) or Floyd-Rivest (https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm 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 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
dreamcompiler 4mo ago
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.
- strstr 4mo ago
  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.
tayo42 4mo ago
Id screw this up assuming that sort and pick the middle is to obvious and do something dumb lol
SeanSullivan86 4mo ago
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.
- verelo 4mo ago
  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.
  - raddan 4mo ago
    Interesting approach. Thanks for sharing. I should send my students your way for internships!
    - 4mo ago
dimview 4mo ago
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.
- raddan 4mo ago
  The rabbit hole goes deep fast with this one! https://rcoh.me/posts/linear-time-median-finding/ 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…
keithnz 4mo ago
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.
ycui7 4mo ago
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.
- karmakaze 4mo ago
  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.
  - AndrewDucker 4mo ago
    I assume that "index" in this case is for the index in the fully sorted list? i.e. if you're looking for the 50th place in a 100 item list, then it's 50th place in the sorted list you want. But as you don't know what value that is, how do you know which partition it's in? (I am feeling very stupid today and hoping someone can explain this to me)
    - AndrewDucker 4mo ago
      Never mind, you're keeping the parts that are going to end up in that sorted location. That makes sense. This visualisation made it click for me: https://www.youtube.com/watch?v=HylYYer2hR4 https://www.youtube.com/watch?v=HylYYer2hR4
kccqzy 4mo ago
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.
- bulbar 4mo ago
  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.
  - kccqzy 4mo ago
    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.
dgacmu 4mo ago
> 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
- dang 4mo ago
  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.
  - dgacmu 4mo ago
    Sorry - I really wasn't trying to be a jerk, but I do acknowledge that directly addressing the author is aggressive. I was mostly trying to emphasize the importance of avoiding the negative experiences of people interviewing when the interviewer was wrong about something and won't flex, as exemplified in a couple of comments in this thread: https://news.ycombinator.com/item?id=48839767 https://news.ycombinator.com/item?id=48839767 https://news.ycombinator.com/item?id=48840261 https://news.ycombinator.com/item?id=48840261 So to clarify my point in a more general way: We _all_ have some concepts wrong in our head, and we should all strive to be not only graceful but delighted if an interviewee is correct when we're wrong.
    - dang 4mo ago
      I appreciate the reply! and yes, that's a much better way to express the point. (Btw this is an interesting phenomenon - I call it the rebound effect: https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=by%3Adang%20rebound&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...)
- mcmoor 4mo ago
  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).
nitwit005 4mo ago
> 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 https://en.wikipedia.org/wiki/Quickselect
halayli 4mo ago
> Right out the gate: the numbers must be sorted. if you are not aware of quickselect algorithm.
cgearhart 4mo ago
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.
lubujackson 4mo ago
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.
- gedy 4mo ago
  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
- strken 4mo ago
  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.
deleted 4mo ago
[deleted]
harrouet 4mo ago
...and it can lead to parallel processing discussions for very large arrays
aldanor 4mo ago
A pretty good related question is - compute a running median (or window median).
OutOfHere 4mo ago
Given `data`, here's a one liner: median = statistics.median(data) # `import statistics` first Here's another one-liner: median = (lambda x: (lambda s,n: s[n//2] if n%2 else (s[n//2-1]+s[n//2])/2)(sorted(x), len(x)))(data)

74 points by speckx 4mo ago

ukoki 4mo ago

Only the median (or pair around the median) needs to be sorted, the other numbers can be unsorted :)

AdieuToLogic 4mo ago
How does one determine the median wherein "the other numbers can be unsorted"? To wit, given the unordered set: [ 5, 1, 3 ] How would "Only the median (or pair around the median) needs to be sorted" be satisfied?
- salamanderman 4mo ago
  https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect
  - AdieuToLogic 4mo ago
    From the Wikipedia page cited: 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 When the collection involved is immutable.

apricot 4mo ago

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.

salamanderman 4mo ago
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.
kccqzy 4mo ago
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.
BobbyTables2 4mo ago
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…
- srean 4mo ago
  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.
- kccqzy 4mo ago
  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.

joshdavham 4mo ago

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.

ismailmaj 4mo ago
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.
- eventualcomp 4mo ago
  Yeesh. Data streaming algorithms. Can I import [1] datasketches-python in the interview? [1] https://github.com/apache/datasketches-python https://github.com/apache/datasketches-python
- dekhn 4mo ago
  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-and-variance-in-a-running-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/ 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.

wewewedxfgdf 4mo ago

[flagged]

DonHopkins 4mo ago
Don't be mean!
recursive 4mo 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.

jagged-chisel 4mo ago

[flagged]

floxy 4mo ago

https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

ta93754829 4mo ago

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

Induane 4mo ago
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.
- bigiain 4mo ago
  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."
  - Induane 4mo ago
    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

meltyness 4mo ago

without thinking about it or looking at the article, this feels rather radixy

hirvi74 4mo ago

> # 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.

minitech 4mo ago
Correct, it’s a common misconception/sloppy wording.
- AdieuToLogic 4mo ago
  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.

NooneAtAll3 4mo ago

I thought this was going to be about computing (a+b)/2 avoiding overflows

foobar1962 4mo ago
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.
- SeanSullivan86 4mo ago
  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?
  - jrpelkonen 4mo ago
    Indeed: https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/ 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.
- justinpombrio 4mo ago
  > 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.
- godelski 4mo ago
  There's also an interesting relationship to variance when you only have mean and median

strstr 4mo ago

Who does a sort for this D:

marseysneed 4mo ago
You need the middle value. You cannot be certain what is the middle value without a sorted array, unless I am mistaken.
- scarmig 4mo ago
  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).
- strstr 4mo ago
  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)
  - AdieuToLogic 4mo ago
    > 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 https://en.wikipedia.org/wiki/Quickselect
- timv 4mo ago
  You can use Quickselect (https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect) or Floyd-Rivest (https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm 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 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

dreamcompiler 4mo ago

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.

strstr 4mo ago
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.

tayo42 4mo ago

Id screw this up assuming that sort and pick the middle is to obvious and do something dumb lol

SeanSullivan86 4mo ago

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.

verelo 4mo ago
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.
- raddan 4mo ago
  Interesting approach. Thanks for sharing. I should send my students your way for internships!
  - 4mo ago

dimview 4mo ago

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.

raddan 4mo ago
The rabbit hole goes deep fast with this one! https://rcoh.me/posts/linear-time-median-finding/ 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…

keithnz 4mo ago

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.

ycui7 4mo ago

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.

karmakaze 4mo ago
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.
- AndrewDucker 4mo ago
  I assume that "index" in this case is for the index in the fully sorted list? i.e. if you're looking for the 50th place in a 100 item list, then it's 50th place in the sorted list you want. But as you don't know what value that is, how do you know which partition it's in? (I am feeling very stupid today and hoping someone can explain this to me)
  - AndrewDucker 4mo ago
    Never mind, you're keeping the parts that are going to end up in that sorted location. That makes sense. This visualisation made it click for me: https://www.youtube.com/watch?v=HylYYer2hR4 https://www.youtube.com/watch?v=HylYYer2hR4

kccqzy 4mo ago

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.

bulbar 4mo ago
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.
- kccqzy 4mo ago
  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.

dgacmu 4mo ago

> 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

dang 4mo ago
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.
- dgacmu 4mo ago
  Sorry - I really wasn't trying to be a jerk, but I do acknowledge that directly addressing the author is aggressive. I was mostly trying to emphasize the importance of avoiding the negative experiences of people interviewing when the interviewer was wrong about something and won't flex, as exemplified in a couple of comments in this thread: https://news.ycombinator.com/item?id=48839767 https://news.ycombinator.com/item?id=48839767 https://news.ycombinator.com/item?id=48840261 https://news.ycombinator.com/item?id=48840261 So to clarify my point in a more general way: We _all_ have some concepts wrong in our head, and we should all strive to be not only graceful but delighted if an interviewee is correct when we're wrong.
  - dang 4mo ago
    I appreciate the reply! and yes, that's a much better way to express the point. (Btw this is an interesting phenomenon - I call it the rebound effect: https://hn.algolia.com/?dateRange=all&page=0&prefix=false&query=by%3Adang%20rebound&sort=byDate&type=comment https://hn.algolia.com/?dateRange=all&page=0&prefix=false&qu...)
mcmoor 4mo ago
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).

nitwit005 4mo ago

> 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 https://en.wikipedia.org/wiki/Quickselect

halayli 4mo ago

> Right out the gate: the numbers must be sorted. if you are not aware of quickselect algorithm.

cgearhart 4mo ago

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.

lubujackson 4mo ago

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.

gedy 4mo ago
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
strken 4mo ago
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.

deleted 4mo ago

[deleted]

harrouet 4mo ago

...and it can lead to parallel processing discussions for very large arrays

aldanor 4mo ago

A pretty good related question is - compute a running median (or window median).

OutOfHere 4mo ago

Given `data`, here's a one liner: median = statistics.median(data) # `import statistics` first Here's another one-liner: median = (lambda x: (lambda s,n: s[n//2] if n%2 else (s[n//2-1]+s[n//2])/2)(sorted(x), len(x)))(data)