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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Waymo.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Waymo during technical interviews.

Generate Instructions for a Blind Maze Robot

Company: Waymo

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

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.

Quick Answer: 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 rectangular maze as a list of strings. Each cell is one of '#', '.', or 'E', where '#' is a wall, '.' is an empty cell, and 'E' is the unique exit. A robot starts on an unknown non-wall cell, possibly already on 'E'. The robot cannot see the maze and cannot observe its current position. You must generate one fixed instruction string in advance. Each instruction is one of 'U', 'D', 'L', or 'R'. When the robot executes an instruction, it tries to move one cell in that direction. If that would go outside the grid or into a wall, it stays where it is. Return an instruction string such that, no matter which non-wall cell the robot starts from, after executing the full string it is guaranteed to end on 'E'. You may assume that at least one valid instruction string exists. The string does not need to be shortest, but any correct string is acceptable.

Constraints

1 <= m, n <= 5
Let k be the number of non-wall cells. k <= 15
Exactly one cell is 'E'
At least one valid instruction string exists

Examples

Input: (["E"],)

Expected Output: ""

Explanation: The robot always starts on the exit, so no moves are needed.

Input: (["..E"],)

Expected Output: "RR"

Explanation: Two right moves push every possible start to the exit at the far right.

Input: (["E.", ".."],)

Expected Output: "UL"

Explanation: U guarantees the top row, then L guarantees the left column, which is the exit.

Input: (["E#", ".."],)

Expected Output: "LU"

Explanation: L merges all possible positions into the left column, and U moves the remaining non-exit cell onto E.

Input: (["...", "...", "..E"],)

Expected Output: "DDRR"

Explanation: Two down moves force the bottom row, then two right moves force the rightmost column and the exit.

Input: (["...", ".E.", "..."],)

Expected Output: "UUDLLR"

Explanation: UU sends every start to the top row, D brings all possibilities to the middle row, LL collapses them to the middle-left cell, and R reaches the center exit.

Hints

After reading some prefix of instructions, the important information is the set of cells where the robot could still be.
Treat each possible set of robot positions as a state. One move transforms that whole set into another set deterministically, so you can run BFS on subsets.

Quick Overview

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.