Katkat
Back

Choose fastest transportation mode on city grid

DatabricksSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model a grid-based transportation network as a graph and apply Dijkstra's algorithm to find the optimal path under multiple constraints.

Problem Description

You are given a city represented as an N x M grid. Each cell (r, c) contains an integer representing the maximum speed allowed (in km/h). You start at (0, 0) and must reach (N-1, M-1).

You have two transportation modes:

  1. Walking: Moves at a constant speed of 5 km/h across any cell.
  2. Biking: Moves at the speed defined by the current cell grid[r][c], but only if grid[r][c] >= 10. Otherwise, you must walk.

Moving between adjacent cells (up, down, left, right) takes time calculated as distance / speed. Assume each cell side is 1 km, so moving between adjacent cells takes 1 / speed hours. Find the minimum time required to travel from the top-left to the bottom-right corner.

Function Signature

def min_travel_time(grid: List[List[int]]) -> float:

Examples

Example 1: Input: grid = [[20, 20], [20, 20]] Output: 0.1 Explanation: Moving from (0,0) to (0,1) takes 1/20 hr, and (0,1) to (1,1) takes 1/20 hr. Total = 0.05 + 0.05 = 0.1 hr.

Example 2: Input: grid = [[5, 5], [5, 20]] Output: 0.3 Explanation: You must walk (5 km/h) through the first two cells (1/5 + 1/5 = 0.4) and bike the last cell (1/20 = 0.05). Wait—the path (0,0)->(1,0)->(1,1) takes 1/5 + 1/20 = 0.25.

Constraints

  • 1 <= N, M <= 100
  • 1 <= grid[r][c] <= 50
  • Time limit: 2 seconds.

Hints

Hint 1

Model the grid as a graph where each cell is a node and edges exist between adjacent cells.

Hint 2

The weight of an edge between two cells is determined by the speed of the destination cell, using 5 km/h if biking is not allowed.

Hint 3

Since edge weights are non-negative, use Dijkstra's algorithm with a priority queue to find the shortest path.

Follow-up questions

  • How would the solution change if you could switch between walking and biking at any point, but switching modes incurs a fixed penalty of 0.05 hours?
  • If the grid contained 'obstacles' (cells with value 0) that you cannot enter, how would you modify your graph traversal?
  • What if you need to find the path that minimizes time, but among those, minimizes the total distance traveled?