Google Interview Experience ( Median Range Question )

Result
Ongoing
Posted
20 Aug 2025
363 reads

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.

How it went

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

Questions asked (1)

  1. 01

    Design APIs for Median Range Query

    Data Structures & Algorithms

    Design 2 APIs/functions for insert into a data stream and return any number between the nearest powers of 2 of the current median.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!