Design a timer that supports many concurrent timers

01The design, in the six-step framework

1. Requirements and use cases

You are handed a class with exactly one timer: set it for a delay and it calls you back once; you may cancel it. Build add_timer(delay, callback) so that thousands of callers can each schedule their own callback, each fires once at its own time, and any of them can be cancelled before firing. Callbacks may themselves add new timers.

Out of scope: repeating timers (a callback can re-add itself), wall-clock scheduling across daylight-saving changes, and running callbacks on a pool; they run on the tick thread one after another.

Constraints: only one hardware timer exists, so the service must always keep it pointed at the earliest live deadline; adding a timer must be O(log n); cancelling must be O(1); a callback that throws must not stop the ones due at the same instant.

2. Core entities and relationships

• OneShotTimer: the given primitive, expressed as a protocol so a software stand-in (ThreadOneShot) can replace the hardware in tests.
• TimerService: the multiplexer. It keeps every pending deadline in a heap and re-arms the single primitive whenever the earliest deadline changes.
• Deadline: a heap record: the absolute time, a sequence number, the callback and its handle.
• TimerHandle: what the caller keeps; cancellation is a flag read when the entry reaches the top.

The service composes its deadlines and merely uses the one primitive; the protocol boundary is the seam that makes the whole thing testable without sleeping (see abstraction and interfaces).

3. Interfaces and key methods

class OneShotTimer(Protocol):
    """The given primitive: a single hardware or OS timer."""
    def set(self, delay: float, callback: Callable[[], None]) -> None: ...
    def cancel(self) -> None: ...

class TimerHandle:
    def cancel(self) -> bool: ...          # True iff not yet fired

class TimerService:
    def __init__(self, hw: OneShotTimer, clock: Callable[[], float]) -> None: ...
    def add_timer(self, delay: float, callback: Callable[[], None]) -> TimerHandle:
        """Fire callback once, delay seconds from now; thousands may be pending."""
    def pending(self) -> int: ...

Invariants: _armed_for is either None or equal to the smallest live at in the heap; a handle fires at most once; cancelled entries are lazily dropped only when they reach the heap top, so the heap may be larger than pending().

4. Design patterns and the choices behind them

A heap of absolute deadlines

What varies is which timer is next. Storing relative delays would require decrementing every entry on each tick (O(n) per tick); storing absolute times in a min-heap makes add O(log n) and next O(1). The absolute times come from an injected monotonic clock, never wall time, so a clock adjustment cannot fire everything at once (see time and expiry inside objects).

Lazy cancellation

Removing from the middle of a heap is O(n). A cancelled handle is only flagged; _rearm_locked and _on_tick skip flagged entries when they surface. The cost is memory for cancelled entries until they are reached, acceptable for timers whose lifetimes are bounded; a compaction when cancelled entries exceed half the heap is the usual add-on.

Re-arm only when the earliest changes

Every add compares the new heap top with _armed_for. Most adds land behind the current earliest and touch the hardware not at all; an earlier one cancels and re-sets it. Setting the hardware on every add was rejected because hardware set and cancel are often slow calls.

Callbacks outside the lock

A callback that calls add_timer would deadlock if the lock were held during callbacks. Due entries are collected under the lock, the timer is re-armed, and only then are callbacks invoked, in deadline order.

5. Core flow and code

1. add_timer(5, a): heap empty, so the primitive is set for 5 s and _armed_for records that deadline.
2. add_timer(2, b): the new top is earlier, so the primitive is cancelled and re-set for 2 s.
3. add_timer(9, c): lands behind the top; the hardware is untouched.
4. The caller cancels c: the flag flips, the heap is unchanged, O(1).
5. At 2 s the primitive calls _on_tick: b is popped as due, _armed_for is cleared, the heap top is a at 5 s so the primitive is re-armed for 3 s more, and b's callback runs outside the lock.
6. At 5 s a fires; the next top is c, flagged, so it is dropped and the primitive is left disarmed.

