Choose fastest transportation mode on city grid
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You live in a city modeled as a 2D grid. Each cell is either:
- A transportation mode `1..4` where:
- `1 = Walk`, `2 = Bike`, `3 = Car`, `4 = Train`
- `S` = source (start)
- `D` = destination
- `X` = roadblock (cannot enter)
You may move only **up, down, left, right** (no diagonals).
A trip must use **exactly one transportation mode** for the whole route:
- For a chosen mode `m`, you may step from a cell to a neighboring cell only if the neighbor is either `S`, `D`, or has value `m`.
- You cannot step onto `X`.
For each mode `m`, if there exists a valid path from `S` to `D` using mode `m`, its total travel time and cost are:
- `time = (#blocks traversed) * timePerBlock[m]`
- `cost = (#blocks traversed) * costPerBlock[m]`
Where `#blocks traversed` is the number of moves (edges) along the chosen path.
Return the **mode number** (1–4) that yields the **minimum total time**. If multiple modes tie on time, return the one with the **minimum total cost**. If still tied, any tied mode is acceptable.
### Example
Grid (rows):
```
|3|3|S|2|X|
|3|1|1|2|X|
|3|1|1|2|2|
|3|1|1|1|D|
|3|3|3|3|4|
|4|4|4|4|4|
```
`costPerBlock = [0, 1, 3, 2]` (for modes 1..4 respectively)
`timePerBlock = [3, 2, 1, 1]`
### Input/Output
- **Input:** `grid`, `costPerBlock[4]`, `timePerBlock[4]`
- **Output:** an integer in `{1,2,3,4}` indicating the selected mode.
### Notes
- You may assume `S` and `D` each appear exactly once.
- If a mode cannot reach `D` from `S`, ignore it.
- (Optional if needed) If no mode can reach `D`, return `-1`.
Quick Answer: This question evaluates a candidate's ability to model constrained grid movement and perform weighted shortest-path optimization, covering skills in graph traversal, pathfinding, and multi-criteria comparison of time and cost.
You are given a city represented as a 2D grid. Each cell contains one of the following values: '1', '2', '3', '4', 'S', 'D', or 'X'. Here, 'S' is the start, 'D' is the destination, 'X' is a roadblock, and '1'..'4' are transportation modes. You may move only up, down, left, or right. A trip must use exactly one transportation mode for the entire route. If you choose mode m, then from any cell you may move to a neighboring cell only if that neighbor is 'S', 'D', or has value equal to m. You may never enter 'X'. For each mode, if a valid path from 'S' to 'D' exists, its total time is (#moves) * timePerBlock[m] and its total cost is (#moves) * costPerBlock[m], where #moves is the number of edge moves in the path. Return the mode number (1 to 4) with the minimum total time. If multiple modes tie on time, return the one with the minimum total cost. If no mode can reach the destination, return -1.