Hard

Google-styleBloomberg-style

Track the Median of a Growing Stream DSA Interview

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.

Mock Interview with AI

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

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

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
Handwritten 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 sorted-storage baseline and improve to a balanced two-heap design.
✓Think aloud while implementing careful heap balancing logic.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a focused follow-up extension.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies behavior when the stream is empty, whether duplicate values are allowed, and whether the median of an even count should be the average of the two middle values.
✓Confirms that insert and getMedian can be called in any interleaved order, not just all inserts then all queries.

Staff-level signals

◆Asks about the relative frequency of insert versus getMedian calls to justify the chosen tradeoff.

Common red flags

×Codes immediately while assuming an odd-only count without confirming the even-count convention.

Approach exploration and optimality

20%

Senior signals

✓Explains a naive baseline that keeps a sorted list and inserts each new value into its correct position (or re-sorts on every insert), identifies the linear-shift or full-sort bottleneck, and improves to a balanced two-heap design: a max-heap for the lower half and a min-heap for the upper half.
✓Explains the balancing invariant that keeps the two heaps within one element of each other in size so the median is always derivable from the heap tops.

Staff-level signals

◆Discusses how the design would change if getMedian were called far more often than insert, or vice versa.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.
×Proposes a single heap without explaining how the median would be derived from it.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates the rebalancing steps after each insertion while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct two-heap design that inserts into the appropriate heap, rebalances sizes to differ by at most one, and derives the median from the heap top(s).
✓Handles an empty stream, a single value, an even total count, and duplicate values.
✓Provides a convincing invariant argument for why the heap tops always represent the two middle values.

Common red flags

×Fails to rebalance after insertion, causing an incorrect median for certain input orders.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with clearly named heaps and a defined rebalancing step, using the language's available heap or priority queue primitive correctly (including max-heap emulation where the language only provides a min-heap).

Common red flags

×Contains heap-comparator direction errors or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom, showing heap contents after each insertion.
✓Covers an empty stream, single value, even count, and duplicate values.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States logarithmic time for insert and constant time for getMedian, with linear auxiliary space overall, comparing it with the sorted-list baseline.

Staff-level signals

◆Discusses the amortized cost tradeoff if getMedian is called much more frequently than insert.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

A sorted list with insertion at the correct position gives O(1) median queries but O(n) insertion due to shifting elements.
Re-sorting on every insert is simple but costs O(n log n) per insertion.
A balanced two-heap design achieves O(log n) insertion and O(1) median queries using O(n) auxiliary space overall.

Practice follow-up questions

1.Coding follow-up: extend the design to compute the median of only the most recent k values in the stream (a sliding window), keeping both insertion of new values and eviction of expired values efficient.
2.Verbal extension: how would the design change if you also needed to support removing an arbitrary previously inserted value, not just the oldest one?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

HeapsStreamingData Structure DesignComplexity Analysis