0

Two cars to their destinations without collisions

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Two cars to their destinations without collisions

Companies: Google

Difficulty: Medium

Problem statement

A parking robot controls two self-driving cars on a rectangular map. The map is a list of equal-length strings. Each character is one cell:

  • . is road.
  • # is a wall. Cars cannot enter it.
  • a and b are the starting cells of car a and car b.
  • A and B are the destinations of car a and car b.

Each symbol a, b, A and B appears exactly once. Cells marked with these letters are road, so either car may drive over them.

Time moves in steps. On every step, both cars act at the same time. Each car either stays where it is or moves one cell up, down, left or right, inside the map and not into a wall. A step is not allowed if:

  • both cars end the step in the same cell, or
  • the cars swap cells, because they would pass through each other.

A car may move into the cell that the other car leaves during the same step.

Implement min_steps(grid: list[str]) -> int. It returns the fewest steps after which car a is on A and car b is on B at the same time. Return -1 if this is impossible.

Constraints: 1 <= rows, cols <= 50.

Example 1

grid = ["abAB"]

Output: 2. Both cars drive right together. On each step, a enters the cell that b has just left.

Example 2

grid = ["BabA",
        ".#.."]

Output: 4. In the top row alone the cars would have to pass each other, which is not allowed. Car b steps down into the lower row while a drives right. Then a reaches A, and b drives back up and left to B. With only the row "BabA", the answer is -1.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Clarify first. Both cars move at the same time. On each step, each car either stays or moves one cell up, down, left or right onto a cell that is not a wall. The letters a, b, A and B are road cells too, so either car may drive over the other car's start or destination. Two rules prevent crashes:

  • The cars may never be in the same cell after a step.
  • The cars may not swap cells in one step, because they would pass through each other on the way.

One car may move into the cell that the other car leaves in the same step ("follow the leader"). Return the smallest number of steps after which a is on A and b is on B at the same time, or -1 if that never happens. Confirm these rules with the interviewer. The swap rule and the follow-the-leader rule are the two that candidates most often get wrong.

Why two separate BFS runs fail. Running BFS for each car alone and taking max(dist_a, dist_b) gives a lower bound, not the answer. In a one-lane corridor B a b A, each car alone needs 2 steps, but the cars must pass each other, which is impossible. With a side pocket, one car must wait or detour, so the true answer is larger than either single-car distance.

Optimal method: BFS over the joint state. The state is the pair (position of a, position of b). One BFS edge is one simultaneous step: 5 options for a times 5 options for b, minus the pairs that collide or swap. Every edge costs 1, so plain BFS finds the minimum number of steps. With K open cells there are at most K^2 states, and each state has at most 25 successors.

Invariants.

  • Every state in the queue is reachable with the cars in different cells. The start is valid, and each edge is checked before it is added.
  • BFS pops states in nondecreasing step order, so the first time it generates the goal pair, that step count is the minimum.
  • "Stay" is one of the moves. This lets a car that has already arrived wait on its destination while the other car finishes. It also lets a car wait to let the other pass.

Early exit. Check for the goal when a state is generated, not when it is popped. This saves one BFS layer, which can be large in an open grid.

Code

from collections import deque

Cell = tuple[int, int]
State = tuple[Cell, Cell]
MOVES: tuple[Cell, ...] = ((0, 0), (1, 0), (-1, 0), (0, 1), (0, -1))


def parse(grid: list[str]) -> dict[str, Cell]:
    cols = len(grid[0]) if grid else 0
    marks: dict[str, Cell] = {}
    for r, line in enumerate(grid):
        if len(line) != cols:
            raise ValueError("grid must be rectangular")
        for c, ch in enumerate(line):
            if ch in "abAB":
                if ch in marks:
                    raise ValueError(f"duplicate {ch!r}")
                marks[ch] = (r, c)
            elif ch not in ".#":
                raise ValueError(f"unknown symbol {ch!r}")
    if len(marks) != 4:
        raise ValueError("grid needs exactly one each of a, b, A, B")
    return marks


