Background Jobs with Exponential Backoff
Shopify● MediumINTERNPHONE SCREENProblem statement
Process background jobs that can fail, retry with exponential backoff, and eventually succeed or exhaust their retry budget.
For this exercise, assume all jobs start at virtual time 0. They run independently, so one job's wait never blocks another job. Each attempt takes one unit of virtual time. Job i fails its first failuresBeforeSuccess[i] attempts and succeeds on the next attempt if the retry budget permits it.
For this exercise, assume maxRetries counts retries after the first attempt. After failed attempt number a, wait baseDelay * 2^(a - 1) units before starting the next attempt. Do not wait or start another attempt after success or after using every allowed retry.
Return one row per job, in input order: [success, attempts, finishedAt]. Here success is 1 for success or 0 for exhausted retries, attempts includes the first attempt, and finishedAt is the time its last executed attempt finishes. Use virtual time; do not sleep.
Function
processJobs(failuresBeforeSuccess: int[], maxRetries: int, baseDelay: int) → int[][]Examples
Example 1
failuresBeforeSuccess = [0,2,5]maxRetries = 2baseDelay = 3return = [[1,1,1],[1,3,12],[0,3,12]]Job 0 succeeds at time 1. For each other job, attempts run during [0,1], [4,5], and [11,12], with waits of 3 and 6. Job 1 succeeds on attempt 3; job 2 still fails and has no retries left. Their waits do not delay job 0.
Example 2
failuresBeforeSuccess = [1,0]maxRetries = 0baseDelay = 10return = [[0,1,1],[1,1,1]]Both jobs execute one attempt ending at time 1. The first fails and the second succeeds. No retry means no backoff wait is added.
Constraints
0 <= failuresBeforeSuccess.length <= 10000 <= failuresBeforeSuccess[i] <= 310 <= maxRetries <= 201 <= baseDelay <= 1000