Databricks Technical Phone Screen: Optimal Commute Problem in SDE Interview

You are comm

You are commuting across a simplified map of San Francisco, represented as a 2D grid. Each cell on the grid is one of the following: 'S' Your home location (starting point). 'D' Your office location (destination). A digit from '1' to k A street segment reserved for exactly one transportation mode. 'X' An impassable roadblock. You are also given three arrays with length k modes The name of each available transportation mode. times The time (in minutes) required to traverse a single block using each mode. costs The cost (in dollars) to traverse a single block using each mode. Movement is allowed up, down, left, and right. You may only travel along contiguous cells of the same transportation... mode (i.e., same digit). You cannot move between cells of different modes, nor can you cross roadblocks. For each mode i, the time and cost to traverse a single block are given by times[i] and costs[i], respectively. The total travel time and cost are calculated as the sum of the time and cost for each cell visited along the path from 'S' to 'D'.

Return the name of the transportation mode that yields the minimum total time from 'S' to 'D'. If multiple modes result in the same minimum time,

return the one with the lowest total cost.

Return an empty string if no valid route exists. I used a regular BFS. The follow-up question was how to reduce the time complexity to RC instead of KRC. I received some hints, and later, two hours later, I explained it to HR info call. Please give me more points!