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.