Start from brute force
The obvious first draft computes the full exponential, multiplies by the random fraction, and clamps last: min(cap, rand[i] * base * 2**i). It even passes the first example, because the only attempt past the cap there has rand = 0.0. It costs O(attempts) time and O(attempts) space for the list, the same as the right answer, so the problem is not speed: it is wrong. Once base * 2**i passes cap, every draw above cap / (base * 2**i) is clamped to exactly cap. At attempt 6 with base = 1 and cap = 10 that is any draw above 10/64, about 84% of clients, all landing on the same instant again.
The approach
The key insight is the order of operations: clamp the window first, then pick a point inside it. For attempt i the window is [0, ceiling] with ceiling = min(cap, base * 2**i), and full jitter draws the delay from that whole window, so the invariant is 0 ≤ delay ≤ ceiling ≤ cap on every attempt. The exponent spreads one client's retries out over time; the jitter spreads different clients out within each window, so two callers that failed at the same moment are unlikely to retry at the same moment.
The reference solution is one loop. For each i in range(attempts) it computes ceiling = min(cap, base * (2 ** i)), scales it with delay = rand[i] * ceiling, and appends round(delay, 4) to delays. Passing rand in is what makes it testable; production code would call random.uniform(0, ceiling) on that line. The rounding matters because 0.7 * 0.1 is 0.06999999999999999 in binary floating point, and the tests compare exact values.
Walk through an example
Trace backoff_jitter(1.0, 10.0, 5, [1.0, 0.5, 1.0, 0.5, 0.0]): the ceiling doubles until the cap stops it at attempt 4, and each delay is that ceiling scaled by rand[i].
| step | base * 2**i | ceiling | rand[i] | delay | delays |
|---|
| i = 0 | 1.0 | 1.0 | 1.0 | 1.0 | [1.0] |
| i = 1 | 2.0 | 2.0 | 0.5 | 1.0 | [1.0, 1.0] |
| i = 2 | 4.0 | 4.0 | 1.0 | 4.0 | [1.0, 1.0, 4.0] |
| i = 3 | 8.0 | 8.0 | 0.5 | 4.0 | [1.0, 1.0, 4.0, 4.0] |
| i = 4 | 16.0 | 10.0 (capped) | 0.0 | 0.0 | [1.0, 1.0, 4.0, 4.0, 0.0] |
Complexity
Optimal: O(attempts) time, because each attempt is a fixed handful of arithmetic operations, and O(attempts) space for the returned list (O(1) beyond it). Brute force (clamp after jitter) has the same O(attempts) time and space; its flaw is the delays it produces, not what it costs to produce them.
Edge cases to test
attempts = 0 → []. The loop never runs and rand may be empty, so never read rand[0] up front.cap below base: base = 10.0, cap = 3.0, rand = [1.0, 0.5, 0.25] → [3.0, 1.5, 0.75]. Every ceiling is 3.0 from the first attempt.rand[i] = 0.0 → a delay of 0.0. Full jitter allows an immediate retry; do not add a floor the spec does not ask for.- Float noise:
base = 0.1, cap = 5.0, rand = [0.7, 0.7, 0.7] gives raw products such as 0.06999999999999999; after rounding the answer is [0.07, 0.14, 0.28]. - A huge attempt count: in Python
1.0 * 2**1024 raises OverflowError (the integer is too large to convert to a float), while in JavaScript 2 ** 1024 is Infinity and Math.min clamps it to cap. Production code stops doubling once the ceiling reaches cap.
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:
rand[i] * base never grows, and ceiling + rand[i] leaves every client on the same doubling schedule, offset by at most one time unit. - Resetting the attempt counter before a call has actually succeeded, so a flapping dependency is retried at the shortest delay forever.
Follow-ups an interviewer asks next
- How do equal jitter and decorrelated jitter differ from full jitter?
- Equal jitter keeps half the window fixed:
delay = ceiling / 2 + rand * ceiling / 2, so a client always waits at least half the ceiling. Decorrelated jitter drops the attempt number and grows from the previous delay: delay = min(cap, uniform(base, previous * 3)). Full jitter has the widest spread; equal jitter gives some of that spread up in exchange for a guaranteed minimum wait. - The server sends a Retry-After header. Now what?
- Treat it as a floor: wait at least that long, and keep jitter on top (for example
retry_after + rand * ceiling) so every client told “30 seconds” does not return on the same tick. If the requested wait is longer than the operation’s overall deadline, fail fast instead of sleeping through it. - How do you stop retries from making an outage worse?
- Bound them three ways: a maximum attempt count, an overall deadline for the operation, and a retry budget shared by the whole client (retries may be at most a fixed fraction of recent requests). Retry only failures that can succeed later, such as timeouts, 429 and 503, and only operations that are safe to repeat or carry an idempotency key.
- How would you test this with real randomness?
- Inject the random source, as this signature does with
rand, or seed it. Then assert properties instead of exact values: every delay is between 0 and its ceiling, ceilings double until they reach cap, and over many draws the mean delay approaches ceiling / 2, which is what a uniform draw on [0, ceiling] predicts.
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. The AWS Architecture Blog post “Exponential Backoff And Jitter” compares this full-jitter formula with equal and decorrelated jitter in a simulation of clients contending for one resource.
Reference solution
Reference solution — Python
def backoff_jitter(base, cap, attempts, rand):
delays = []
for i in range(attempts):
ceiling = min(cap, base * (2 ** i)) # exponential, clamped at cap
delay = rand[i] * ceiling # full jitter: uniform [0, ceiling]
delays.append(round(delay, 4))
return delays
print(backoff_jitter(1.0, 10.0, 5, [1.0, 0.5, 1.0, 0.5, 0.0])) # -> [1.0, 1.0, 4.0, 4.0, 0.0]
Reference solution — TypeScript
function backoffJitter(base: number, cap: number, attempts: number, rand: number[]): number[] {
const delays: number[] = [];
for (let i = 0; i < attempts; i++) {
const ceiling = Math.min(cap, base * 2 ** i); // exponential, clamped
const delay = rand[i] * ceiling; // full jitter
delays.push(Math.round(delay * 1e4) / 1e4);
}
return delays;
}
console.log(JSON.stringify(backoffJitter(1.0, 10.0, 5, [1.0, 0.5, 1.0, 0.5, 0.0]))); // -> [1,1,4,4,0]