Stream Records into Clusters and Track Each Cluster's Maximum and Median

A service consumes a stream of data records and processes them one at a time. Every record is stored in exactly one cluster, and the record itself determines which one: looking at the record, the system decides whether it belongs to a cluster that already exists or whether it is the first record of a new cluster. Each record carries a numeric value. Besides ingesting records, the system must provide a function that reads the maximum value of each cluster.

The interview started from this basic version, continued with several follow-ups about optimizing reads and writes, and ended with a verbal follow-up about medians.

Constraints and Clarifications

• The membership rule was described only as "decided from the record itself". Treat the rule as given, but find out how it works before you code, because it sets the cost of every insert.
• Assume each record has a numeric value over which the maximum (and later the median) is taken.
• Records arrive continuously and clusters are created on the fly; no list of clusters is known in advance.

Clarifying Questions

• Is membership decided by a key carried in or computed from the record (an exact match), or by comparing the record with the existing clusters, for example by its distance to a cluster representative under a threshold?
• If membership is decided by comparison, can a record match several clusters, and which one wins?
• Is the maximum read for one cluster at a time, for all clusters at once, or both? Must a read reflect every record ingested before it?
• Do clusters only grow, or can records be removed or expire?
• What is the ratio of writes to reads, and do several producers ingest at the same time?

Part 1 — Ingest records and read cluster maxima

Implement a class with one operation that ingests a record into its cluster, creating the cluster when the record is its first, and one operation that returns a cluster's maximum value. State the time and space cost of each operation.

What This Part Should Cover

• A cluster registry and an assignment step that follow the clarified membership rule, including creation of a new cluster
• Per-cluster state that answers a maximum read without scanning the cluster's records
• Time and space cost of insert and read, including the cost of the membership decision itself
• Behavior for an unknown cluster, negative values and equal values

Part 2 — Optimize reads and writes

The interviewer then pushed on read and write performance through several follow-ups. Explain how you would change the design when reads of the maxima dominate, when ingest throughput dominates, and when several threads ingest and read concurrently.

What This Part Should Cover

• Read-side optimizations, including reading every cluster's maximum without walking all clusters on each call
• Write-side cost, especially the membership lookup when there are many clusters, and batching
• Concurrency control granularity, safe creation of new clusters, and the freshness a reader gets
• Memory: which record data must be kept at all

Part 3 — Median of each cluster (verbal follow-up)

How would you return the median value of each cluster, in addition to the maximum?

What This Part Should Cover

• Why a single running value no longer works
• A per-cluster structure with sublinear insert and fast median reads
• The definition used for an even number of values
• Memory cost, and exact versus approximate options for very large clusters