Best Restart Cutoff for a Long-Tailed Job
Updated
Problem statement
A randomized job may need a different amount of time on every start, and separate starts are independent. You started it n times and wrote down how long each start took to finish: that is the array runtimes. Treat these samples as the exact distribution: a new start needs runtimes[i] time units with probability 1 / n for each index i.
A few starts take far longer than the rest. To finish sooner on average, pick a restart cutoff T, a positive integer, and follow this rule: start the job; if it has not finished after T time units, kill it and start again; keep going until some start finishes. A start that needs exactly T units finishes. Killing and restarting take no extra time.
Let k(T) be the number of samples that are at most T, and S(T) the sum of min(runtimes[i], T) over all samples. With cutoff T, the expected total time until the job finishes is
E(T) = S(T) / k(T)
because one start takes S(T) / n on average and finishes with probability k(T) / n. If k(T) = 0, no start ever finishes and E(T) is infinite.
Return the cutoff T with the smallest E(T). If several cutoffs reach that smallest value, return the smallest such T. A cutoff at or above the largest sample never kills a run, so that choice means never restarting.
Function
bestRestartCutoff(runtimes: int[]) → intExamples
Example 1
runtimes = [2,50,2,2]return = 2With cutoff T = 2, an attempt finishes 3 times out of 4. Every attempt costs 2 time units: the slow run is stopped at 2. The expected total is (2 + 2 + 2 + 2) / 3 = 8 / 3, about 2.67.
With T = 50 we never restart, so the expected total is the plain average (2 + 50 + 2 + 2) / 4 = 14. Any cutoff from 3 to 49 has the same 3 in 4 chance as T = 2 but makes failed attempts longer, and T = 1 never finishes. So the answer is 2.
Example 2
runtimes = [5,3,4]return = 5Here the runtimes are close together, so restarting does not pay. T = 3: only the run of 3 finishes, each attempt costs 3, so the expected total is 9 / 1 = 9. T = 4: attempt costs add up to 3 + 4 + 4 = 11 and 2 runs finish, giving 5.5. T = 5: never restart, (5 + 3 + 4) / 3 = 4. The best is 5.
Example 3
runtimes = [7,1,4,2]return = 2The order of the samples does not matter. Sorted, they are 1, 2, 4, 7. T = 1 gives 4 / 1 = 4. T = 2 gives (1 + 2 + 2 + 2) / 2 = 3.5. T = 4 gives (1 + 2 + 4 + 4) / 3, about 3.67. T = 7 gives 14 / 4 = 3.5.
Cutoffs 2 and 7 tie at 3.5, so the smaller one, 2, is returned.
Constraints
1 <= runtimes.length <= 10^41 <= runtimes[i] <= 10^4
More OpenAI Onsite Interview questions
- Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Rectangle Point Coverage CountsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Message Event AggregationPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- 15-Minute Chat Session TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Segmented Durable Key-Value StorePHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Durable Work Queue OperationsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Versioned Social NetworkPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Budgeted API Inference with Out-of-Order FeedbackONSITE INTERVIEW · Seen Oct 2026
- Plant Infection Simulation, Part 4: Death CountdownPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Count Friend CirclesPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Decision Tree Regression from ScratchNVIDIA · OANVIDIA interview questions
- Possible Timer Intervals with One Wrong ReadingIndeed · OAIndeed interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Meeting Scheduling SystemHevo Data · ONSITE INTERVIEW
- Random Pick with Weight Using Recorded DrawsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Maintain a Consistent-Hashing RingCohesity · ONSITE INTERVIEW
- Text Embedding and Vector SearchNike, Inc. · PHONE SCREEN · ONSITE INTERVIEWNike, Inc. interview questions
- Pythagorean Triple with Array MultiplicityByteDance · ONSITE INTERVIEWByteDance interview questions
- Detect a Server RAM Capacity BreachMyntra · ONSITE INTERVIEWMyntra interview questions
- Car Pooling Capacity CheckGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions