Minimize Commute
Databricks● MediumFULLTIMEOAPHONE SCREENProblem statement
You are given a city grid containing one S, one D, blocked cells X, and transport cells 1 through 4 for Walk, Bike, Car, and Train.
Choose exactly one transport mode. You may move one cell at a time in the four cardinal directions and may enter only S, D, and cells labeled with the chosen mode. Blocked cells and cells for other modes are impassable.
The arrays time and cost give per-block values in the order Walk, Bike, Car, Train. For every reachable mode, use its shortest path from S to D. Return the mode with minimum total time; break a total-time tie by minimum total cost.
Discussion follow-up: transfers
How would the route-finding approach change if the commuter could transfer between transportation modes during the trip? Discuss how to represent the travel state and compare routes. The transfer locations, transfer penalties, and return format for this extension are unspecified; clarify them before implementing it. The judged minimizeCommute function above continues to choose exactly one mode.
Function
minimizeCommute(grid: String[][], time: int[], cost: int[]) → StringExamples
Example 1
grid = [["3","3","S","2","X","X"],["3","1","1","2","X","2"],["3","1","1","2","2","2"],["3","1","1","1","D","3"],["3","3","3","3","3","4"],["4","4","4","4","4","4"]]time = [3, 2, 1, 1]cost = [0, 1, 3, 2]return = "Bike"Bike reaches D in five blocks for total time 5 × 2 = 10. Walk needs five blocks for time 15, Car needs eleven blocks for time 11, and Train is unreachable, so Bike is fastest.
Constraints
1 ≤ rows, cols ≤ 100- Grid contains exactly one
'S'and one'D' time.length == cost.length == 4- At least one mode can reach
'D'