Find a Lexicographically Optimal Robot Path with Charging Cells
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find a Lexicographically Optimal Robot Path with Charging Cells
You are given a rectangular grid containing:
- `S`: the robot's start cell, exactly once.
- `E`: the destination cell, exactly once.
- `C`: a charging cell.
- `.`: an open cell.
- `#`: a blocked cell.
The robot moves one cell up, left, right, or down, and each move consumes one unit of battery. It starts with a full battery of capacity `B`; entering a charging cell immediately refills the battery to `B`.
For any path, define:
1. `chargingCellsUsed`: the number of times the path enters a `C` cell.
2. `batteryRequired`: the smallest capacity `B` that makes the complete path feasible.
3. `moves`: the number of moves in the path.
Choose a path that lexicographically minimizes `(chargingCellsUsed, batteryRequired, moves)`. If several paths have the same three values, choose the path whose sequence of flattened cell indices is lexicographically smallest, where `(row, col)` maps to `row * columnCount + col`.
Implement:
```text
optimalRobotPath(grid) -> integer[]
```
Return `[chargingCellsUsed, batteryRequired, moves, pathIndex0, pathIndex1, ...]`, including the start and destination indices. Return `[-1]` if no path exists.
## Constraints
- `1 <= rows, columns <= 20`
- `rows * columns <= 400`
- A path may enter the same charging cell more than once, although extra cycles cannot improve the three optimization criteria.
## Examples
### Example 1
```text
grid = ["S.C", "...", "..E"]
output = [0, 4, 4, 0, 1, 4, 5, 8]
```
The selected path avoids charging cells, needs capacity 4, and moves along flattened indices `[0, 1, 4, 5, 8]`. Other no-charger four-move paths have the same first three metrics, but their index sequences are lexicographically larger.
### Example 2
```text
grid = ["S#E", ".C.", "###"]
output = [1, 2, 4, 0, 3, 4, 5, 2]
```
The only route enters the charging cell at index 4. Its longest segment between the start, recharge, and destination is two moves.
Quick Answer: Find a deterministic robot path through a blocked grid with automatic charging cells. The objective first minimizes charging-cell use, then required battery capacity, then moves, with a final path tie-break and an explicit flattened-index return format.
You are given a rectangular grid with exactly one start cell S, exactly one destination E, charging cells C, open cells represented by a dot, and blocked cells #. The robot moves one cell up, left, right, or down. Each move consumes one battery unit, the robot starts with a full battery of capacity B, and entering C immediately refills it to B. For a path, chargingCellsUsed is the number of times it enters C, batteryRequired is the smallest B that makes the whole path feasible, and moves is its move count. Choose the path that lexicographically minimizes (chargingCellsUsed, batteryRequired, moves). Break any remaining tie by the lexicographically smallest sequence of flattened indices row * columnCount + column. Return [chargingCellsUsed, batteryRequired, moves, pathIndex0, pathIndex1, ...], including S and E. Return [-1] when no path exists.
Constraints
- 1 <= rows, columns <= 20
- rows * columns <= 400
- The grid is rectangular and contains exactly one S and exactly one E.
- Grid cells are S, E, C, dot, or #.
- Movement is one cell up, left, right, or down.
- A path may enter the same charging cell more than once, although extra cycles cannot improve the three optimization criteria.
Examples
Input: (['SE'],)
Expected Output: [0, 1, 1, 0, 1]
Explanation: Adjacent endpoints need one battery unit and one move.
Input: (['S#E'],)
Expected Output: [-1]
Explanation: The single row has no passable route.
Hints
- Every path can be split into segments at the charging cells it enters.
- Apply the optimization priorities in order before comparing flattened index sequences.