Reason About Top K Frequent Values at Scale

# Reason About Top K Frequent Values at Scale Given a collection of values and an integer `k`, explain how to identify the `k` most frequent values. Start with a single-machine frequency map and size-`k` min-heap, then extend the design to data that cannot fit on one machine by partitioning on value, computing local candidates, and finding the global top `k`. ### Constraints & Assumptions - The source does not define which values win a frequency tie or how the result is ordered. - A distributed design must ensure that all occurrences of one value contribute to the same final count. - Analyze both the number of input items and the number of distinct values. ### Clarifying Questions to Ask - If several values tie at the `k`th frequency, should all tied values be returned or should a tie policy select exactly `k`? - Must the result be ranked, and if so by what secondary order? - Are values streamable, and how many partitions and workers are available? ```hint Separate counting from selection First establish one complete count per distinct value; only then apply the agreed top-k comparison. ``` ### What a Strong Answer Covers - Frequency-map and bounded-heap invariants with time and space complexity. - Explicit treatment of ties, invalid `k`, and output ordering. - Key-based partitioning, local top-k candidates, and a global merge. - Skew, worker failure, spilling, repartitioning, and horizontal scaling. ### Follow-up Questions 1. Why can each key-based partition send only its local top `k` values to the final reducer? 2. How would a single extremely frequent or expensive-to-process key affect the design?