FastPrepGas Station
Problems/Gas Station

Gas Station

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Gas Station came up in the last round of a March 2025 Microsoft SWE intern interview loop (off-campus, India), a round that also had behavioral questions. The interviewer only wanted a working brute force. Making it faster was a talking point rather than something to code.

The report has no statement, so this version uses the familiar setup, and several details are our own choices. The tank starts empty. Fuel is picked up before leaving a station. Reaching a station with zero fuel is fine. The smallest index wins when several starts work, and -1 means none works. The limits are ours too (up to 10^5 stations, values from 0 to 10^4). At that size the brute force is too slow, so you need the faster idea from that discussion.

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

There are n gas stations on a circular road, numbered 0 to n - 1. From station i you drive forward to station i + 1, and from station n - 1 you drive back to station 0.

Station i lets you fill up gas[i] units of fuel. The drive from station i to the next station burns cost[i] units. Your car's tank has no size limit, and it is empty when you start.

Choose a starting station and drive forward around the whole circle until you reach the start again. At every station on the way, including the first, you fill up there and then drive to the next station. The trip fails if the fuel would drop below zero on any drive. Arriving at a station with exactly zero fuel is allowed.

Return the index of a starting station from which the trip succeeds. If several stations work, return the smallest index. If no station works, return -1.

Function

canCompleteCircuit(gas: int[], cost: int[]) → int

Examples

Example 1

gas = [1,4,2,5]cost = [3,2,4,1]return = 1

The net change at each station is gas[i] - cost[i]: -2, 2, -2, 4. Station 0 fails at once: it gives 1 unit but the first leg needs 3.

Start at station 1 with an empty tank. Fill up 4 and drive to station 2 using 2, leaving 2. Fill up 2 and drive to station 3 using 4, leaving 0. Fill up 5 and drive to station 0 using 1, leaving 4. Fill up 1 and drive back to station 1 using 3, leaving 2. The tank never drops below zero, so station 1 works.

Station 3 also works, but the answer is the smaller index, 1.

Example 2

gas = [3,1,2]cost = [2,3,2]return = -1

The stations give 3 + 1 + 2 = 6 units in total, but one full trip uses 2 + 3 + 2 = 7 units. No starting station can finish, so the answer is -1.

Example 3

gas = [0,6,1,0]cost = [2,1,2,2]return = 1

Stations 0 and 3 have no fuel, and station 2 gives 1 unit for a leg of 2, so all three fail on their first leg. From station 1 the tank holds 5 after the first leg, then 4, then 2, then 0 when it arrives back at station 1. Ending the trip with exactly zero fuel is allowed, so the answer is 1.

Constraints

  • 1 <= n <= 10^5
  • gas.length == cost.length == n
  • 0 <= gas[i], cost[i] <= 10^4

More Microsoft Onsite Interview questions

  • Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
  • Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
  • Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
  • Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
  • Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
  • Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
  • Coin ChangeONSITE INTERVIEW · Seen Oct 2026
  • Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
  • Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
  • Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026

Similar questions at other companies

  • Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
  • Minimum Station Tracks for a Train ScheduleBNSF Railway · ONSITE INTERVIEWBNSF Railway interview questions
  • Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
  • Minimize Total Weight After HalvingAmazon · ONSITE INTERVIEW
  • Gas StationeBay · ONSITE INTERVIEWeBay interview questions
  • Make an Array Non-Decreasing With One ModificationGoogle · ONSITE INTERVIEWGoogle interview questions
  • Wizard Scroll Allocation StrategyJane Street · ONSITE INTERVIEWJane Street interview questions
  • Maximize Compatible Car RidersUber Freight · PHONE SCREEN · ONSITE INTERVIEWUber Freight interview questions
  • Maximize Monsters DefeatedSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions

Interview reports that mention this question

  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // Write your code here.
    }
}
Checking account…