Katkat
Back

Generate Instructions for a Blind Maze Robot

WaymoMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design algorithmic strategies for state-space synchronization, graph traversal, and reasoning under partial observability in grid environments.

You are given a known 2D maze grid with m rows and n columns. Each cell is one of:

  • #: wall
  • .: empty cell
  • E: the exit, which appears exactly once

A robot starts at an unknown non-wall cell, possibly already on E. The robot has no knowledge of the maze layout and cannot observe its position. It will execute one fixed instruction string that you generate in advance. Each instruction is one of U, D, L, or R.

Movement rules:

  • If the instruction would move the robot into a wall or outside the grid, the robot stays in its current cell.
  • Otherwise, the robot moves one cell in that direction.

Write a function that generates an instruction string such that, no matter which non-wall cell the robot starts from, after executing the entire string the robot is guaranteed to be on E.

You may assume that at least one valid instruction string exists. The instruction string does not need to be shortest.