Find Fastest Commute Mode
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a 2D city grid containing:
- `S`: starting location
- `D`: destination
- `X`: blocked cell that cannot be entered
- `1`, `2`, `3`, `4`: cells usable by Walk, Bike, Car, and Train, respectively
Choose exactly one transportation mode for the entire trip; switching modes is not allowed. Starting from `S`, you may move only up, down, left, or right.
For a chosen mode:
- you may travel through cells labeled with that mode
- `S` and `D` are considered enterable for any mode
- moving across one block takes `time[i]` minutes and costs `cost[i]` dollars, where `i` corresponds to the chosen mode
Return the name of the transportation mode that can reach `D` from `S` with the minimum total travel time. If multiple modes have the same total travel time, return the one with the lower total cost.
You may assume at least one mode can reach the destination.
Quick Answer: This question evaluates graph traversal and shortest-path reasoning on a constrained 2D grid, including modeling movement rules per transportation mode, reachability analysis, and multi-criteria optimization (minimizing total travel time with cost as a tie-breaker).