Find the K most frequent IPs in a huge log in O(n log K)
You have a very large access.log (N lines, the client IP in the first field) and must return the K most frequent IPs where K is small relative to the number of distinct IPs. A full sort of all unique IPs is O(U log U); you must do better.
Constraints: target O(N log K) time and O(U + K) space; you may use a programming language here. Implement the function below.
def top_k_ips(path: str, k: int) -> list[str]:
# your code here
...Write the implementation.
Count frequencies in a hash map in one O(N) pass, then keep a min-heap of size K over the counts: push each (count, ip), and once the heap exceeds K pop the smallest. Each heap op is O(log K), so selecting over U distinct IPs is O(U log K) ≤ O(N log K). The heap leaves the K largest; sort just those K for the final order. This beats sorting all uniques at O(U log U).
- ✗Using a max-heap of size K instead of a min-heap — you must pop the smallest
- ✗Sorting all unique IPs (O(U log U)) when only the top K are needed
- ✗Forgetting the O(N) hash-count pass and trying to heap raw lines directly
- →Why does keeping the K largest require a min-heap rather than a max-heap?
- →How would you adapt this when even the distinct-IP counts exceed memory?
Solution
Two stages: a hash count, then a bounded heap to select the top K without sorting every distinct IP.
import heapq
from collections import Counter
def top_k_ips(path: str, k: int) -> list[str]:
counts = Counter()
with open(path) as f:
for line in f: # O(N) single pass
ip = line.split(" ", 1)[0]
counts[ip] += 1
# min-heap of size K over (count, ip): the smallest sits at the root
heap: list[tuple[int, str]] = []
for ip, c in counts.items(): # O(U) items
if len(heap) < k:
heapq.heappush(heap, (c, ip))
elif c > heap[0][0]:
heapq.heappushpop(heap, (c, ip)) # O(log K)
# heap holds the K largest; order them descending for output
return [ip for _, ip in sorted(heap, reverse=True)]Why a min-heap. We want the K largest counts. A size-K min-heap keeps the smallest of the current top-K at the root; when a bigger count arrives we evict that root. The survivors are exactly the K largest. A max-heap would surface the global maximum, which is the wrong element to evict.
Complexity. Counting is O(N). The selection does O(U) heap operations, each O(log K), so O(U log K) ≤ O(N log K). Space is O(U) for the map plus O(K) for the heap. This beats sorting all U distinct IPs at O(U log U) when K ≪ U.
