Top K IPs in Real Time

MediumPython

Problem

Datadog Log Management receives a stream of log events. Each event contains a source IP address. Implement a function that processes the stream and returns the k most frequent IP addresses.

Order results by descending frequency. If two IP addresses have the same frequency, order them lexicographically by IP address. The function should count events in one pass and use a heap-based selection strategy rather than sorting every distinct IP when k is small.

Formal Specification

Implement top_k_frequent_ips(events, k), where events is an iterable of strings and k is a positive integer. Return a list of at most k IP address strings. If fewer than k distinct IP addresses occur, return all distinct addresses.

The stream is finite for this function, and the returned result represents the ranking after all events have been processed. The frequency map should be updated as each event arrives, making the counting portion suitable for online ingestion.

Constraints

1 <= len(events) <= 10^6
1 <= k <= 10^5
Each event is a valid IPv4 or IPv6 address string
There are at most 10^6 distinct IP addresses
Ties are resolved by lexicographically ascending IP address

Function Signature

def top_k_frequent_ips(events, k):

Datadog Log Management receives a stream of log events. Each event contains a source IP address. Implement a function that processes the stream and returns the k most frequent IP addresses.