Find the Most Frequent IP Addresses in a File Too Large for Memory

Interview Prompt

A file contains IP headers, one record at a time. Return the ten most frequent IP addresses with cutoff ties preserved. If there are at least ten distinct addresses, let cutoff be the frequency of the tenth address after sorting by descending frequency; return every address whose frequency is at least cutoff, so the result may contain more than ten addresses. Group results by descending frequency and sort addresses deterministically within each group. First solve the in-memory case, then redesign it for a file whose distinct-address map cannot fit in memory.

Constraints & Assumptions

• The file is streamed and cannot be reread accidentally through hidden library behavior.
• IP parsing failures need an explicit skip-or-fail policy.
• Counts may exceed 32-bit range.
• The external-memory design has bounded local disk and can process partitions sequentially.

Clarifying Questions to Ask

• Are addresses IPv4, IPv6, or both, and how are equivalent textual forms normalized?
• May derived partition-count files be scanned more than once after the source stream is partitioned?
• May approximate heavy-hitter results be returned, or must the answer be exact?