Design a logger that returns its top-K messages

01The design, in the six-step framework

1. Requirements and use cases

This prompt starts as a small class and is reported as open-ended: the candidate defines the methods, the assumptions and the tests. Landing on a clean API before the data structure is part of the grade.

• A caller records a message with a timestamp.
• A caller asks for the top k messages by count, over everything seen or over the last W seconds.
• A caller sets an importance on messages, and the logger evicts the least important when it is over capacity.
• Ties in count break deterministically, by message text.

Out of scope: persistence, cross-process counts and message similarity. Assumptions to state aloud: timestamps are integer seconds and non-decreasing at first; k is small compared with the distinct messages; memory is bounded by the window. Non-functional constraints: record in amortised O(1), top_k in O(d log k) for d distinct messages; thread safety as a follow-up. Reported twists: timestamps arriving out of order, and a log manager that evicts by importance.

2. Core entities and relationships

• LogEntry: an immutable message, timestamp and importance.
• WindowCounter: per-second buckets of message counts, expired from the old end, plus running totals.
• TopKLogger: the public API; owns the counter and the retained entries.
• RetentionPolicy: decides which entry to evict when over capacity.
• ImportancePolicy: the default policy, a min-heap by (importance, timestamp).

The logger composes the counter, which is private bookkeeping. The retention policy is aggregated because it is passed in, so a test can use a first-in-first-out policy without touching the logger.

3. Interfaces and key methods

class RetentionPolicy(Protocol):
    def add(self, entry: LogEntry) -> None: ...
    def evict(self) -> LogEntry: ...
    def entries(self) -> list[LogEntry]: ...

class WindowCounter:
    def add(self, message: str, ts: int) -> None:
        """Count one occurrence in the bucket for ts; older than the window is ignored."""
    def expire(self, now: int) -> None:
        """Subtract buckets with ts <= now - window from totals."""

class TopKLogger:
    def record(self, message: str, ts: int, importance: int = 0) -> None: ...
    def top_k(self, k: int, now: int) -> list[tuple[str, int]]:
        """Most frequent messages in (now - window, now], count descending, ties by text."""
    def retained(self) -> list[LogEntry]: ...

Invariants: totals[m] equals the sum of m across live buckets; a message with a zero total is absent from totals, so memory follows the window; the number of retained entries never exceeds capacity.

4. Design patterns and the choices behind them

Buckets instead of a list of events

A deque of every event gives an exact window, but memory grows with traffic. Per-second buckets bound memory by window size times distinct messages per second, and expiry is a subtraction per bucket. The price is one-second granularity, which the stated integer timestamps make free. A dictionary of buckets rather than a ring also handles out-of-order arrival: a late event lands in its own bucket if that second is still in the window.

A size-k heap at query time

Keeping a sorted order on every record costs a log factor on the hot path, and with sliding windows counts go down as well as up, which breaks a maintained heap. Scanning totals with a size-k min-heap at query time is O(d log k), and heapq.nsmallest with a key says exactly that. Reads are rarer than writes here, so the cost sits on the right side. If queries dominate, an ordered map of count to messages gives O(k) reads at the price of O(log d) writes; state which you chose and why.

Retention as an injected policy

Eviction is a different question from counting, and the two must not share a structure: an evicted log entry must still count towards frequency unless told otherwise. A separate policy keeps that clear and keeps the public API small.

5. Core flow and code

1. record calls counter.add, then stores a LogEntry in the policy.
2. If the policy now holds more than capacity entries, it calls evict once.
3. top_k(k, now) calls expire(now), which pops buckets from the oldest second and subtracts them.
4. It runs a size-k selection over totals with key (negative count, message).

from __future__ import annotations
import heapq, threading
from collections import Counter
from dataclasses import dataclass
from typing import Protocol


@dataclass(frozen=True)
class LogEntry:
    message: str
    ts: int
    importance: int = 0


class RetentionPolicy(Protocol):
    def add(self, entry: LogEntry) -> None: ...
    def evict(self) -> LogEntry: ...
    def entries(self) -> list[LogEntry]: ...


