JP Morgan·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

JP Morgan coding round, just one algorithmic problem about gas stations on a circular route. Pretty classic greedy problem but the pressure of a finance interview made me second-guess myself the whole time.

Questions Asked (1)

Given n gas stations arranged in a circle, each with a known amount of gas and a known travel cost to the next station, find the starting station index from which you can complete a full loop clockwise with an empty tank. Return -1 if no such starting point exists.

Algorithms & Data Structures

Author's notes

I knew this problem but still fumbled explaining my reasoning out loud.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a greedy approach: iterate through stations while tracking the current gas surplus and total surplus. If the current surplus drops below zero, reset the starting point to the next station and reset the current surplus. After one pass, if the total surplus is non-negative, return the last reset starting point; otherwise, return -1.

Pro tip: Mention that the problem is equivalent to finding the starting index in a circular array where the cumulative sum of (gas - cost) never drops below zero. Emphasize that the greedy choice is safe because if a valid tour exists, it must start after the last point where the cumulative sum was minimal.

1. Understand the problem

Restate the problem: given arrays gas and cost, find the starting index for a circular tour with non-negative gas at all times. Clarify that if no solution exists, return -1.

2. Check feasibility

Compute the total gas and total cost. If total gas < total cost, no solution exists; return -1 immediately.

3. Greedy single-pass algorithm

Initialize start = 0, current_tank = 0, total_tank = 0. For each station i, update current_tank += gas[i] - cost[i] and total_tank += gas[i] - cost[i]. If current_tank < 0, set start = i + 1 and reset current_tank = 0.

4. Return result

After the loop, if total_tank >= 0, return start; otherwise, return -1. Explain why this works: the start is the first station after the last deficit.

5. Analyze complexity

State that the algorithm runs in O(n) time and O(1) space, which is optimal. Mention that a brute-force approach would be O(n^2).

Key Points to Mention

The problem is a classic greedy algorithm problem (LeetCode 134: Gas Station).
The key insight: if the total gas is at least the total cost, a solution is guaranteed, and the starting point is the station after the last point where the cumulative sum was negative.
Maintain two variables: current_tank (since last reset) and total_tank (overall).
When current_tank becomes negative, reset the starting point to the next station and reset current_tank to 0.
Time complexity O(n) and space complexity O(1).
Edge cases: empty input, single station, and cases where total gas equals total cost.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.