Rolling Ball Maze Reachability

Quick Overview

Solve a rolling-ball maze reachability problem where direction changes are allowed only at stopping cells.

Rolling Ball Maze Reachability

Company: Goldman Sachs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Rolling Ball Maze Reachability Implement `has_rolling_path(maze: list[list[int]], start: list[int], destination: list[int]) -> bool`. The maze is a rectangular grid where `0` is open and `1` is a wall. A ball placed at `start` may choose one of the four cardinal directions, but once moving it continues until the next step would hit a wall or leave the grid. It may choose a new direction only after stopping. Return whether the ball can stop exactly at `destination`. ### Input Domain - `maze` has `m` rows and `n` columns, where `1 <= m, n <= 100`. - Every cell is `0` or `1`. - `start` and `destination` are two-element `[row, column]` lists naming open cells. - The input maze is not modified. ### Output Rules - Return `true` only if some sequence of rolls ends with the ball stopped at `destination`. - Passing through the destination without stopping does not count. ### Constraints - Explore at most the set of stopping cells; repeated visits to the same stop need not be expanded. - Output is a single Boolean, so tie semantics are not applicable. ### Examples #### Example 1 Input: `maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]` Output: `true` #### Example 2 Input: `maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]` Output: `false` ```hint Treat stops as states A useful search state is a cell where the ball has stopped, not every open cell it crosses while rolling. ```

Quick Answer: Solve a rolling-ball maze reachability problem where direction changes are allowed only at stopping cells.

|Home/Coding & Algorithms/Goldman Sachs
Goldman Sachs logo
Goldman Sachs
Aug 15, 2026
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

Rolling Ball Maze Reachability

Implement has_rolling_path(maze: list[list[int]], start: list[int], destination: list[int]) -> bool.

The maze is a rectangular grid where 0 is open and 1 is a wall. A ball placed at start may choose one of the four cardinal directions, but once moving it continues until the next step would hit a wall or leave the grid. It may choose a new direction only after stopping. Return whether the ball can stop exactly at destination.

Input Domain

  • maze has m rows and n columns, where 1 <= m, n <= 100 .
  • Every cell is 0 or 1 .
  • start and destination are two-element [row, column] lists naming open cells.
  • The input maze is not modified.

Output Rules

  • Return true only if some sequence of rolls ends with the ball stopped at destination .
  • Passing through the destination without stopping does not count.

Constraints

  • Explore at most the set of stopping cells; repeated visits to the same stop need not be expanded.
  • Output is a single Boolean, so tie semantics are not applicable.

Examples

Example 1

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]

Output: true

Example 2

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]

Output: false

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...