Nearest Fire Station Distance and Capped Charge for Every Residence in a Grid with Lakes
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A city map is a grid in which every cell holds `0` for a fire station, `-1` for a residence, or `-2` for a lake. A fire truck moves one cell at a time up, down, left or right. It may drive through fire stations and residences but never through a lake. For every residence, find its distance from the nearest fire station, then the amount the city pays for a truck to reach it.
In the interview the distances came first and the charges were added as a second part. The report describes the charge as a base cost discounted for the closest residences, the base cost a little farther out, a surcharge that grows with each further step, and a cap, without giving the percentages; this version therefore passes the schedule in as a table of whole-number charges.
### Function Signature
```python
def residence_charges(grid: list[list[int]], charges: list[int]) -> list[list[int]]:
```
### Rules
- The distance of a residence is the smallest number of moves on any route from any fire station to it, where each move goes to an edge-adjacent cell inside the grid and no route enters a lake. This equals the Manhattan distance when no lake is in the way. A reachable residence always has a distance of at least 1.
- A residence at distance `d` costs `charges[d - 1]` when `d <= len(charges)`. For any larger distance the charge is `charges[-1]`, so the last entry acts as the cap.
- A residence that no fire station can reach (for example one cut off by lakes, or any residence when the grid has no fire station) has distance `-1` and charge `-1`.
- Return one `[row, col, distance, charge]` list for every residence, ordered by `row` ascending and then by `col` ascending. Rows and columns are 0-indexed. Return `[]` when the grid has no residence.
### Constraints
- `rows >= 1`, `cols >= 1` and `rows * cols <= 10^5`; every row has the same length.
- Every cell is `0`, `-1` or `-2`. The grid may contain any number of fire stations, including none.
- `1 <= len(charges) <= 10^5`
- `0 <= charges[i] <= 10^9`
### Examples
**Example 1**
```text
Input: grid = [[0, -1, -1], [-2, -2, -1], [-1, -1, -1]], charges = [80, 100, 120, 130]
Output: [[0, 1, 1, 80], [0, 2, 2, 100], [1, 2, 3, 120], [2, 0, 6, 130], [2, 1, 5, 130], [2, 2, 4, 130]]
```
```text
S R R
L L R
R R R
```
(S = fire station, R = residence, L = lake.) The only station is at `(0, 0)`. The lakes in row 1 force every route into row 2 around the right side, so `(2, 0)` is 6 moves away even though its Manhattan distance is 2. Distances 5 and 6 are beyond the table, so they pay its last entry, 130.
**Example 2**
```text
Input: grid = [[-1, -1, 0], [0, -2, -1], [-1, -1, -1]], charges = [50, 70]
Output: [[0, 0, 1, 50], [0, 1, 1, 50], [1, 2, 1, 50], [2, 0, 1, 50], [2, 1, 2, 70], [2, 2, 2, 70]]
```
There are stations at `(0, 2)` and `(1, 0)`, and each residence uses the nearer one. For example, `(2, 1)` is 2 moves from `(1, 0)` through `(2, 0)` but 3 moves from `(0, 2)`.
**Example 3**
```text
Input: grid = [[-1, -2, 0, -1]], charges = [5, 9]
Output: [[0, 0, -1, -1], [0, 3, 1, 5]]
```
The lake at `(0, 1)` cuts `(0, 0)` off from the only station, while `(0, 3)` is one move away.
Overview: A grid shortest-path coding question: a map holds fire stations, residences and impassable lakes, and for every residence you return the length of the shortest four-directional route from the nearest station plus a charge looked up in a capped distance table. It tests graph search on grids, unreachable cells and exact output ordering.
Read the full LinkedIn Software Engineer interview experience this question came from
A city map is a rectangular grid in which every cell holds `0` for a fire station, `-1` for a residence, or `-2` for a lake. A fire truck moves one cell at a time up, down, left or right, staying inside the grid. It may drive through fire stations and residences but never through a lake.
For every residence, find its distance from the nearest fire station, then the amount the city pays for a truck to reach it. The charge schedule is passed in as a table `charges` of whole-number charges.
## Rules
- The distance of a residence is the smallest number of moves on any route from any fire station to it, where each move goes to an edge-adjacent cell inside the grid and no route enters a lake. This equals the Manhattan distance when no lake is in the way. A reachable residence always has a distance of at least 1.
- A residence at distance `d` costs `charges[d - 1]` when `d <= len(charges)`. For any larger distance the charge is `charges[-1]` (the last entry), so the last entry acts as the cap.
- A residence that no fire station can reach (for example one cut off by lakes, or any residence when the grid has no fire station) has distance `-1` and charge `-1`.
- Return one `[row, col, distance, charge]` list for every residence, ordered by `row` ascending and then by `col` ascending. Rows and columns are 0-indexed. Fire stations and lakes get no entry. Return `[]` when the grid has no residence.
## Constraints
- `rows >= 1`, `cols >= 1` and `rows * cols <= 10^5`; every row has the same length.
- Every cell is `0`, `-1` or `-2`. The grid may contain any number of fire stations, including none.
- `1 <= len(charges) <= 10^5`
- `0 <= charges[i] <= 10^9`
- Every distance is below `10^5` and every charge is at most `10^9`, so no value exceeds `2^31 - 1`: a 32-bit `int` is enough in Java and C++.
## Example 1
```text
Input: grid = [[0, -1, -1], [-2, -2, -1], [-1, -1, -1]], charges = [80, 100, 120, 130]
Output: [[0, 1, 1, 80], [0, 2, 2, 100], [1, 2, 3, 120], [2, 0, 6, 130], [2, 1, 5, 130], [2, 2, 4, 130]]
```
The only station is at `(0, 0)`. The lakes in row 1 force every route around the right side and back along row 2, so `(2, 0)` is 6 moves away even though its Manhattan distance is 2. Distances 5 and 6 are beyond the table, so they pay its last entry, 130.
## Example 2
```text
Input: grid = [[-1, -2, 0, -1]], charges = [5, 9]
Output: [[0, 0, -1, -1], [0, 3, 1, 5]]
```
The lake at `(0, 1)` cuts `(0, 0)` off from the only station, so it reports `-1, -1`, while `(0, 3)` is one move away and pays `charges[0] = 5`.
Constraints
- rows >= 1, cols >= 1 and rows * cols <= 10^5; every row has the same length.
- Every cell is 0 (fire station), -1 (residence) or -2 (lake). The grid may contain any number of fire stations, including none.
- 1 <= len(charges) <= 10^5
- 0 <= charges[i] <= 10^9
- Every distance is below 10^5 and every charge is at most 10^9, so no value exceeds 2^31 - 1 (32-bit int in Java and C++).
Examples
Input: ([[0, -1, -1], [-2, -2, -1], [-1, -1, -1]], [80, 100, 120, 130])
Expected Output: [[0, 1, 1, 80], [0, 2, 2, 100], [1, 2, 3, 120], [2, 0, 6, 130], [2, 1, 5, 130], [2, 2, 4, 130]]
Explanation: Source example 1: lakes in row 1 force a detour, so (2, 0) is 6 moves away (Manhattan 2); distance 4 = len(charges) uses charges[3], distances 5 and 6 pay the cap 130.
Input: ([[-1, -1, 0], [0, -2, -1], [-1, -1, -1]], [50, 70])
Expected Output: [[0, 0, 1, 50], [0, 1, 1, 50], [1, 2, 1, 50], [2, 0, 1, 50], [2, 1, 2, 70], [2, 2, 2, 70]]
Explanation: Source example 2: two stations, each residence uses the nearer one; (2, 1) is 2 moves away (no diagonal moves), so it pays charges[1] = 70.
Hints
- A truck may pass through residences and other fire stations but never a lake, so when lakes sit in the way the true distance can be much larger than the Manhattan distance.
- Each residence only needs its distance to whichever fire station is nearest, not to any particular station.
- Once a distance d is known the charge is a direct table lookup: entry d - 1 while d <= len(charges), otherwise the last entry; a residence no station can reach reports -1 for both.