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. ```hint What a new record can change When a record joins a cluster, ask which stored facts about that cluster can change, and whether a later read has to look at anything other than those facts. ``` #### 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. ```hint Who pays for the bookkeeping Every piece of extra state moves cost from reads to writes or the other way around. Decide, for each workload, which side can afford it. ``` ```hint Find the shared hot spot Identify the structures that every writer and every reader touches, and ask whether they really need to be shared at that granularity. ``` #### 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? ```hint Why the maximum was easy A maximum can be updated from a single stored number. Work out the smallest state that still lets you update a median after one insertion. ``` #### 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 ### What a Strong Answer Covers - The membership rule clarified first, with its cost reflected in the complexity analysis - Incremental per-cluster summaries rather than recomputation on read - Read and write optimizations tied explicitly to the workload - Correct behavior under concurrent ingestion, including the creation of new clusters - A clear path from maximum to median, with exact and approximate trade-offs ### Follow-up Questions - If records can be deleted from a cluster, what happens to the stored maximum, and how do you keep reads fast? - How would you return the k largest values of each cluster? - Ingest is spread over several machines. How do you keep per-cluster maxima and medians correct across them?