Retry with Exponential Backoff

Build a retry wrapper with exponential backoff — the single most common reliability primitive around a flaky call (an LLM API, a tool HTTP request, a rate-limited endpoint). The interviewer wants to see correct attempt counting, a growing backoff, and a sleep you can inject so the behavior is deterministic and testable.

How backoff works

You call fn(). If it succeeds, you return its result. If it raises, you wait a bit and try again — and each wait is longer than the last so you back off a service that is under pressure.

For retry attempt attempt (0-indexed: the first retry is attempt = 0), the wait is:

delay = base_delay * 2**attempt + jitter
jitter = 0.1 * base_delay * attempt

The jitter here is deterministic (a fixed function of attempt) so the test can assert exact delays. In production you would randomize it to avoid thundering-herd sync, but a gradeable exercise keeps it reproducible.

You sleep by calling the injected sleep(delay) — not time.sleep — so tests run instantly and can record every delay.

Task

Complete retry(fn, max_retries, base_delay, sleep):

1. Attempt fn(). On success, return its result immediately.
2. On exception, if any retries remain, compute delay = base_delay * 2**attempt + 0.1 * base_delay * attempt, call sleep(delay), then try again.
3. After the final attempt fails (a total of max_retries + 1 calls to fn), re-raise the last exception.

Example

calls = []
delays = []

def flaky():
    calls.append(1)
    if len(calls) < 3:          # fail twice, then succeed
        raise ValueError("boom")
    return "ok"

def sleep(s):
    delays.append(s)

retry(flaky, max_retries=3, base_delay=1.0, sleep=sleep)  # -> "ok"
# len(calls) == 3
# delays == [1.0, 2.1]   # attempt 0: 1*1 + 0; attempt 1: 1*2 + 0.1

Constraints

• Do not call time.sleep or any real timer — use the injected sleep.
• max_retries counts retries, not total attempts: fn is invoked at most max_retries + 1 times.
• If max_retries == 0, call fn exactly once and let any exception propagate (no sleep).
• Do not swallow the final failure — re-raise the exception from the last attempt unchanged.

Approach

Loop over attempt indices 0..max_retries. Try fn() inside the loop and return on success. On failure, if this was the last allowed attempt re-raise, otherwise compute the exponential backoff base_delay * 2**attempt plus a deterministic jitter, sleep via the injected sleeper, and continue. Injecting sleep keeps the whole thing time-free and deterministic.

Solution

from typing import Callable, TypeVar

T = TypeVar("T")

def retry(
    fn: Callable[[], T],
    max_retries: int,
    base_delay: float,
    sleep: Callable[[float], None],
) -> T:
    for attempt in range(max_retries + 1):      # +1: the initial try plus max_retries retries
        try:
            return fn()
        except Exception:
            if attempt == max_retries:          # last attempt failed -> give up
                raise
            delay = base_delay * 2**attempt + 0.1 * base_delay * attempt
            sleep(delay)

Walkthrough

On the example (max_retries=3, base_delay=1.0):

1. attempt = 0: flaky() raises. Not the last attempt, so delay = 1.0 * 2**0 + 0.1*1.0*0 = 1.0; sleep(1.0) records 1.0.
2. attempt = 1: flaky() raises again. delay = 1.0 * 2**1 + 0.1*1.0*1 = 2.1; sleep(2.1) records 2.1.
3. attempt = 2: flaky() now returns "ok", which we return.

fn ran 3 times and delays == [1.0, 2.1], matching the expected output. Had it kept failing, attempt = 3 (== max_retries) would raise the last ValueError.

Complexity & notes

• Time is O(max_retries) loop iterations of bookkeeping (the real cost is dominated by fn and the sleeps). Space is O(1).
• The attempt == max_retries guard is what turns “sleep then retry” into “give up and re-raise” — without it you would either sleep after the final failure or swallow the error.
• except Exception deliberately does not catch BaseException (e.g. KeyboardInterrupt, SystemExit), so a Ctrl-C still interrupts; catching those would trap the process in the retry loop.
• Real implementations add a max_delay cap, randomized jitter to de-synchronize many clients, and retry only on retryable exceptions (timeouts, 429/503) while failing fast on programming errors like a 400. The deterministic jitter here exists only so the exercise is checkable by hand.