Google Interview Experience ( Median Range Question )
Summary
Had my 2nd Google round today with a question about designing 2 APIs for a data stream that returns numbers between the nearest powers of 2 of the current median. Faced challenges with infinite stream constraints and eventually came up with an O(1) space solution with hints from the interviewer.
Full Experience
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 nadir 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 🤞.
Interview Questions (1)
Design 2 APIs/functions for insert into a data stream and return any number between the nearest powers of 2 of the current median.