FastPrepTop-K IP Addresses Across Log Files
Problems/Top-K IP Addresses Across Log Files

Top-K IP Addresses Across Log Files

Render logoRender● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks for the five most frequent request IPs across three logs and discusses an external-memory follow-up. The callable adapter receives the already parsed address field from each log row and generalizes five to k; malformed-line parsing is outside the judged core.

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.
See Render hiring insights
Saved
class Solution {
    public String[] topKIpAddresses(String[] addresses, int k) {
        // Write your code here.
    }
}
Checking account…