import heapq, itertools, threading, time
from dataclasses import dataclass, field
from typing import Callable, Protocol

class OneShotTimer(Protocol):
    def set(self, delay: float, callback: Callable[[], None]) -> None: ...
    def cancel(self) -> None: ...

class TimerHandle:
    def __init__(self) -> None:
        self.cancelled = False
        self.fired = False

    def cancel(self) -> bool:
        if self.fired or self.cancelled:
            return False
        self.cancelled = True
        return True

@dataclass(order=True)
class Deadline:
    at: float
    seq: int
    callback: Callable[[], None] = field(compare=False)
    handle: TimerHandle = field(compare=False)

class TimerService:
    def __init__(self, hw: OneShotTimer, clock: Callable[[], float] = time.monotonic) -> None:
        self._hw = hw
        self._clock = clock
        self._heap: list[Deadline] = []
        self._seq = itertools.count()
        self._lock = threading.Lock()
        self._armed_for: float | None = None      # deadline the hardware timer is set for

    def add_timer(self, delay: float, callback: Callable[[], None]) -> TimerHandle:
        if delay < 0:
            raise ValueError("delay must be non-negative")
        handle = TimerHandle()
        with self._lock:
            heapq.heappush(self._heap, Deadline(self._clock() + delay, next(self._seq), callback, handle))
            self._rearm_locked()
        return handle

    def pending(self) -> int:
        with self._lock:
            return sum(1 for d in self._heap if not d.handle.cancelled)

    def _rearm_locked(self) -> None:
        """Point the single hardware timer at the earliest live deadline."""
        while self._heap and self._heap[0].handle.cancelled:
            heapq.heappop(self._heap)
        if not self._heap:
            if self._armed_for is not None:
                self._hw.cancel(); self._armed_for = None
            return
        earliest = self._heap[0].at
        if self._armed_for != earliest:
            self._hw.cancel()
            self._hw.set(max(0.0, earliest - self._clock()), self._on_tick)
            self._armed_for = earliest

    def _on_tick(self) -> None:
        due: list[Deadline] = []
        with self._lock:
            now = self._clock()
            while self._heap and self._heap[0].at <= now:
                d = heapq.heappop(self._heap)
                if not d.handle.cancelled:
                    d.handle.fired = True
                    due.append(d)
            self._armed_for = None
            self._rearm_locked()
        for d in due:                 # callbacks outside the lock: they may add timers
            try:
                d.callback()
            except Exception:
                pass                  # a bad callback must not stop the others

class ThreadOneShot:
    """A software stand-in for the primitive, for tests and demos."""
    def __init__(self) -> None:
        self._t: threading.Timer | None = None

    def set(self, delay: float, callback: Callable[[], None]) -> None:
        self._t = threading.Timer(delay, callback); self._t.daemon = True; self._t.start()

    def cancel(self) -> None:
        if self._t:
            self._t.cancel()

6. Extensions, concurrency and what interviewers probe

• Repeating timers: a period on Deadline and a re-push in _on_tick before callbacks run; the handle's fired flag becomes a count.
• Run callbacks on a pool: hand each due entry to an executor so one slow callback cannot delay the next tick; ordering guarantees then need stating.
• The atomic step: pop-and-mark-fired under the lock, so a cancel racing with a fire sees a consistent answer; cancel returns False once fired is set.
• Clock drift: if the hardware fires early, _on_tick finds nothing due and simply re-arms for the remainder; if it fires late, several entries are due and all run in order.
• Test first: with a fake clock and a fake primitive that records set and cancel calls, assert three adds produce exactly two hardware sets; then advance the clock and call the recorded callback, asserting fire order and that a cancelled timer never fires.
• Common mistake: spawning one thread per timer, which answers the question without using the given primitive and falls over at thousands of timers.

02Where this question was reported

• LeetCode Discuss · Given a class with one timer method, build addTimer supporting many concurrent timers
• Glassdoor · SWE: 'OOP design class to create timer object'
• 1point3acres · Google engineering OA with a challenging OOD timer implementation (snippet only)