# Find a Distributed Mode Efficiently A large multiset is partitioned across ten workers. Find the value with the highest total frequency across all workers. Network bandwidth is the bottleneck, so sending every raw item to one coordinator is unacceptable. Design an exact solution and, if useful, an approximate alternative. Specify worker, network, reducer, and coordinator responsibilities; tie-breaking; failure behavior; and the amount of data transferred in terms of local distinct values and global cardinality. ### Constraints & Assumptions - A value may appear on many workers and local partitions can be highly skewed. - The exact mode is required unless the caller explicitly chooses an approximate result. - Use a deterministic tie-breaker such as the smallest serialized value. - Workers can aggregate locally before communicating. - The coordinator should not become the only place that stores every raw record. ### Clarifying Questions to Ask - What is the value domain and approximate distinct cardinality? - Is the result one-time or continuously updated? - Are worker partitions replayable after failure? - Is an error probability or additive frequency error acceptable? - Can workers communicate with one another, or only with a service tier? ### What a Strong Answer Covers - A correct global aggregation plan with quantified communication. - Partitioning and skew mitigation. - An explicit exact-versus-approximate contract. - Retry, deduplication, tie-breaking, and observability. ### Follow-up Questions 1. How would the design change for a sliding window? 2. How would you find the top one thousand values rather than one mode? 3. What happens when one value dominates a reducer partition? 4. Can you prove when a two-round candidate-pruning scheme is exact?