Meta Machine Learning Engineer Interview Experience — A Robot Room Cleaner API Variant

Meta recruiters often say they won't ask hard questions, but there are still interviewers who ask hard problems or hard variants.

Robot Room Cleaner API variant. Recording the core approach and the easy-to-miss details here for anyone who needs it.

Problem summary

• The map is unknown, boundaries are unknown
• You can only interact with the environment through the robot API:
  • move()
  • turnLeft() / turnRight()
  • isTarget() (or an equivalent interface)

Different from the original problem:

• You don't need to traverse or clean the entire area
• You just need to find the target from the starting point and stop once you find it

Breaking down the problem

Under this API constraint, the core problems come down to two things:

• How to record which positions have already been visited (visited)
• How to backtrack to the previous position when exploration fails, while keeping the robot's state correct

Solution overview (no implementation details yet)

• Use DFS + backtracking
• Maintain your own relative coordinate system
• Use a visited set to avoid revisiting
• At the end of every DFS layer, guarantee:
  • the robot returns to the position it was at before entering this layer
  • the robot's orientation matches what it was before entering

Below are the key implementation details.

1. How to model visited

Since you can't get the map directly, you have to maintain coordinates yourself:

• Define the starting point as (0, 0)
• Use a direction array to represent relative movement, e.g.:
  • 0: up, 1: right, 2: down, 3: left
• After every successful move(), update (x, y) based on the current direction
• Use a visited = set() to store (x, y)

Things to watch out for:

• Only add a coordinate to visited after move() succeeds and you've entered the new position
• A direction where move() fails should not affect visited

2. The full definition of backtracking

Backtracking isn't just "go back to the previous position" — you need to restore both position and orientation at the same time.

Standard backtracking steps:

• Turn 180 degrees in place
• move() back to the parent node
• Turn 180 degrees again to restore the original orientation

Corresponding calls:

turnRight()
turnRight()
move()
turnRight()
turnRight()

3. The DFS state invariant

The key to DFS correctness is this invariant:

On entering dfs(x, y, dir):

• the robot is at (x, y)
• the robot is facing dir

On returning from that function:

• the robot is still at (x, y)
• the robot is still facing dir

Every DFS branch (success or failure) must satisfy this.

4. How to iterate over directions

• Try all 4 directions from the current position
• For each direction:
  • if the next coordinate hasn't been visited and move() succeeds: recurse into DFS
  • if it fails, backtrack
  • call turnRight() once to move to the next direction

This guarantees:

• the coordinate calculations stay consistent with the robot's actual orientation
• no reachable direction gets skipped

5. Common mistakes

• Only backtracking position without restoring orientation
• Marking visited before move()
• Robot state being inconsistent after DFS returns
• Continuing to search after finding the target

6. Complexity

• Time: O(N), where N is the number of reachable cells
• Space: O(N), for visited and the recursion stack

7. Common extensions

• If you need to return the path: maintain a path variable in DFS, return it directly on success
• If you need the shortest path: that needs a separate BFS discussion, but it's fairly complex to implement under this API