Oracle·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Oracle SWE coding round, one greedy algorithm problem. Pretty standard stuff but the O(n) insight is the kind of thing that separates a clean answer from a brute-force mess.

Questions Asked (1)

There are n gas stations arranged in a circle. Each station gives you some gas and each leg of the journey costs some gas. Starting with an empty tank, find the index of the station from which you can complete the full loop without running out of gas, or return -1 if it's impossible.

Algorithms & Data Structures

Author's notes

The brute force is obvious and wrong for an interview.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then propose an efficient O(n) greedy solution that tracks total gas balance and current tank balance to identify the valid starting station. Explain the key insight that if total gas is less than total cost, no solution exists; otherwise, the starting point is the station after the last point where the tank went negative.

Pro tip: Mention that the greedy approach works because if a car can't reach station B from A, then no station between A and B can be the start, allowing us to skip them. This demonstrates deep understanding and can impress the interviewer.

1. Clarify and Validate

Ask clarifying questions about input format, constraints, and edge cases (e.g., empty input, negative values). Confirm that gas and cost arrays are of equal length and represent stations in a circle.

2. Check Feasibility

Compute the total gas and total cost. If total gas < total cost, return -1 immediately because the trip is impossible regardless of starting point.

3. Greedy Scan

Iterate through stations, maintaining a running tank balance and a candidate start index. When the tank balance drops below zero, reset the start to the next station and reset the tank balance to zero.

4. Return Result

After the scan, if total gas >= total cost, the candidate start index is the answer; otherwise, return -1. Explain why this works using the circular property.

5. Analyze Complexity

State that the algorithm runs in O(n) time and O(1) space, which is optimal. Discuss potential variations (e.g., if gas and cost are given as separate arrays).

Key Points to Mention

Total gas must be >= total cost for a solution to exist.
Greedy approach: if tank goes negative at station i, no station before i can be the start.
Track total surplus and current surplus separately.
The starting index is the station after the last deficit point.
Time complexity O(n), space complexity O(1).
Edge cases: single station, all stations have enough gas, no solution.

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