33. Top-K Frequent Failure Modes from a Log Stream

Problem

An on-call dashboard scans a stream of failure-mode labels emitted by a model-serving pipeline (e.g. "timeout", "oom", "refusal"), one per failed request, and needs the k most common failure modes to surface first.

Given the full list of failure-mode labels and k, return the k labels that occur most often, most frequent first, without fully sorting every distinct label by frequency. Ties in frequency are broken alphabetically ascending.

Source: src/33_top_k_failure_modes.py

def top_k_failure_modes(failure_log: list[str], k: int) -> list[str]:
    ...

Examples:
>>> top_k_failure_modes(["timeout", "timeout", "oom", "refusal", "oom", "timeout"], k=2)
['timeout', 'oom']
>>> top_k_failure_modes(["b", "a", "a", "b", "c"], k=2)
['a', 'b']

Step-by-Step Approach

1. First count occurrences of every distinct failure-mode label in a single O(n) pass — collections.Counter does exactly this.
2. Recognize that you don't need a full sort of all m distinct labels by frequency — you only need the k most frequent, so a heap-based selection beats an O(m log m) sort whenever k is much smaller than m.
3. Build a composite sort key per label: (-count, label). Negating the count makes "most frequent" sort as "smallest," and the label as secondary key gives the required alphabetical-ascending tiebreak.
4. Use heapq.nsmallest(k, items, key=...) over that composite key — "smallest k by (-count, label)" is exactly "k most frequent, ties broken alphabetically."
5. Extract just the labels (drop the counts) from the result, preserving the order nsmallest already returns them in.
6. Handle edge cases: k=0 returns an empty list, an empty log returns an empty list, and k larger than the number of distinct labels just returns all of them.

The key insight is that heapq.nsmallest/nlargest already implement the bounded-heap top-k pattern internally in O(m log k) time — you get that efficiency for free by picking the right composite sort key instead of hand-rolling a heap loop.

Reference solution

import heapq
from collections import Counter


def top_k_failure_modes(failure_log: list[str], k: int) -> list[str]:
    # O(n) to count, O(m) for m distinct labels, O(m log k) for nsmallest -> O(n + m log k)
    counts = Counter(failure_log)
    # sort key (-count, label): highest count first, alphabetical tiebreak ascending;
    # nsmallest on that key == the k "smallest" keys == the k most frequent labels
    top = heapq.nsmallest(k, counts.items(), key=lambda item: (-item[1], item[0]))
    return [label for label, _ in top]

Key Functions & Tricks

• collections.Counter(failure_log) — one-line O(n) frequency count
• heapq.nsmallest(k, items, key=...) — bounded-heap top-k selection in O(m log k), no full sort needed
• key=lambda item: (-item[1], item[0]) — composite key packs "most frequent first" (negated count) and "alphabetical tiebreak" into one comparable tuple
• counts.items() — iterates (label, count) pairs directly from the Counter, no separate sorting step
• Negate to flip sort direction — a general trick for getting "largest first" out of functions that default to "smallest first" (or vice versa)

How to Recognize This Pattern