Coding Interview: Implement a Hashed Timing Wheel Timer

Prompt and context

This question tests whether you can choose a data structure for many approximate timers. A binary heap orders deadlines, so insertion and deletion maintain heap order; a timing wheel maps deadlines into buckets and fits network timeouts, retries, and connection keepalives where exact timing is unnecessary. Explain precision, complexity, cancellation semantics, long delays, and the execution-thread boundary.

What the interviewer is evaluating

• Whether you connect the tick, bucket count, covered span, and task deadline precisely.
• Whether you handle tasks crossing a rotation, work in the current bucket, late ticks, and early execution.
• Whether cancellation is cheap and cancelled nodes cannot execute accidentally.
• Whether you can explain thread safety, callback isolation, clock choice, and overload behavior.

Clarifying questions to ask first

Confirm the task volume, earliest and latest error allowed, minimum and maximum delay, cancellation ratio, and callback duration. Must tasks be durable, and should they survive a process restart? Can multiple threads call schedule and cancel? May callbacks block? If one tick contains too many due tasks, should execution be delayed, low-priority work dropped, or backpressure applied? These answers determine whether one wheel is enough or whether you need a hierarchical wheel or external persistence.

A 30-second answer framework

I would compute relative deadlines with a monotonic clock and advance a cursor at a fixed tick. For each task, calculate a bucket index and remaining rounds, then store it in a doubly linked list. On each tick, scan only the current bucket: decrement and retain tasks with remaining rounds, and remove due tasks for execution when the rounds reach zero. A handle lets cancel mark and unlink a node. The wheel schedules work but never runs user callbacks on the tick thread; precision, concurrency, and overload behavior are verified with tests and metrics.

Step-by-step deep dive

1. Define wheel parameters and error

Let tickDuration be the tick and wheelSize the number of buckets; one rotation covers tickDuration × wheelSize. Convert a deadline to relative ticks, then compute (currentTick + remainingTicks) mod wheelSize. The tick determines minimum resolution, while the rotation span determines which delays fit directly. For a larger range, use a hierarchical wheel or keep a remaining-rounds value until the task can be placed more precisely.

2. Choose task nodes and bucket structure

Each node stores a deadline, remainingRounds, callback, cancellation flag, and previous and next pointers. A doubly linked list gives constant-time insertion and removal when the node is known; a handle can point directly to it, so cancel does not search. Do not keep every task in an array and scan all of them on each tick, because the cost grows with the total task count.

3. Advance ticks and handle rotations

Advance the monotonic clock and cursor, then detach the current bucket. If remainingRounds is positive, decrement it and reinsert the node. Otherwise compare the actual deadline: re-bucket a task that is still early and submit only a task that is due. If a thread pause skips many ticks, cap the catch-up work and record delay so recovery does not block for an unbounded time.

4. Handle schedule, cancel, and races

A producer queue can send schedule and cancel requests to one tick thread, reducing bucket-lock contention. Cancel sets the flag before attempting to unlink; after the tick thread takes a node from a bucket, it checks the flag again so a race cannot run a cancelled callback. A deadline earlier than now should be defined as “run on the next available tick,” not converted with a negative modulo into an arbitrary future bucket.

5. Isolate callbacks and overload

The tick thread only moves nodes and submits work; a bounded executor runs user callbacks. When it is full, define a policy such as queue limits, dropping discardable work by priority, delaying non-critical work, or returning an overload error. Track expiry delay, bucket-scan time, cancellations, executor queue length, and callback failures to determine whether the wheel or the downstream executor is the bottleneck.

6. Fix the core invariant with pseudocode

The core loop can be expressed as follows; locking and thread ownership depend on the implementation language:

schedule(task, deadline):
    ticks = ceil((deadline - now) / tickDuration)
    ticks = max(ticks, 0)
    node.rounds = ticks / wheelSize
    node.bucket = (currentTick + ticks) % wheelSize
    buckets[node.bucket].append(node)
    return node.handle

advance(now):
    while currentTick <= floor(now / tickDuration):
        bucket = buckets[currentTick % wheelSize]
        for node in bucket.detachAll():
            if node.cancelled: continue
            if node.rounds > 0:
                node.rounds -= 1
                bucket.append(node)
            elif node.deadline <= now:
                executor.submit(node.callback)
            else:
                schedule(node, node.deadline)
        currentTick += 1

Model high-quality answer

I would first confirm error tolerance, delay range, cancellation ratio, durability, and callback blocking. I would use a monotonic clock and fixed ticks, with doubly linked bucket lists whose nodes store the deadline, remaining rounds, cancellation flag, and handle. Schedule computes the bucket and rounds; cancel unlinks through the handle and sets the flag. The tick thread processes only the current bucket, decreases rounds for future rotations, and submits due callbacks to a bounded executor. Catch-up after skipped ticks is capped and measured; executor overload has queue, priority, and failure policies. Tests cover boundary deadlines, long delays, repeated cancellation, concurrent schedule/cancel, clock jumps, callback exceptions, and scan cost with millions of nodes. If tighter error or a wider range is required, add a hierarchical wheel or a heap rather than claiming the wheel is always faster.

Common mistakes

• Using wall-clock time for relative delays and ignoring system-clock adjustments.
• Forgetting remainingRounds, causing a task to fire on the first rotation.
• Executing or silently losing a current-bucket task that is not due yet.
• Setting a cancellation boolean without checking it again after taking the node.
• Running user callbacks synchronously on the tick thread and stalling the wheel.
• Scanning a fixed array of every task and losing sparse scheduling efficiency.
• Omitting behavior for skipped ticks, overload, restart recovery, and callback failures.

Follow-up questions and responses

Why not use a min-heap?

A min-heap fits smaller workloads or strict deadline ordering, but each insertion or removal maintains heap order. A timing wheel trades precision for constant-time bucket placement and removal, which fits many approximate timers. Choose from the error budget and operation distribution instead of claiming the wheel is always faster.

What if the tick thread pauses for several seconds?

Use monotonic time to calculate the ticks that should have elapsed, cap the number of buckets or tasks processed in one catch-up pass, and leave the rest for later. Measure scheduling delay; if a burst is unacceptable, combine batching with backpressure rather than running every callback synchronously during recovery.

How do you ensure cancel cannot execute a task?

The handle points to the node. Cancel atomically marks it before unlinking, and the tick thread checks the flag again after detaching it. If the callback is already submitted, define the cancellation linearization point and have the callback check task state before starting.

When do you need a hierarchical timing wheel?

Use one when a single rotation cannot cover the largest deadline or task delays span several orders of magnitude. Add coarser upper levels and cascade tasks downward, while defining each level's precision, degradation, and migration cost. Durability and crash recovery still require separating the wheel from reliable storage or messaging.