def min_steps(grid: list[str]) -> int:
    """Fewest simultaneous steps until a is on A and b is on B, or -1."""
    marks = parse(grid)
    rows, cols = len(grid), len(grid[0])

    # Options for one car from each open cell: stay, or one of 4 moves.
    options: dict[Cell, list[Cell]] = {}
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "#":
                continue
            options[(r, c)] = [
                (r + dr, c + dc)
                for dr, dc in MOVES
                if 0 <= r + dr < rows and 0 <= c + dc < cols
                and grid[r + dr][c + dc] != "#"
            ]

    start: State = (marks["a"], marks["b"])
    goal: State = (marks["A"], marks["B"])
    dist: dict[State, int] = {start: 0}
    queue: deque[State] = deque([start])
    while queue:
        pa, pb = queue.popleft()
        d = dist[(pa, pb)]
        for na in options[pa]:
            for nb in options[pb]:
                if na == nb:                    # same cell at the same time
                    continue
                if na == pb and nb == pa:       # passing through each other
                    continue
                state = (na, nb)
                if state in dist:
                    continue
                if state == goal:
                    return d + 1
                dist[state] = d + 1
                queue.append(state)
    return -1

Complexity

Let K be the number of open cells (at most N * M).

  • Parsing and building the move lists: O(N * M) time, O(K) space.
  • BFS: at most K^2 states, each with at most 25 successor pairs, so O(25 * K^2) = O(K^2) time and O(K^2) space for dist and the queue.
  • For a 50 x 50 grid that is about 6.25 million states. That is acceptable in C++ and slow in Python. See the follow-ups for A* and for pruning.

Test cases

  • ["aA", "bB"] -> 1. Both cars move right in the same step.
  • ["a..A", "b..B"] -> 3. Two independent lanes, so the answer is the larger single-car distance.
  • ["abAB"] -> 2. Both cars move right together. Each step, a enters the cell b just left. This is allowed.
  • ["BabA"] -> -1. A one-lane corridor where the cars must pass each other.
  • ["BabA", ".#.."] -> 4. b steps down into the pocket, a drives past to A, then b comes back up and drives left.
  • ["bAaB"] -> -1. a reaches A in one step, but b must then pass through the cell where a is parked.
  • ["a.A", "...", "B.b"] -> 2. Each car needs 2 steps, and their paths never conflict.
  • ["a#A", "b#B"] -> -1. A wall cuts both cars off from their destinations.
  • ["a.A"] -> ValueError. The grid is missing b and B.

Follow-ups

  1. Return the paths, not only the count. Store a parent pointer for each state in dist (a dict from state to previous state). When the goal is found, walk back to the start and split the pairs into two sequences of cells. Memory stays O(K^2).
  2. Make it faster on large open grids. Use A* with the heuristic max(da[pa], db[pb]), where da and db come from a single-car BFS backward from A and from B. Each car needs at least its own shortest distance, so the heuristic is admissible and consistent. You can also prune early: if either single-car distance is infinite, return -1 before the joint search. Bidirectional BFS also works, because every move can be reversed (the reverse of a legal simultaneous step is legal).
  3. The cars move one at a time instead of together. Each edge then moves exactly one car to an adjacent free cell. Swaps become impossible by construction, and the only rule left is "not onto the other car". If the question asks for total moves, this is still BFS with at most 8 successors per state.
  4. Different costs. If staying is free, or some cells (traffic, mud) cost more, the edges no longer have equal cost. Switch to Dijkstra over the same joint state. If you minimize the sum of each car's arrival time instead of the makespan, add a flag per car that says it has finished, so it stops paying for waiting.
  5. More than two cars. The joint state grows as K^k and becomes impossible to search for large k. Discuss practical multi-agent path finding: prioritized planning (plan cars one at a time and reserve cells by time in a space-time table), or Conflict-Based Search, which plans each car alone and branches only on detected conflicts. Prioritized planning is fast but can fail to find a solution that exists. CBS is optimal but exponential in the worst case.

Interviewer expectations

Mid-level (L4)

  • Asks how the cars move and what counts as a collision, including swaps.
  • Sees that two independent BFS runs are not enough, and moves to BFS over the pair of positions.
  • Writes a correct BFS with a visited set, includes the stay move, and handles -1.

Senior (L5)

  • States the size of the state space (K^2) and the branching factor (25) without help, and explains why the first time BFS reaches the goal gives the minimum.
  • Handles the edge cases cleanly: follow-the-leader moves, a car parked on its destination that blocks the other car, and unreachable destinations.
  • Adds path reconstruction and the single-car lower bound for pruning when asked.

Staff (L6+)

  • Proposes A* with an admissible max heuristic and explains why it is consistent.
  • Explains how the model changes with other rules: moves one at a time, different costs, or makespan versus sum of arrival times.
  • Discusses scaling to many cars with reservation tables and Conflict-Based Search, including their limits on completeness and optimality.

Sign in to comment, vote or remix.