Katkat
Back

Explore an Unknown Grid and Return a Robot Path

LinkedInDevOps Engineer · Onsite
MediumDevOps EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests graph traversal, state-space representation, and pathfinding in an environment where the map must be discovered dynamically.

Robot Exploration and Pathfinding

You are tasked with designing an algorithm for a robot to navigate a finite 2D grid of size M x N. The robot starts at (0, 0) and needs to reach a target coordinate (target_r, target_c). The grid is initially unknown; some cells are blocked, and some are clear.

The robot has the following capabilities:

  1. sense(): Returns the status (blocked or clear) of the four adjacent cells (Up, Down, Left, Right).
  2. move(direction): Attempts to move one cell in the specified direction. Returns True if successful, or False if blocked.
  3. get_position(): Returns current (r, c) coordinates.

Since moving the robot physically is expensive, your algorithm must minimize the total number of moves. If the target is unreachable, the robot must return to the start (0, 0) and report failure.

Task

Implement a function find_path(target, grid_dims) that returns the shortest path as a sequence of moves (e.g., ['U', 'R', 'R', 'D']) to the target. You must maintain an internal representation of the grid as you explore.

Constraints

  • 1 <= M, N <= 100
  • The robot can only move to adjacent cells.
  • move() operations incur a cost, while sense() operations are free.

Example

  • Input: target = (2, 2), grid_dims = (3, 3)
  • Robot calls sense(), builds a map, and performs BFS on the known graph to find the shortest path to the target.
  • Output: ['R', 'R', 'D', 'D']

Edge Cases

  • Target is blocked.
  • Target is unreachable due to surrounding obstacles.
  • The grid is fully open (no obstacles).

Hints

Hint 1

Use a data structure like a dictionary or 2D array to maintain a 'known' grid, initializing all cells as 'unknown'.

Hint 2

Treat this as a two-phase process: use an exploration strategy (like Depth-First Search) to map the grid, and then use A* or Breadth-First Search on your internal map to calculate the optimal path.

Hint 3

Since moving the robot is costly, consider using a 'Frontier' set to keep track of reachable, unexplored cells during the exploration phase.

Follow-up questions

  • How would your approach change if the robot had a limited battery life and needed to return to a charging station periodically?
  • What modifications are needed if the grid is dynamic (i.e., obstacles move or appear over time)?
  • How do you handle the trade-off between the time taken to explore the entire map versus moving directly toward the target?