Weather Station Retries

EasysimulationAlso known as Exponential Backoff with a Cap

Two hundred weather stations on a hillside upload a reading every few minutes. When the upload server restarts, every station fails at once. If each one retries every 100 ms, the server comes back to a wall of retries and falls over again. So each station waits longer after every failure: 100 ms, then 200, then 400, doubling up to a ceiling. A reading is useless after a while, so a station also gives up when its total waiting would pass a time budget.

Every client that calls a network service needs this schedule (see Idempotency and Retries and Reliability and Failure). Real clients also add random jitter, for example picking a random wait between 0 and the scheduled value, so stations do not retry in lockstep. Here you compute the schedule that the jitter draws from.

Your task

Write retryDelays(baseMs, capMs, maxRetries, budgetMs). Return the list of waits, in milliseconds, before retry 1, retry 2, and so on.

The wait before retry k (counting from 1) is min(capMs, baseMs × 2^k−1).
There are at most maxRetries retries.
Stop before any retry whose wait would make the total of all waits so far greater than budgetMs. A total exactly equal to the budget is allowed.

Return an empty list if no retry fits.

retryDelays(baseMs: int, capMs: int, maxRetries: int, budgetMs: int) → int[]

Examples

Example 1

Input

baseMs = 100
capMs = 1000
maxRetries = 6
budgetMs = 10000

Output

[100, 200, 400, 800, 1000, 1000]

Why

The waits double from 100: 100, 200, 400, 800. The next would be 1,600, but the cap is 1,000, so retries 5 and 6 wait 1,000 each. The total is 3,500 ms, well inside the 10,000 ms budget, so all 6 retries happen.

Example 2

Input

baseMs = 500
capMs = 4000
maxRetries = 10
budgetMs = 6000

Output

[500, 1000, 2000]

Why

After three retries the station has waited 500 + 1,000 + 2,000 = 3,500 ms. Retry 4 would wait 4,000 ms more, for a total of 7,500, which is over the 6,000 ms budget, so the station gives up there. It does not look for a later, shorter wait: waits never shrink.

Constraints

1 ≤ baseMs ≤ capMs ≤ 3,600,000
0 ≤ maxRetries ≤ 60
0 ≤ budgetMs ≤ 1,000,000,000

Start with brute force

A first version computes baseMs × 2^k−1 with a power function for every retry and then applies the cap. JavaScript and Python give the right answer, but the number in the middle is huge: for retry 60 with a base of 1,000 ms it is about 5.8 × 10²⁰ ms. In a language with 64-bit integers that overflows (the limit is about 9.2 × 10¹⁸) and can come out negative, and a negative wait means retrying instantly, in a tight loop, which is the exact storm backoff exists to prevent.

Doubling a value that is already capped never leaves the range of the constraints, so it avoids the problem with no extra work.

Hints

0 of 4 shown

Hint 1
Write out the first few waits for base 100 and cap 1,000. After which retry does the cap start to matter, and what happens to every wait after that?
Hint 2
Keep the current wait in a variable. After each retry it doubles, but never past the cap: wait = min(wait × 2, cap).
Hint 3
Keep a running total. Before adding a wait, check whether total + wait would exceed the budget. If it would, stop: every later wait is at least as long, so none of them can fit either.
Hint 4
Loop at most maxRetries times; the loop can end early on the budget check. Do not compute 2^k for large k when you can double a capped value instead.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Track two numbers: the next wait and the total waited so far. Each round, check the budget, record the wait, then double it and clamp it to the cap.

Trace the second example, base 500, cap 4,000, budget 6,000:

wait 500, total 0: 0 + 500 ≤ 6,000. Record 500, total 500, next wait 1,000.
500 + 1,000 = 1,500 ≤ 6,000. Record 1,000, total 1,500, next wait 2,000.
1,500 + 2,000 = 3,500 ≤ 6,000. Record 2,000, total 3,500, next wait 4,000.
3,500 + 4,000 = 7,500 > 6,000. Stop. Answer [500, 1000, 2000].

Stopping at the first wait that does not fit is safe because waits never shrink. The cap is what keeps one unlucky client from sleeping for an hour; the budget is what stops it from retrying long after the caller stopped caring.

Reference solution

function retryDelays(baseMs, capMs, maxRetries, budgetMs) {
  const waits = [];
  let wait = baseMs, total = 0;
  for (let k = 1; k <= maxRetries; k++) {
    if (total + wait > budgetMs) break; // later waits are never shorter
    waits.push(wait);
    total += wait;
    wait = Math.min(wait * 2, capMs);   // double, but never past the cap
  }
  return waits;
}

def retry_delays(base_ms, cap_ms, max_retries, budget_ms):
    waits = []
    wait, total = base_ms, 0
    for _ in range(max_retries):
        if total + wait > budget_ms:  # later waits are never shorter
            break
        waits.append(wait)
        total += wait
        wait = min(wait * 2, cap_ms)  # double, but never past the cap
    return waits

TimeO(r)One loop step per retry, and r = maxRetries ≤ 60.

SpaceO(r)The returned list holds at most one wait per retry.

Learn the idea: Idempotency and Retries Reliability and Failure Rate Limiting

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code