How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve grid path and robot navigation

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Part A — Shortest path in a grid with obstacles: Given an m×n grid of 0/1 cells (0 = open, 1 = obstacle), start at (0, 0) and end at (m−1,n− 1). You may move in four directions (up, down, left, right), each move costs 1. Return the length of the shortest path; return −1 if unreachable. Describe your algorithm, prove correctness, and analyze time/space complexity. Part B — Robot search in an unknown room (LeetCode-inspired, original prompt): You do not have the grid map. You control a robot in a finite 2D room with walls/obstacles. The robot starts at an arbitrary cell. Available APIs: - bool move(Direction d): attempts to move one cell in {up, down, left, right}; returns false if blocked and the robot stays put. - void turnLeft(), void turnRight() (optional; use if needed to manage orientation). - bool atTarget(): returns true if the current cell is the target. Design and implement an algorithm that explores the room, locates the target, and returns the minimal number of steps from the start to the target. Explain how you: ( 1) represent coordinates without a given grid, ( 2) avoid revisiting and handle backtracking, ( 3) ensure optimality of the returned step count, and ( 4) analyze complexity in terms of R, the number of reachable cells.

Quick Answer: This question evaluates proficiency in graph traversal and pathfinding, state representation for unknown environments, exploration and backtracking, and rigorous reasoning about correctness and time/space complexity.

Shortest Path in a Grid with Obstacles

Given an `m x n` grid of `0`/`1` cells where `0` is an open cell and `1` is an obstacle, you start at the top-left corner `(0, 0)` and want to reach the bottom-right corner `(m-1, n-1)`. From any cell you may move one step in four directions (up, down, left, right); each move costs `1`. Return the length of the shortest path measured as the number of cells visited along the way (so the start cell counts as `1`). Return `-1` if the destination is unreachable, or if either the start or the destination is itself an obstacle. This is a classic single-source shortest-path problem on an unweighted grid: because every edge has unit cost, a breadth-first search expands cells in non-decreasing distance order, so the first time BFS reaches the destination it has found a shortest path. Time complexity is O(m*n) since each cell is enqueued at most once, and space is O(m*n) for the visited matrix and the queue.

Constraints

1 <= m, n <= 1000
grid[i][j] is either 0 (open) or 1 (obstacle)
If grid[0][0] == 1 or grid[m-1][n-1] == 1, the answer is -1
Path length is counted as the number of cells visited (start cell counts as 1)

Examples

Input: ([[0,0,0],[1,1,0],[0,0,0]],)

Expected Output: 5

Explanation: Go right twice along the top row to (0,2), down to (1,2), down to (2,2), left to (2,1): 5 cells visited.

Input: ([[0,1],[1,0]],)

Expected Output: -1

Explanation: The only neighbors of the start are obstacles, so the destination is unreachable.

Input: ([[0]],)

Expected Output: 1

Explanation: Start and destination are the same single open cell; the path visits 1 cell.

Input: ([[1]],)

Expected Output: -1

Explanation: The start cell is itself an obstacle, so there is no valid path.

Input: ([[0,0,0],[0,0,0],[0,0,0]],)

Expected Output: 5

Explanation: Manhattan distance from (0,0) to (2,2) is 4 moves = 5 cells visited, with no obstacles to detour around.

Input: ([[0,0],[0,1]],)

Expected Output: -1

Explanation: The bottom-right destination cell is an obstacle, so it is unreachable.

Input: ([],)

Expected Output: -1

Explanation: An empty grid has no path; return -1.

Input: ([[0,1,0],[0,1,0],[0,0,0]],)

Expected Output: 5

Explanation: The middle column is blocked, so go down the left column to (2,0), then right to (2,2): 5 cells.

Hints

All moves cost the same, so BFS (not Dijkstra/DFS) gives the shortest path on the first arrival at the destination.
Mark a cell visited the moment you enqueue it (not when you pop it) to avoid enqueuing the same cell multiple times.
Handle the degenerate cases first: empty grid, a blocked start, or a blocked destination should all return -1. A 1x1 open grid returns 1.

Robot Search in an Unknown Room

