0

Fastest single-mode commute on a city grid

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Fastest single-mode commute on a city grid

Companies: Databricks

Difficulty: Medium

Problem statement

You are planning a commute across a city drawn as a 2D grid of characters:

  • 'S': your starting point (exactly one).
  • 'D': your destination (exactly one).
  • '1' to 'k': a block that only transport mode i can use.
  • 'X': a blocked cell.

You are also given two arrays of length k. time[i-1] and cost[i-1] are the minutes and dollars that mode i spends per block.

You pick one mode for the whole trip and cannot switch. Moves go up, down, left or right. A trip in mode i may step only on S, D and cells labelled i. Its total time is (blocks travelled) × time[i-1], and its total cost is (blocks travelled) × cost[i-1]. S and D do not count as blocks.

Implement optimal_commute(grid: list[str], time: list[int], cost: list[int]) -> int. It returns the mode number with the smallest total time. Break ties by smaller total cost, then by smaller mode number. Return -1 if no single mode can reach D.

Constraints: 1 <= rows, cols <= 500, 1 <= k <= 9, 1 <= time[i], cost[i] <= 1000.

Example 1

grid = ["S2D",
        "1X1",
        "111"]
time = [1, 9], cost = [9, 1]

Mode 1 goes around the wall through 5 blocks, for time 5. Mode 2 uses 1 block, for time 9. Answer: 1.

Example 2

Same grid, time = [9, 2], cost = [1, 1]. Mode 1 takes 45 and mode 2 takes 2. Answer: 2.

Example 3

grid = ["S12D"]. Reaching D needs both modes, and switching is not allowed. Answer: -1.

Approach

Each digit cell belongs to exactly one mode, and you may not change modes mid-trip. So a trip in mode m is a path from S to D that only steps on S, D and cells labelled m. Every block in mode m costs the same time[m] and cost[m]. That means the trip's time and cost are both blocks * time[m] and blocks * cost[m], where blocks is the number of mode cells on the path. Fewer blocks is better on both counts. The question for each mode becomes: what is the shortest unweighted path from S to D through that mode's cells?

Brute force. DFS over all simple paths for each mode and keep the shortest. This is exponential. Mention it only to dismiss it.

BFS per mode. For each mode m, run BFS from S. A neighbour is passable if it is D or a cell labelled m. X, other digits and out-of-bounds cells are walls. The first time BFS reaches D, the distance d counts the steps. The blocks travelled are the d - 1 cells strictly between S and D. Score the mode as (blocks * time[m], blocks * cost[m], m) and take the minimum tuple. That ranks by fastest first, then cheapest, then lowest mode number. Modes that never reach D are skipped. Return -1 if no mode works.

Why it is cheaper than it looks. A naive bound is O(k * R * C). But BFS for mode m only enters cells labelled m (plus D). Each cell has a single label, so across all modes every cell is dequeued at most once, apart from S and D. The total work is O(R * C + k). You can also skip modes with no cell adjacent to S before running BFS.

Invariants.

  • BFS dequeues cells in non-decreasing distance order, so the first arrival at D is the shortest path.
  • A cell is marked visited when it is enqueued, so it is never enqueued twice in one mode's search.
  • S and D are passable for every mode. D is a goal and is never expanded.

Code

from collections import deque
from typing import List, Optional, Sequence, Tuple

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def _find(grid: Sequence[str], ch: str) -> Tuple[int, int]:
    for r, row in enumerate(grid):
        c = row.find(ch)
        if c != -1:
            return r, c
    raise ValueError(f"grid has no {ch!r}")


def _blocks_for_mode(grid: Sequence[str], mode: str,
                     start: Tuple[int, int]) -> Optional[int]:
    """Fewest mode cells between S and D using only `mode`, or None."""
    rows, cols = len(grid), len(grid[0])
    seen = {start}
    queue = deque([(start[0], start[1], 0)])
    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols) or (nr, nc) in seen:
                continue
            cell = grid[nr][nc]
            if cell == "D":
                return dist  # dist mode cells were stepped on before D
            if cell == mode:
                seen.add((nr, nc))
                queue.append((nr, nc, dist + 1))
    return None


def optimal_commute(grid: Sequence[str], time: List[int],
                    cost: List[int]) -> int:
    """Return the 1-based mode with least total time, ties by cost then
    lower mode number. Return -1 if no single mode reaches D."""
    if len(time) != len(cost):
        raise ValueError("time and cost must have the same length")
    if not grid or not grid[0]:
        return -1
    start = _find(grid, "S")
    best: Optional[Tuple[int, int, int]] = None
    for m in range(1, len(time) + 1):
        blocks = _blocks_for_mode(grid, str(m), start)
        if blocks is None:
            continue
        key = (blocks * time[m - 1], blocks * cost[m - 1], m)
        if best is None or key < best:
            best = key
    return best[2] if best else -1


