Find target using robot movement API

Quick Overview

This question evaluates a candidate's ability to design exploration and state-space search strategies for a robot operating in an unknown, partially blocked 2D grid using a constrained movement and sensing API, testing competency in traversal algorithms, state management, and handling limited observability.

Find target using robot movement API

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You control a robot in an unknown 2D grid. The grid layout and boundaries are unknown, and you cannot access the map directly. Some cells are blocked (walls), others are open. ## Robot API You can only interact with the environment through these methods: - `bool move()` - Moves the robot forward by 1 cell in the direction it is currently facing. - Returns `true` if the move succeeds; returns `false` if the cell in front is blocked (robot stays in place). - `void turnLeft()` / `void turnRight()` - Rotates the robot 90 degrees in place. - `bool isTarget()` - Returns `true` if the robot is currently standing on the target cell. The robot starts at an unknown start cell (treat it as the origin) facing an unknown but fixed initial direction. ## Task Implement a procedure that **finds the target** and **stops as soon as the robot reaches it**. - You must not rely on any external map/grid representation. - You must ensure the robot can correctly explore without getting stuck in loops. - If the target is reachable from the start, your algorithm should eventually reach it. ## Output / Interface Describe or implement a function such as: - `bool findTarget(Robot& robot)` that returns `true` if it reaches the target (and stops searching immediately), otherwise `false` if the target is not reachable after exploring all reachable cells.

Quick Answer: This question evaluates a candidate's ability to design exploration and state-space search strategies for a robot operating in an unknown, partially blocked 2D grid using a constrained movement and sensing API, testing competency in traversal algorithms, state management, and handling limited observability.

|Home/Coding & Algorithms/Meta
Meta logo
Meta
Oct 30, 2025, 12:00 AM
mediumMachine Learning EngineerOnsiteCoding & Algorithms
13
0

You control a robot in an unknown 2D grid. The grid layout and boundaries are unknown, and you cannot access the map directly. Some cells are blocked (walls), others are open.

Robot API

You can only interact with the environment through these methods:

  • bool move()
    • Moves the robot forward by 1 cell in the direction it is currently facing.
    • Returns true if the move succeeds; returns false if the cell in front is blocked (robot stays in place).
  • void turnLeft() / void turnRight()
    • Rotates the robot 90 degrees in place.
  • bool isTarget()
    • Returns true if the robot is currently standing on the target cell.

The robot starts at an unknown start cell (treat it as the origin) facing an unknown but fixed initial direction.

Task

Implement a procedure that finds the target and stops as soon as the robot reaches it.

  • You must not rely on any external map/grid representation.
  • You must ensure the robot can correctly explore without getting stuck in loops.
  • If the target is reachable from the start, your algorithm should eventually reach it.

Output / Interface

Describe or implement a function such as:

  • bool findTarget(Robot& robot)

that returns true if it reaches the target (and stops searching immediately), otherwise false if the target is not reachable after exploring all reachable cells.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...