Answer Repeated Shortest Increasing-Path Queries
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Given an integer grid, repeatedly find a shortest strictly increasing path from the top-left cell to a requested target value. Moves are allowed up, right, down, and left. Return the values along the path, or an empty path if the target is absent or unreachable.
Implement `increasing_paths(grid: int[][], targets: int[]) -> int[][]`, returning one value path per target in input order.
### Constraints & Assumptions
- The grid is rectangular, with 1 through 100 rows and columns, and at most 1,000 target queries.
- Values are distinct signed 32-bit integers. The source does not specify duplicates; uniqueness is an explicit practice assumption so each target identifies one cell.
- A move is legal only if the next cell's value is strictly greater than the current value.
- Path length is measured in number of edges. The starting cell has a zero-edge path containing its own value.
- Resolve equal-length paths using the first discovery in a FIFO BFS that visits neighbors in this order: up, right, down, left. This is a deterministic tie convention for the source's any-shortest-path output.
- Preprocess the fixed grid once. Do not run a full new traversal for every query; each answer should require only lookup and output-path reconstruction after preprocessing.
### Examples
```text
grid = [[1,2,3],[4,5,8],[7,9,6]]
targets = [5,6,1]
result = [[1,2,5],[],[1]]
```
```text
grid = [[4,3],[5,6]]
targets = [6,3,9]
result = [[4,5,6],[],[]]
```
Explain the preprocessing and per-query time and space costs. Compare storing a complete path at every reachable cell with storing one distance/predecessor per cell, including the cost of actually returning a long path. Discuss why a shortest-path traversal or equivalent dynamic program can reuse work across calls.
```hint Retain how each cell was first reached
Once shortest reachability from the fixed start is known, a query can follow saved predecessor links instead of exploring the grid again.
```
Overview: Preprocess shortest strictly increasing grid paths for repeated target queries, with deterministic BFS ties, predecessor reconstruction, and memory trade-offs.
Read the full Uber Software Engineer interview experience this question came from
Given an integer grid, repeatedly find a shortest strictly increasing path from the top-left cell to a requested target value. Moves are allowed up, right, down, and left. Return the values along the path, or an empty path if the target is absent or unreachable.
Implement `increasing_paths(grid: int[][], targets: int[]) -> int[][]`, returning one value path per target in input order.
### Constraints & Assumptions
- The grid is rectangular, with 1 through 100 rows and columns, and at most 1,000 target queries.
- Values are distinct signed 32-bit integers. The source does not specify duplicates; uniqueness is an explicit practice assumption so each target identifies one cell.
- A move is legal only if the next cell's value is strictly greater than the current value.
- Path length is measured in number of edges. The starting cell has a zero-edge path containing its own value.
- Resolve equal-length paths using the first discovery in a FIFO BFS that visits neighbors in this order: up, right, down, left. This is a deterministic tie convention for the source's any-shortest-path output.
- Preprocess the fixed grid once. Do not run a full new traversal for every query; each answer should require only lookup and output-path reconstruction after preprocessing.
### Examples
```text
grid = [[1,2,3],[4,5,8],[7,9,6]]
targets = [5,6,1]
result = [[1,2,5],[],[1]]
```
```text
grid = [[4,3],[5,6]]
targets = [6,3,9]
result = [[4,5,6],[],[]]
```
Explain the preprocessing and per-query time and space costs. Compare storing a complete path at every reachable cell with storing one distance/predecessor per cell, including the cost of actually returning a long path. Discuss why a shortest-path traversal or equivalent dynamic program can reuse work across calls.
```hint Retain how each cell was first reached
Once shortest reachability from the fixed start is known, a query can follow saved predecessor links instead of exploring the grid again.
```
Constraints
- Rectangular grid has 1 through 100 rows and columns with distinct signed 32-bit values; at most 1000 target queries.
- Start is the top-left cell. Orthogonal moves must strictly increase the value.
- Return a shortest value path measured in edges; FIFO first discovery with up/right/down/left neighbor order resolves ties.
- The start target returns its singleton value. Missing or unreachable targets return [].
- Preprocess the fixed grid once, then answer by lookup and predecessor reconstruction in query order.
Examples
Input: ([[1, 2, 3], [4, 5, 8], [7, 9, 6]], [5, 6, 1])
Expected Output: [[1, 2, 5], [], [1]]
Explanation: The prescribed FIFO tie order reaches five through the right neighbor first.
Input: ([[4, 3], [5, 6]], [6, 3, 9])
Expected Output: [[4, 5, 6], [], []]
Explanation: Existing lower targets and absent targets both return empty paths.