[ismailmaj]

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.

[dekhn]

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.

[ismailmaj]

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

[dekhn]

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.

[krackers]

>"it's a data stream" I knew the answer was going to be reservoir sampling.

But it's only an approximate percentile. Unless the interviewer mentions that an approximate solution is OK, you would be stuck. (And it's not fair to ask the candidate to ask whether an approximate solution is ok given that almost every problem has an easy "approximate" solution which is not explicitly not what they're looking for).

[eventualcomp]

Yeesh. Data streaming algorithms. Can I import [1] datasketches-python in the interview?

[1] https://github.com/apache/datasketches-python

[bulbar]

Yeah, you basically have to grind leetcode or get lucky - having a interviewer giving you enough hints or come up with a (for you) novel idea on the fly.

[2muchcoffeeman]

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.

[gedy]

Please tell me this was not interview for a SaaS CRUD app role

[ismailmaj]

I don't know what the day to day would be like but it was a ML research engineer role.