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

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

Company: Google

Role: Software Engineer

Category: Software Engineering Fundamentals

Difficulty: medium

Interview Round: Technical Screen

## 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? ### What a Strong Answer Covers - Streaming normalization and a hash-map count for the in-memory case. - A size-ten selection structure to find the address cutoff frequency, followed by collection of every address at or above that cutoff. - Hash partitioning to disk so identical normalized addresses land together, followed by exact per-partition aggregation. - A global threshold pass over every partition count plus a second count-file pass that recovers all cutoff ties, rather than discarding them with a fixed local top ten. - Handling of skew, oversized partitions, cleanup, checkpoints, and malformed records. ### Follow-up Questions - How would you support an approximate one-pass answer with fixed memory? - What if one IP dominates and creates a severely skewed partition? - How would you parallelize without counting the same file segment twice?

Overview: Find the ten most frequent normalized IP addresses with cutoff ties preserved, first in memory and then exactly through disk partitioning, per-partition aggregation, global thresholding, and skew handling.

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 Guidance

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?

What a Strong Answer Covers Guidance

Streaming normalization and a hash-map count for the in-memory case.
A size-ten selection structure to find the address cutoff frequency, followed by collection of every address at or above that cutoff.
Hash partitioning to disk so identical normalized addresses land together, followed by exact per-partition aggregation.
A global threshold pass over every partition count plus a second count-file pass that recovers all cutoff ties, rather than discarding them with a fixed local top ten.
Handling of skew, oversized partitions, cleanup, checkpoints, and malformed records.

Follow-up Questions Guidance

How would you support an approximate one-pass answer with fixed memory?
What if one IP dominates and creates a severely skewed partition?
How would you parallelize without counting the same file segment twice?