Id screw this up assuming that sort and pick the middle is to obvious and do something dumb lol
A software engineering interview question I like: computing the median
21–30 of 97 posts
Re: A software engineering interview question I like: computing the median
#22Huh, 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.
Re: A software engineering interview question I like: computing the median
#23I 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…
Yeesh. Data streaming algorithms. Can I import [1] datasketches-python in the interview?
Re: A software engineering interview question I like: computing the median
#24Who does a sort for this D:
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, recursively compute the median on those, and pick the middle median as your pivot, which guarantees linear progress per iteration)
Re: A software engineering interview question I like: computing the median
#25I 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…
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 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.
Re: A software engineering interview question I like: computing the median
#26I 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.
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?
Re: A software engineering interview question I like: computing the median
#27Only 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 ]
Re: A software engineering interview question I like: computing the median
#28You 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.
Re: A software engineering interview question I like: computing the median
#29[flagged]
Don't be mean!
Re: A software engineering interview question I like: computing the median
#30> # 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.
Correct, it’s a common misconception/sloppy wording.
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.