FastPrepBest Restart Cutoff for a Long-Tailed Job
Problems/Best Restart Cutoff for a Long-Tailed Job

Best Restart Cutoff for a Long-Tailed Job

OpenAI logoOpenAI● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A report from April 2026 on an OpenAI research onsite describes a probability round on restarts. Some runs of a job take much longer than others, and the question is when it pays to kill a run and start over. Only that topic was kept. The report gives no numbers, distribution or expected answer.

Here the runtime distribution is a list of samples, the strategy is a fixed cutoff, and the expected total time is the average length of one attempt divided by the chance that an attempt finishes. The tie rule, the limits and the examples are ours.

Our version is about 35% the same as the reported question.

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[]) → int

Examples

Example 1

runtimes = [2,50,2,2]return = 2

With 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 = 5

Here 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 = 2

The 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^4
  • 1 <= 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
All OpenAI interview questionsSee OpenAI hiring insights
Saved
class Solution {
    public int bestRestartCutoff(int[] runtimes) {
        // Write your code here.
    }
}
Checking account…