How about something like the beginnings of a spreadsheet engine?
Or.. count the number of distinctly shaped black regions in a bitmap image.
apricot 49 minutes 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 43 minutes 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.
joshdavham 47 minutes 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 11 minutes 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 3 minutes ago [-]
Yeesh. Data streaming algorithms. Can I import [1] datasketches-python in the interview?
I thought this was going to be about computing (a+b)/2 avoiding overflows
foobar1962 11 minutes 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.
tayo42 7 minutes ago [-]
Id screw this up assuming that sort and pick the middle is to obvious and do something dumb lol
ukoki 45 minutes ago [-]
Only the median (or pair around the median) needs to be sorted, the other numbers can be unsorted :)
dreamcompiler 11 minutes 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 7 minutes 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.
meltyness 23 minutes ago [-]
without thinking about it or looking at the article, this feels rather radixy
hirvi74 22 minutes 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 19 minutes ago [-]
Correct, it’s a common misconception/sloppy wording.
wewewedxfgdf 42 minutes ago [-]
Great question! Assuming the job requires calculating a lot of medians.
jagged-chisel 39 minutes ago [-]
> High-quality candidates …
Oh, you … ;-)
strstr 15 minutes ago [-]
Who does a sort for this D:
marseysneed 7 minutes ago [-]
You need the middle value. You cannot be certain what is the middle value without a sorted array, unless I am mistaken.
strstr 1 minutes 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.
ta93754829 30 minutes 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 14 minutes 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.
Rendered at 02:07:39 GMT+0000 (Coordinated Universal Time) with Vercel.
How about something like the beginnings of a spreadsheet engine?
Or.. count the number of distinctly shaped black regions in a bitmap image.
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.
[1] https://github.com/apache/datasketches-python
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.
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.
Oh, you … ;-)
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.