# Find the Most Frequent IP Addresses in a File Too Large for Memory You receive a file containing billions of IP-address records, one record per line. Design an implementation that returns the `k` addresses with the highest occurrence counts. The file is much larger than available RAM, but sequential disk scans are allowed. Define how malformed lines are handled, how ties are ordered, and whether IPv4 and IPv6 text is normalized before counting. Give precise time, memory, and disk-I/O complexity for your design. ### Constraints & Assumptions - The available memory budget is known and substantially smaller than the file. - The exact result is required; an approximate heavy-hitters answer is not sufficient unless discussed as a follow-up. - Temporary disk space is available but should be bounded and cleaned up safely. - `k` is small compared with the number of distinct addresses. ### Clarifying Questions to Ask - Must differently formatted but equivalent IPv6 addresses count as the same key? - Is input compressed, and may it be read more than once? - What deterministic order should break equal-count ties? - What are the memory and temporary-storage budgets? ### What a Strong Answer Covers - A bounded-memory exact counting strategy - Stable partitioning or external sorting and safe temporary-file handling - A size-`k` selection structure after aggregation - Complexity expressed in records, distinct keys, partitions, and disk passes - Skew, malformed input, normalization, and operational failure cases ### Follow-up Questions - How would the design change for an unbounded stream? - When would an approximate sketch be preferable? - How could multiple machines process the file in parallel? - How would you avoid one extremely frequent address creating a hot partition?