You control a robot in a finite 2D room of open cells and walls, but you are NOT given the map. The robot starts at an arbitrary open cell and can only sense the room through these primitives: `move(direction)` attempts to step one cell up/down/left/right and returns `false` (staying put) if a wall blocks it; `atTarget()` returns `true` when the robot stands on the target cell. Design an algorithm that explores the room, locates the target, and returns the MINIMAL number of steps from the start to the target — or `-1` if the target is unreachable. For an executable, deterministic version, this challenge passes you a hidden `grid` (0 = open, 1 = wall) plus `start` and `target` coordinates. Your `solution(grid, start, target)` must use the grid ONLY to back the `move()`/`atTarget()` primitives (i.e., treat the layout as unknown to the robot) — explore in robot-relative coordinates with DFS + backtracking to discover the reachable free cells, then run BFS over those discovered cells to compute the minimal step count. Key ideas: (1) Represent coordinates relative to the start, treating it as `(0,0)` and tracking `(dr, dc)` offsets as you move. (2) Avoid revisiting by recording every discovered cell in a set and backtracking with the opposite move after each DFS branch so the robot's physical position stays consistent. (3) Optimality comes from running BFS over the discovered free-cell graph (DFS only maps the room; it does not measure shortest distance). (4) Complexity is O(R) cells discovered with O(R) BFS, where R is the number of reachable cells.

Constraints

The robot does not know the grid; it may only use move()/atTarget() semantics during exploration.
Coordinates are tracked relative to the start cell, which is treated as (0, 0).
Steps are counted as moves between adjacent cells (start == target yields 0).
Return -1 if the target is unreachable, or if start/target is a wall or out of bounds.
1 <= m, n; grid[i][j] is 0 (open) or 1 (wall)

Examples

Input: ([[0,0,0],[1,1,0],[0,0,0]], [0,0], [2,0])

Expected Output: 6

Explanation: The middle row is mostly walls; the only route from (0,0) to (2,0) goes right across the top, down the right column, and left across the bottom: 6 steps.

Input: ([[0,0,0],[0,0,0],[0,0,0]], [0,0], [2,2])

Expected Output: 4

Explanation: An open 3x3 room: the Manhattan distance from (0,0) to (2,2) is 4 steps.

Input: ([[0,1],[1,0]], [0,0], [1,1])

Expected Output: -1

Explanation: The target (1,1) is isolated by walls; the robot can never reach it, so return -1.

Input: ([[0]], [0,0], [0,0])

Expected Output: 0

Explanation: Start and target are the same cell; the robot is already at the target with 0 steps.

Input: ([[0,0,0,0]], [0,0], [0,3])

Expected Output: 3

Explanation: A single open corridor of length 4; moving right three times reaches the target.

Input: ([[0,1,0],[0,1,0],[0,0,0]], [0,0], [0,2])

Expected Output: 6

Explanation: The middle column is walled off, so the robot must travel down the left column, across the bottom, and up the right column: 6 steps.

Input: ([[0,0],[0,0]], [0,0], [1,1])

Expected Output: 2

Explanation: Open 2x2 room; the diagonal corner is 2 steps away (down then right, or right then down).

Input: ([[0,0,0],[1,1,0],[0,0,0]], [0,0], [2,2])

Expected Output: 4

Explanation: Despite the walled middle row, (2,2) is reached via the right column: right, right, down, down = 4 steps.

Hints

DFS alone cannot give the minimal step count — it only discovers which cells are reachable. Use DFS (or any flood fill) to MAP the room, then BFS over the discovered cells to MEASURE the shortest distance.
Track position with relative offsets: treat the start as (0,0) and add the direction delta on each successful move. This lets you build a coordinate system without ever knowing the absolute grid.
After exploring a branch, issue the opposite move to physically backtrack the robot to its previous cell, so the relative coordinate you track always matches where the robot actually stands.

Solve grid path and robot navigation

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Shortest Path in a Grid with Obstacles

Constraints

1 <= m, n <= 1000
grid[i][j] is either 0 (open) or 1 (obstacle)
If grid[0][0] == 1 or grid[m-1][n-1] == 1, the answer is -1
Path length is counted as the number of cells visited (start cell counts as 1)

Examples

