Assume the two-heap streaming-median approach exceeds available memory for a very large or unbounded stream. Identify the bottlenecks and propose scalable designs to continue producing exact or approximate medians and the loose-median interval under memory constraints. Consider options such as external-memory algorithms, bucketization, quantile sketches, distributed aggregation, and windowed processing. Explain trade-offs in accuracy, latency, memory, and I/O, and outline failure handling and back-pressure strategies.

This System Design question evaluates understanding of streaming data processing, quantile estimation, and the design of memory-constrained services that must trade off accuracy, latency, memory, and I/O.

How do I approach System Design interview questions?

System Design questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master system design interviews.

What difficulty level is this interview question?

This is a hard difficulty System Design question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Scale median under memory constraints | Google Interview Question

Design a Scalable Streaming Median Service Under Memory Constraints

Context

You are building a service that consumes a very large or unbounded stream of numeric values and must continuously report:

The median (exact if feasible, otherwise approximate), and
A "loose-median" interval: a value range [L, R] guaranteed to contain the true median.

The classic two-heap (max-heap for lower half, min-heap for upper half) approach requires storing all seen values and therefore exceeds memory when the stream is very large.

Tasks

Identify the bottlenecks of the in-memory two-heap approach for very large/unbounded streams.
Propose scalable designs that continue producing exact or approximate medians and the loose-median interval under memory constraints. Consider:
- External-memory (disk-backed) algorithms
- Bucketization/histograms
- Quantile sketches (e.g., GK, KLL, t-digest)
- Distributed aggregation
- Windowed (e.g., sliding/tumbling) processing
Explain the trade-offs across accuracy, latency, memory, and I/O for each option.
Outline failure handling and back-pressure strategies suitable for a production service.

State any minimal assumptions you make (e.g., numeric domain, tolerance for approximation, latency SLOs).

Context

You are building a service that consumes a very large or unbounded stream of numeric values and must continuously report:

The median (exact if feasible, otherwise approximate), and

A "loose-median" interval: a value range [L, R] guaranteed to contain the true median.

The classic two-heap (max-heap for lower half, min-heap for upper half) approach requires storing all seen values and therefore exceeds memory when the stream is very large.

Tasks

Identify the bottlenecks of the in-memory two-heap approach for very large/unbounded streams.

Propose scalable designs that continue producing exact or approximate medians and the loose-median interval under memory constraints. Consider:

External-memory (disk-backed) algorithms
Bucketization/histograms
Quantile sketches (e.g., GK, KLL, t-digest)
Distributed aggregation
Windowed (e.g., sliding/tumbling) processing

Explain the trade-offs across accuracy, latency, memory, and I/O for each option.

Outline failure handling and back-pressure strategies suitable for a production service.

State any minimal assumptions you make (e.g., numeric domain, tolerance for approximation, latency SLOs).

Scale median under memory constraints

Quick Overview

Design a Scalable Streaming Median Service Under Memory Constraints

Context

Tasks

Solution

Submit Your Answer to Earn 20XP

Scale median under memory constraints

Quick Overview

Design a Scalable Streaming Median Service Under Memory Constraints

Context

Tasks

Solution

Submit Your Answer to Earn 20XP