class ImportancePolicy:
    """Evict the lowest importance first, oldest first within a tie."""
    def __init__(self) -> None:
        self.heap: list[tuple[int, int, int, LogEntry]] = []
        self._seq = 0

    def add(self, entry: LogEntry) -> None:
        self._seq += 1
        heapq.heappush(self.heap, (entry.importance, entry.ts, self._seq, entry))

    def evict(self) -> LogEntry:
        return heapq.heappop(self.heap)[3]

    def entries(self) -> list[LogEntry]:
        return [item[3] for item in self.heap]


class WindowCounter:
    def __init__(self, window: int) -> None:
        self.window = window
        self.buckets: dict[int, Counter[str]] = {}
        self.order: list[int] = []            # heap of live bucket seconds
        self.totals: Counter[str] = Counter()
        self.newest = 0

    def add(self, message: str, ts: int) -> None:
        self.newest = max(self.newest, ts)
        if ts <= self.newest - self.window:
            return                            # too late to matter
        if ts not in self.buckets:
            self.buckets[ts] = Counter()
            heapq.heappush(self.order, ts)
        self.buckets[ts][message] += 1
        self.totals[message] += 1

    def expire(self, now: int) -> None:
        cutoff = now - self.window
        while self.order and self.order[0] <= cutoff:
            second = heapq.heappop(self.order)
            for message, n in self.buckets.pop(second).items():
                self.totals[message] -= n
                if self.totals[message] == 0:
                    del self.totals[message]


class TopKLogger:
    def __init__(self, window: int, capacity: int, policy: RetentionPolicy) -> None:
        self.counter = WindowCounter(window)
        self.capacity = capacity
        self.policy = policy
        self.size = 0
        self.lock = threading.Lock()

    def record(self, message: str, ts: int, importance: int = 0) -> None:
        with self.lock:
            self.counter.add(message, ts)
            self.policy.add(LogEntry(message, ts, importance))
            self.size += 1
            if self.size > self.capacity:
                self.policy.evict()
                self.size -= 1

    def top_k(self, k: int, now: int) -> list[tuple[str, int]]:
        if k <= 0:
            return []
        with self.lock:
            self.counter.expire(now)
            return heapq.nsmallest(k, self.counter.totals.items(), key=lambda kv: (-kv[1], kv[0]))

    def retained(self) -> list[LogEntry]:
        with self.lock:
            return self.policy.entries()

6. Extensions, concurrency and what interviewers probe

• Out-of-order timestamps: a late event inside the window lands in its own bucket, which the bucket dictionary and the heap of seconds allow. Later than the window, it is dropped; say so as a stated assumption, because a global counter would count it wrongly.
• Dedup variant: dropping duplicates within the window is the logger rate limiter shape. Rejected events must not enter the accepted history, so the check belongs before counter.add.
• Boundary: the window here is half-open, (now minus W, now]. Writing the expiry with < instead of <= counts one extra second, and this is the usual bug.
• Concurrency: one lock is the honest first answer, because a query mutates by expiring. Shards by message hash reduce contention, but top_k must then merge every shard's candidates.
• Scale: if distinct messages exceed memory, a count-min sketch with a small heap gives approximate top k; say that it trades exactness and cannot subtract cleanly over sliding windows without bucketed sketches.
• Test first: counts age out at exactly W; a tie orders by text; k larger than distinct messages returns all; a capacity of two evicts the lowest importance but leaves the count intact.
• Common mistake: starting to code before fixing the method signatures. This prompt is deliberately vague, and interviewers grade the questions you ask first.

02Where this question was reported

• FastPrep · Follow-up: timestamps arrive out of order; rejected events don't enter accepted history; per-message independent windows
• LeetCode Discuss · Open-ended: candidate had to define methods, assumptions and tests; follow-up variant drops messages duplicated within the window
• Land the Lab · 'Logger that reports its top K messages'; also 'Log manager that evicts the least important logs'
• techprep.app · Named as a typical Google LLD prompt alongside parking lot and in-memory file system
• vikyding.gitbooks.io · LC 359 in a Google-tagged collection
• Taro · Taro problem page; boundary (>= vs >) is the usual mistake
• PracHub · Google tech screen; frequency counting, interval query, heap top-K