Top K IPs Log Parsing | Dataford Interview Questions

Your question is Top K IPs Log Parsing. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Dell PowerStore telemetry can produce log streams too large to load into memory at once. Given an iterable of log lines, return the k most frequent IP addresses while counting each line in a single pass.

Each non-empty log line begins with an IP address, followed by zero or more fields separated by whitespace. Every IP address is valid. If multiple addresses have the same frequency, order them lexicographically by IP address. Return results ordered by decreasing frequency, then lexicographic IP order.

Formal Specification

Implement top_k_ips(log_lines, k).

Input: log_lines, an iterable of strings, and k, a positive integer.
Output: A list of at most k strings containing the most frequent IP addresses.
The function must process the input incrementally and must not store all log lines.
If k is greater than the number of distinct IP addresses, return every distinct address.

Constraints

1 <= number of log lines <= 10^7
1 <= k <= 10^5
Each line is non-empty and begins with a valid IP address
The input is an iterable of strings and may be consumed only once
Let u be the number of distinct IP addresses

Function Signature

def top_k_ips(log_lines, k):