FastPrepTop-K IP Addresses from File Records
Problem · Hash Table

Top-K IP Addresses from File Records

Learn this problem
● MediumGoogle logoGoogleNEW GRADONSITE INTERVIEW
See Google hiring insights

Problem statement

The array addresses represents the records of a newline-delimited file, with one IP address per record. Every record is a valid canonical IPv4 address.

Return the k most frequent addresses, ordered by decreasing occurrence count. When two addresses have the same count, order them by ascending lexicographic string order. The result must be exact; approximate heavy-hitter results are not accepted.

GB-Scale Resource Model

The callable judge materializes the file records in addresses. For the original external-file setting, multiple sequential passes and deterministic external hash partition files are allowed. The bounded-memory target is to keep the counts for only one partition plus O(k) selection state in working memory; temporary disk storage is not counted as working memory. Choose enough partitions that each partition's distinct-address counts fit the available working-memory budget.

Function

topKIpAddresses(addresses: String[], k: int) → String[]

Examples

Example 1

addresses = ["10.0.0.1","10.0.0.2","10.0.0.1","192.168.1.1","10.0.0.2","10.0.0.1"]k = 2return = ["10.0.0.1","10.0.0.2"]

10.0.0.1 appears three times, 10.0.0.2 appears twice, and 192.168.1.1 appears once. The first two addresses therefore form the result.

Example 2

addresses = ["2.0.0.1","1.0.0.1","3.0.0.1","2.0.0.1","1.0.0.1"]k = 2return = ["1.0.0.1","2.0.0.1"]

1.0.0.1 and 2.0.0.1 each appear twice. Their equal counts are resolved by ascending lexicographic order.

Constraints

  • 1 <= addresses.length <= 200000 for the callable judge adapter.
  • Every element of addresses is a canonical IPv4 dotted-decimal string with four octets from 0 through 255 and no leading zero in a multi-digit octet.
  • 1 <= k <= the number of distinct addresses.
  • The output contains exactly k addresses.
  • The external-file follow-up requires an exact result and permits multiple sequential passes and temporary partition files.

More Google problems

drafts saved locally
public String[] topKIpAddresses(String[] addresses, int k) {
    // Write your code here.
}
addresses["10.0.0.1","10.0.0.2","10.0.0.1","192.168.1.1","10.0.0.2","10.0.0.1"]
k2
expected["10.0.0.1", "10.0.0.2"]
checking account