Circular Race Track Gas Can Strategy

This brain teaser describes a car on a circular track with fuel placed at various points and just enough total fuel to complete a lap. The candidate is asked whether a suitable starting point is always guaranteed, and to justify the reasoning rigorously rather than by example or guesswork. It's a canonical version of the gas-station or circular tour problem, common in algorithmic interviews and sometimes in quantitative trading or software roles where candidates are expected to reason clearly about invariants on a cycle.

The solution path leans on cumulative sums, surplus–deficit reasoning, and how minima of a running total behave on a circle. Strong answers typically recast the problem in terms of prefix sums around a loop, then argue about where the "lowest point" must occur and what starting there implies. Interviewers look for the ability to formalize intuition, avoid hidden assumptions, and give a clean existence proof rather than an ad hoc construction or simulation. They also watch how the candidate structures the argument and checks edge cases.

What it tests

This problem class is governed by the principle of cumulative surplus and deficit in circular systems, often called the 'circular tour' or 'gas station' problem. The key insight is that if the total resource (here, gasoline) exactly matches the total requirement (the distance to be traveled), then there must exist at least one starting point where the cumulative surplus never becomes negative as you traverse the cycle. This is because any deficit accumulated up to the lowest point is exactly offset by the surplus that follows, due to the total sum being zero. The reason this pattern holds is that, in a cycle, the lowest point in the running total marks a reset: starting there, you always have enough to continue, since the total never dips lower. This is a consequence of the pigeonhole principle applied to cumulative sums around a loop, ensuring at least one viable starting position.