if __name__ == "__main__":
    city = [
        "3333D",
        "3XX1X",
        "S1112",
        "2XX2X",
        "2222X",
    ]
    # Modes 1 and 2 dead-end; mode 3 reaches D in 5 blocks.
    assert optimal_commute(city, [1, 1, 9], [1, 1, 9]) == 3
    assert optimal_commute(["S1D"], [5, 1], [1, 1]) == 1
    assert optimal_commute(["S2D", "1X1", "111"], [1, 9], [9, 1]) == 1
    assert optimal_commute(["S2D", "1X1", "111"], [9, 2], [1, 1]) == 2
    assert optimal_commute(["S11", "22D"], [2, 2], [3, 1]) == 2
    assert optimal_commute(["SD"], [3, 1], [1, 1]) == 1
    assert optimal_commute(["SX", "XD"], [1], [1]) == -1
    assert optimal_commute(["S12D"], [1, 1], [1, 1]) == -1
    print("ok")

Complexity

  • Time: O(R * C + k). Each mode's BFS only enters cells with that mode's label, so every cell is processed by at most one search (S is the start of all k searches).
  • Space: O(R * C) for the visited set and queue of the largest single mode.

Test cases

  • ["S1D"], time=[5,1], cost=[1,1] → 1. Mode 2 has no cells, so only mode 1 reaches D.
  • ["S2D","1X1","111"], time=[1,9], cost=[9,1] → 1. Mode 1 uses 5 blocks for time 5. Mode 2 uses 1 block for time 9.
  • Same grid, time=[9,2], cost=[1,1] → 2. Mode 2 takes 2, mode 1 takes 45.
  • ["S11","22D"], time=[2,2], cost=[3,1] → 2. Mode 1 dead-ends, so mode 2 wins outright.
  • ["SD"], time=[3,1], cost=[1,1] → 1. Zero blocks, so every mode ties at (0, 0) and the lowest mode number wins.
  • ["SX","XD"], time=[1], cost=[1] → -1. Fully blocked.
  • ["S12D"], time=[1,1], cost=[1,1] → -1. Reaching D needs a mode switch, which is not allowed.
  • Time tie: two modes with equal blocks * time → the lower blocks * cost wins.

Follow-ups

  • Return the route too. Store a parent pointer per cell in the winning mode's BFS and walk back from D. This adds O(R * C) space.
  • Mode switches allowed, with a transfer penalty. Run Dijkstra on states (r, c, mode). Moving within a mode costs time[mode]. Switching costs a fixed penalty. Use a lexicographic (time, cost) priority. That is O(R * C * log(R * C)), because each cell has one label and so only a constant number of states.
  • Per-cell weights (traffic, hills). Plain BFS is no longer correct. Use Dijkstra per mode, or 0-1 BFS if weights are 0/1.
  • Many queries on the same map (different S/D pairs or price lists). Precompute connected components per mode with union-find to answer "can mode m connect them?" in O(1). Cache BFS distances from popular sources.
  • Optimise a weighted blend or a budget ("fastest under $X"). Each mode's path is fixed-length, so filter modes by blocks * cost <= X and then take the fastest. With mode switching this becomes a constrained shortest path. Discuss Pareto labels per state.

Interviewer expectations

Mid-level (L4)

  • Parses the grid and finds S correctly. Writes a correct BFS with bounds and visited checks.
  • Sees that a fixed mode makes time and cost proportional to path length.
  • Handles the unreachable case and the tie-break, with a few hand-traced tests.

Senior (L5)

  • Explains why BFS (not DFS) gives the shortest path, and counts blocks off by none, including the S next to D case.
  • Encodes the ranking as a tuple comparison instead of nested ifs.
  • Notes the tighter O(R * C + k) bound, and moves cleanly to Dijkstra when weights or mode switches are added.

Staff (L6+)

  • Asks the ambiguous questions early: are S/D counted as blocks, may modes switch, what to return on a tie or no path.
  • Designs the switching follow-up as a state-space graph and reasons about its size.
  • Discusses reuse across queries (component precompute, caching) and multi-objective trade-offs (Pareto fronts) without over-building the base answer.

Sign in to comment, vote or remix.