CODING CHALLENGE · N°64

Exponential Backoff with Full Jitter

Medium FDEReliabilityIntegrations

When a customer’s API throws 503s, everyone retrying on the same doubling schedule stampedes it in sync. Full jitter spreads the retries randomly across the window so the herd disperses. Compute the delay schedule. (Random draws are supplied, so it’s deterministic.) Solve it in Python or TypeScript, with hidden tests.

The problem

Implement backoff_jitter(base, cap, attempts, rand). For attempt i (0-indexed), the exponential ceiling is min(cap, base * 2^i). With full jitter, the actual delay is a uniform random value in [0, ceiling]: here that random fraction is supplied as rand[i] in [0, 1], so the delay is rand[i] * ceiling. Return the list of attempts delays, each rounded to 4 decimals.

EXAMPLE 1

Input base = 1.0, cap = 10.0, attempts = 5, rand = [1.0, 0.5, 1.0, 0.5, 0.0]

Output [1.0, 1.0, 4.0, 4.0, 0.0]

ceilings 1,2,4,8,10; ×rand → 1, 1, 4, 4, 0

CONSTRAINTS

Ceiling for attempt i is min(cap, base * 2^i) — exponential growth, clamped at cap.
Full jitter: delay = rand[i] * ceiling (a fraction of the ceiling, not the ceiling itself).
Round each delay to 4 decimal places. rand has at least attempts entries.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement backoff_jitter(base, cap, attempts, rand): for each attempt compute the clamped exponential ceiling, multiply by the supplied random fraction, round to 4 decimals, and collect the delays.

HINTS — 3 IDEAS

Ceiling: min(cap, base * (2 ** i)) for i in 0 … attempts-1.
Full jitter multiplies that ceiling by rand[i] (in [0,1]) — so a retry lands anywhere in the window, not on a synchronized tick.
Round to 4 decimals so floating-point noise doesn’t leak into the result.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Grow the delay exponentially with the attempt number — base × 2^attempt — and cap it at a maximum so it cannot run away. Then add jitter: instead of the exact computed delay, pick a random delay within the window (full jitter chooses uniformly in [0, computed]). The exponent spaces out retries; the jitter de-synchronizes clients.

Complexity

Time O(1) to compute each delay.

Common mistakes

Exponential growth with no cap — delays explode into minutes or hours.
No jitter — every client retries on the same doubling schedule and stampedes the recovering service in lockstep (a thundering herd).
Jittering the wrong range, or resetting the attempt counter at the wrong time.

Where this shows up

Exponential backoff with jitter is the standard retry strategy for any flaky dependency — APIs, databases, queues. The jitter is the crucial part: when a service returns 503s, un-jittered retries all fire together and re-stampede it in sync, so spreading them randomly across the window is what actually lets it recover.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Forward Deployed Engineering