Bloomberg Interview Question: Desert Ride with Rocks

Problem

You have a grid representing a desert:

• . sand (walkable)
• c car start
• o oasis target
• r rock (blocked)

The car can move up/down/left/right. Each move costs 1 unit of gas.

Given gas, determine if the car can reach the oasis before gas runs out.

Approach

This is a shortest-path / reachability problem on a grid with obstacles.

Use BFS to find the minimum number of steps from c to o. Return min_steps <= gas.

Python

from collections import deque


def can_reach(desert: list[list[str]], gas: int) -> bool:
    R, C = len(desert), len(desert[0])

    start = end = None
    for r in range(R):
        for c in range(C):
            if desert[r][c] == 'c':
                start = (r, c)
            elif desert[r][c] == 'o':
                end = (r, c)

    if not start or not end:
        return False

    q = deque([(start[0], start[1], 0)])
    seen = {start}

    while q:
        r, c, d = q.popleft()
        if (r, c) == end:
            return d <= gas
        if d == gas:
            continue

        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen:
                if desert[nr][nc] != 'r':
                    seen.add((nr, nc))
                    q.append((nr, nc, d + 1))

    return False

Complexity

• Time: O(R*C)
• Space: O(R*C)

Need interview help? Contact OA VO Service

• 📧 Email: [email protected]
• 📱 Phone: +86 17863968105

Need real interview questions? Contact WeChat: Coding0201 to get the questions.