Had my 2nd Google round today, and the question was to design 2 APIs/functions for insert into a data stream and return any number between the nearest powers of 2 of the current median

I started with a multiset + iterator to the median approach.

But then the interviewer reminded me it’s an infinite stream, so O(N) space won’t work.

Then I thought in terms of ranges instead of storing elements. I wrote down buckets like [2^0,2^1], [2^1,2^2], …, [2^63,2^64] and realized I could just maintain the bucket index of the median. Took me a bit of struggle, but with hints from the interviewer, I came up with an O(1) space solution. Finally coded it up.

Follow-ups

Handling negatives: I suggested skipping them / treating separately.
Interviewer pointed out not to use while(1){} (I did that in the code 😅).

At the end we had a nice casual talk since he was from my college too (noticed from his Google ID photo, clg alumini what a coincidence lol....).

Felt like it went fine maybe hire / strong hire, not sure, but let’s hope 🤞.

first round exp : https://leetcode.com/discuss/post/7101066/google-interview-experience-trie-questio-6d7r/
third round exp : https://leetcode.com/discuss/post/7230869/google-interview-experience-by-charizard-5vuc/