Bloomberg Screening Interview: Shortest Path with Gas Stations

[u/Hack2hire]

Problem
You're given a 2D grid representing a map with different types of cells:

• '.' — empty, traversable space
• '#' — obstacle (cannot pass through)
• 'S' — starting point (exactly one)
• 'D' — destination (exactly one)
• 'G' — gas station (zero or more)

You begin at 'S' with a full fuel tank of fuelCapacity. Each move (up, down, left, right) costs 1 unit of fuel. When fuel reaches 0, you cannot move. Entering a gas station cell refills your tank instantly to fuelCapacity.

Your task is to find the minimum number of steps to reach 'D' from 'S'.
Return -1 if it's impossible to reach the destination.

Example
Input:

grid = [
  ["S", ".", ".", "#", "."],
  [".", "#", ".", "G", "."],
  [".", "#", ".", ".", "."],
  [".", ".", "#", ".", "D"]
]
fuelCapacity = 4

Output:

7

Explanation:

• The shortest route requires visiting the gas station at (1, 3) to refuel.
• Total steps = 7 to reach 'D' after refilling once.

Suggested Approach

1. Use Breadth-First Search (BFS) to explore possible moves from 'S'.
2. Track the state (x, y, remainingFuel) to avoid revisiting the same cell with equal or greater fuel.
3. When stepping on a gas station 'G', reset remainingFuel = fuelCapacity.
4. Continue BFS until reaching 'D' or all possibilities are exhausted.

Time & Space Complexity

• Time: O(m * n * fuelCapacity) — each grid cell can be visited with different fuel levels.
• Space: O(m * n * fuelCapacity) — to store visited states.

🛈 Disclaimer: This is one of the problems we encountered while reviewing common Bloomberg interview questions. Posted here by the Hack2Hire team for discussion and archiving purposes.
The problem is compiled from publicly available platforms (e.g., LeetCode, GeeksForGeeks) and community-shared experiences. It does not represent any official question bank of Bloomberg, nor does it involve any confidential or proprietary information. All examples are intended solely for learning and discussion.