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

41–50 of 97 posts

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

#41

Post by jrpelkonen »

SeanSullivan86 wrote: post #26
foobar1962 wrote: post #16

Earlier quoted context omitted.

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.

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?

Indeed: 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.

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

#42

Post by justinpombrio »

foobar1962 wrote: post #16
NooneAtAll3 wrote: post #13

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

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.

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

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

#43

Post by bigiain »

Induane wrote: post #15
ta93754829 wrote: post #9

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

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.

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

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

#44

Post by raddan »

dimview wrote: post #28

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.

The rabbit hole goes deep fast with this one!

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…

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

#45

Post by godelski »

foobar1962 wrote: post #16
NooneAtAll3 wrote: post #13

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

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.

There's also an interesting relationship to variance when you only have mean and median

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

#46

Post by dekhn »

ismailmaj wrote: post #34
dekhn wrote: post #25

Earlier quoted context omitted.

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…

I'm pretty confident I would've been able to come up to the solution in better circumstances, maybe even without hints. 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…

Good point. I've ended interviews (as a candidate) when I believed the interviewer was being lazy (for example, administering a leetcode question and not even changing any of the details like input or output data). I ended up writing my own questions that aren't in leetcode because I interview candidates now. And I give 100% attention to the candidate.

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

#47

Post by 2muchcoffeeman »

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…

That sort of stuff is bullshit I assume meant to boost the interviewer’s ego. Anyone can come up with shit like that given time to prepare or the internet.

Unless you work in some highly specialised field maybe.

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

#48

Post by kccqzy »

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 it could just be someone who uses C++ instead of Python as their interview language. The std::nth_element is in the standard library.

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

#49

Post by salamanderman »

AdieuToLogic wrote: post #27
ukoki wrote: post #4

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

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?

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

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

#50

Post by raddan »

verelo wrote: post #35
SeanSullivan86 wrote: post #22

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.

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…

Interesting approach. Thanks for sharing. I should send my students your way for internships!
Post reply on HN