ZH version is available. Content is displayed in original English for accuracy.
Advertisement
Advertisement
⚡ Community Insights
Discussion Sentiment
52% Positive
Analyzed from 2607 words in the discussion.
Trending Topics
#median#interview#quickselect#algorithm#mean#sorted#array#sort#don#question
Discussion (60 Comments)Read Original on HackerNews
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.
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
A fun follow up is asking a candidate how to compute the 25th and 75th percentiles or more broadly, the n-th percentile.
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.
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.
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.
[1] https://github.com/apache/datasketches-python
Unless you work in some highly specialised field maybe.
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.
There is also an approximate algorithm that does not keep all the data in memory at the same time.
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 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
How about something like the beginnings of a spreadsheet engine?
Or.. count the number of distinctly shaped black regions in a bitmap image.
"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.
I'm not sure if its best to focus on strengths of weaknesses, but i did prefer to focus on strengths. I found convincing myself why I do want to work with someone was a better experience than trying to find reasons not to. Also it just tended to get better buy in from the other team member that way, and i'd know how to assign work once they joined.
if you are not aware of quickselect algorithm.
To wit, given the unordered set:
How would "Only the median (or pair around the median) needs to be sorted" be satisfied?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
My answer was one from experience and supported by a resource which provides details as to why medians are needed in real-world scenarios.
> This problem belongs to selection algorithms and quickselect is the common approach.
I responded to a specific comment in this discussion, not to what "this problem belongs."
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."
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.
Eventually most of those started getting spoiled too lol.
> # 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.
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.
I think the lore is that it was a bug in Java?'s binary search lib decades ago?
P.S. I can’t believe this happened over 20 years ago, I must be old.
The median of an even number of values is typically defined to be the mean of the two middle-most values.
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 4QuickSelect 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)
> QuickSelect is ...
Quickselect implementations can, and often do, partially sort the underlying collection:
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
Oh, you … ;-)