Top K Frequent IPs | Dataford Interview Questions

Noblis mission operations telemetry can contain a very large stream of network transaction records. Write a function that returns the k most frequent IP addresses without sorting every distinct address.

Each input line has the format timestamp ip action status, separated by single spaces. The timestamp and remaining fields are irrelevant. Return IP addresses ordered by decreasing frequency. If two addresses have the same frequency, order them lexicographically ascending.

Your algorithm must process lines in one pass and maintain a heap containing at most k candidates after counting. The input iterable may be a list or a generator.

Formal Specification

Implement top_k_ips(lines, k), where lines is an iterable of valid log-line strings and k is a positive integer. Return a list of at most k strings. The input guarantees that k does not exceed the number of distinct IP addresses.

Constraints

1 <= len(lines) <= 10^7
Each line contains at least four whitespace-separated fields
Each IP is a valid IPv4 address string
1 <= k <= number of distinct IP addresses
The number of distinct IP addresses may be much larger than k

Function Signature

def top_k_ips(lines, k):

Your question is Top K Frequent IPs. Start with the requirements in the Question tab.

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

Problem