EngMock
Coding interview questionHard
GoogleBloomberg

Track the Median of a Growing Stream

Design a structure that supports inserting numbers one at a time from a stream and efficiently reporting the median of all numbers seen so far.

Practice in Interview Dashboard

1. Problem Statement

Design a structure that supports inserting integers one at a time from a stream and returning the median of all values inserted so far, at any point.

2. Live Coding Format

Work in the provided coding workspace while explaining your decisions to the live interviewer. Validation may use inline tests, examples, comments, or a verbal walkthrough.

3. Key Focus Areas

  • 1
    Problem clarification and contract
  • 2
    Approach exploration and optimality
  • 3
    Think-aloud communication and pacing
  • 4
    Implementation correctness
  • 5
    Code quality and language fluency
  • 6
    Tests and dry run
  • 7
    Debugging and self-correction
  • 8
    Complexity analysis
  • 9
    Follow-up performance

4. What Strong Candidates Should Demonstrate

  • Clarify insertion frequency, query frequency, and duplicate/negative value assumptions before coding.
  • Explain a naive baseline and improve it so each insertion takes logarithmic time and each median query constant time.
  • Think aloud while implementing readable, correct code.
  • Validate with explicit expected outputs and a top-to-bottom dry run.
  • Analyze time and space complexity and handle a focused follow-up extension.

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, implementation, trade-offs, and validation.

Continue to Dashboard

Core Concepts

Hidden because they name the technique, which a real interviewer would not tell you.

Show core concepts
HeapsStreamingData Structure DesignComplexity Analysis

Continue preparing

Build a complete software engineer mock interview plan

Explore this interview track →View the complete guide →

Prepare by company

Google interview guide

Use this scenario in a focused preparation plan

OpenAI Coding Interview Preparation →

Related Coding / DSA

Fewest Moves to Solve a Sliding Tile Puzzle

Given a small 2-by-3 sliding tile puzzle board with one blank space, find the minimum number of adjacent tile slides needed to reach a specified target arrangement, or report it is unreachable.

Related Coding / DSA

Maximum Value in Every Sliding Window

Given an array and a window size k, return the maximum value within every contiguous window of size k as it slides from left to right across the array.

Related Coding / DSA

Merge Overlapping Room Bookings

Given a list of room booking intervals, each with a start and end time, merge all overlapping or touching intervals into the minimal set of consolidated bookings.

Related Coding / DSA

Minimum Worst-Case Drops with Two Bulbs

Given two identical bulbs and a building with F floors, return the minimum number of drops needed in the worst case to guarantee identifying the critical threshold floor.