Input: ([[0,0,0],[1,1,0],[0,0,0]],)

Expected Output: 5

Explanation: Go right twice along the top row to (0,2), down to (1,2), down to (2,2), left to (2,1): 5 cells visited.

Input: ([[0,1],[1,0]],)

Expected Output: -1

Explanation: The only neighbors of the start are obstacles, so the destination is unreachable.

Input: ([[0]],)

Expected Output: 1

Explanation: Start and destination are the same single open cell; the path visits 1 cell.

Input: ([[1]],)

Expected Output: -1

Explanation: The start cell is itself an obstacle, so there is no valid path.

Input: ([[0,0,0],[0,0,0],[0,0,0]],)

Expected Output: 5

Explanation: Manhattan distance from (0,0) to (2,2) is 4 moves = 5 cells visited, with no obstacles to detour around.

Input: ([[0,0],[0,1]],)

Expected Output: -1

Explanation: The bottom-right destination cell is an obstacle, so it is unreachable.

Input: ([],)

Expected Output: -1

Explanation: An empty grid has no path; return -1.

Input: ([[0,1,0],[0,1,0],[0,0,0]],)

Expected Output: 5

Explanation: The middle column is blocked, so go down the left column to (2,0), then right to (2,2): 5 cells.

Hints

All moves cost the same, so BFS (not Dijkstra/DFS) gives the shortest path on the first arrival at the destination.
Mark a cell visited the moment you enqueue it (not when you pop it) to avoid enqueuing the same cell multiple times.
Handle the degenerate cases first: empty grid, a blocked start, or a blocked destination should all return -1. A 1x1 open grid returns 1.

Robot Search in an Unknown Room

Constraints

The robot does not know the grid; it may only use move()/atTarget() semantics during exploration.
Coordinates are tracked relative to the start cell, which is treated as (0, 0).
Steps are counted as moves between adjacent cells (start == target yields 0).
Return -1 if the target is unreachable, or if start/target is a wall or out of bounds.
1 <= m, n; grid[i][j] is 0 (open) or 1 (wall)

Examples

Input: ([[0,0,0],[1,1,0],[0,0,0]], [0,0], [2,0])

Expected Output: 6

Explanation: The middle row is mostly walls; the only route from (0,0) to (2,0) goes right across the top, down the right column, and left across the bottom: 6 steps.

Input: ([[0,0,0],[0,0,0],[0,0,0]], [0,0], [2,2])

Expected Output: 4

Explanation: An open 3x3 room: the Manhattan distance from (0,0) to (2,2) is 4 steps.

Input: ([[0,1],[1,0]], [0,0], [1,1])

Expected Output: -1

Explanation: The target (1,1) is isolated by walls; the robot can never reach it, so return -1.

Input: ([[0]], [0,0], [0,0])

Expected Output: 0

Explanation: Start and target are the same cell; the robot is already at the target with 0 steps.

Input: ([[0,0,0,0]], [0,0], [0,3])

Expected Output: 3

Explanation: A single open corridor of length 4; moving right three times reaches the target.

Input: ([[0,1,0],[0,1,0],[0,0,0]], [0,0], [0,2])

Expected Output: 6

Explanation: The middle column is walled off, so the robot must travel down the left column, across the bottom, and up the right column: 6 steps.

Input: ([[0,0],[0,0]], [0,0], [1,1])

Expected Output: 2

Explanation: Open 2x2 room; the diagonal corner is 2 steps away (down then right, or right then down).

Input: ([[0,0,0],[1,1,0],[0,0,0]], [0,0], [2,2])

Expected Output: 4

Explanation: Despite the walled middle row, (2,2) is reached via the right column: right, right, down, down = 4 steps.

Hints

DFS alone cannot give the minimal step count — it only discovers which cells are reachable. Use DFS (or any flood fill) to MAP the room, then BFS over the discovered cells to MEASURE the shortest distance.
Track position with relative offsets: treat the start as (0,0) and add the direction delta on each successful move. This lets you build a coordinate system without ever knowing the absolute grid.
After exploring a branch, issue the opposite move to physically backtrack the robot to its previous cell, so the relative coordinate you track always matches where the robot actually stands.

Quick Overview

Quick Overview