Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Help Mouse Find the Cheese

Given a mouse in a grid, determine if the mouse can reach the cheese. The only way to manipulate the mouse is via two functions, move() and isCheese(). The move() function returns true and moves the mouse if the move is possible, and returns false otherwise. The isCheese() function returns true if the mouse is currently at the cheese and false otherwise. You only have one instantiation of the mouse class. You cannot access the graph outside of the methods provided. The graph may have walls and isn’t guaranteed to be any particular shape. Exactly one cheese exists, and it’s always possible to reach it.

Asked at:

Meta

DESCRIPTION

Input:

Grid with mouse at (0,0) and cheese at (2,2), no walls

Output:

true

Explanation: The mouse can reach the cheese by moving right twice and down twice (or any valid path)

Constraints:

The grid size is unknown and cannot be accessed directly
The mouse's starting position is unknown
The cheese's position is unknown
The grid may contain walls that block movement
Exactly one cheese exists in the grid
The cheese is always reachable from the starting position
Can only interact via move() and isCheese() methods

Understanding the Problem

Let's understand what we're being asked to do. We have a mouse placed somewhere in a grid (like a maze), and there's cheese located somewhere else in that grid. The grid may contain walls that block movement.

We can only interact with the mouse through two methods: move(direction) which attempts to move the mouse in a direction (returns true if successful, false if blocked by a wall or boundary), and isCheese() which tells us if the mouse is currently at the cheese location.

Important constraints: We cannot see the grid layout directly - we can only explore it by attempting moves. We don't know the mouse's starting position or the cheese's position. We can only move in four directions (up, down, left, right).

Key insight: Since we're told the cheese is always reachable, there must exist at least one valid path from the starting position to the cheese. We need to systematically explore the grid to find it.

Edge cases to consider: What if the mouse starts right at the cheese? What if the grid has dead ends? What if there are multiple paths to the cheese (we only need to find one)?

Building Intuition

Since we can't see the entire grid, we need to explore systematically. Each time we move to a new cell, we discover what's adjacent to it by attempting moves in all four directions.

The key challenge is: how do we avoid getting stuck in loops? If we visit a cell, move away, and then come back to it later, we might explore the same paths repeatedly forever.

We need a way to remember which cells we've already visited. Once we've explored all paths from a cell without finding cheese, there's no point returning to it.

By marking cells as visited, we ensure we explore each cell at most once, guaranteeing we'll eventually find the cheese (since we're told it's always reachable).

Imagine you're in a real maze with a piece of chalk. Every time you enter a new room, you mark it with chalk. When you hit a dead end, you backtrack to the last room that had unexplored exits.

You keep exploring new rooms (unmarked ones) until you find the cheese. The chalk marks prevent you from wasting time re-exploring rooms you've already checked. This is exactly how we'll navigate the grid - systematically exploring unvisited cells until we reach the goal.

Common Mistakes

Forgetting to track visited cells, leading to infinite loops when the algorithm revisits the same cells repeatedly

Not properly backtracking - failing to unmark cells as visited when backtracking can prevent finding valid paths

Attempting to access grid positions directly instead of using the provided move() and isCheese() methods

Not checking isCheese() at the starting position - the mouse might already be at the cheese

Incorrect direction handling - make sure to try all four directions (up, down, left, right) and handle the coordinate system correctly

Optimal Solution

Use depth-first search (DFS) to systematically explore the grid. Start from the mouse's current position and recursively try moving in all four directions. Keep track of visited cells to avoid revisiting them. For each unvisited cell, check if it contains cheese using isCheese(). If not, recursively explore all valid adjacent cells. If we find the cheese, return true. If all paths are exhausted without finding cheese, backtrack. Since the cheese is guaranteed to be reachable, this exploration will eventually find it.

Visualization

def find_cheese(mouse):
    """
    Use DFS to find cheese in a grid.
    Returns True when cheese is found.
    """
    # Track visited cells to avoid cycles
    visited = set()
    
    def dfs(position):
        # Check if current position has cheese
        if mouse.isCheese():
            return True
        
        # Mark current position as visited
        visited.add(position)
        
        # Try all four directions: up, down, left, right
        directions = ['up', 'down', 'left', 'right']
        
        for direction in directions:
            # Try to move in this direction
            if mouse.move(direction):
                # Get new position (conceptual - we track state)
                new_position = (position[0] + (1 if direction == 'down' else -1 if direction == 'up' else 0),
                               position[1] + (1 if direction == 'right' else -1 if direction == 'left' else 0))
                
                # Only explore if not visited
                if new_position not in visited:
                    # Recursively search from new position
                    if dfs(new_position):
                        return True
                    
                    # Backtrack: move back to previous position
                    opposite = {'up': 'down', 'down': 'up', 'left': 'right', 'right': 'left'}
                    mouse.move(opposite[direction])
        
        return False
    
    # Start DFS from initial position (0, 0)
    return dfs((0, 0))

Start DFS to find cheese in grid

0 / 44

Test Your Knowledge

Complexity Analysis

Time Complexity: O(rows × cols) In the worst case, we visit every cell in the grid exactly once before finding the cheese. Each cell is processed in constant time (checking if it's cheese and attempting moves).

Space Complexity: O(rows × cols) We need to track visited cells in a set or 2D array, which requires space proportional to the grid size. Additionally, the recursion call stack can go as deep as the number of cells in the worst case (a long winding path).

What We've Learned

DFS/BFS with limited API: When you can't directly access a graph structure but have movement primitives (move, check state), use depth-first search with backtracking - explore each direction, mark visited positions, and backtrack when hitting dead ends to systematically cover all reachable cells.
Visited state tracking without direct access: Since you can't see the grid, maintain a Set of visited coordinates by tracking your position through successful moves - this prevents infinite loops and ensures you don't revisit the same cell, which is critical when you can only interact through method calls.
Directional exploration pattern: Systematically try all four directions (up, down, left, right) at each position using a recursive helper function - if move() succeeds, recurse; if it fails or returns false, try the next direction. Always backtrack by moving in the opposite direction after exploring.
Coordinate tracking with relative movement: Without direct grid access, maintain current position (x, y) coordinates by updating them with each successful move() call - this allows you to track visited cells and implement backtracking by reversing your last move to return to previous positions.
Early termination optimization: Check isCheese() immediately after each successful move before recursing deeper - this prevents unnecessary exploration once the goal is found and is crucial when working with opaque APIs where you can't pre-compute paths.
Blind search applications: This pattern applies to robot navigation, maze solving, and API-constrained exploration problems in real systems where you control an agent through limited commands (IoT devices, game bots, automated testing) rather than having full state visibility.

Test Your Understanding

Why is matrix the right data structure for this problem?

matrix provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early December, 2025

Meta

Mid-level

Late November, 2025

Meta

Mid-level

Early November, 2025

Meta

Senior

Get Premium to View All 10+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Help Mouse Find the Cheese

DESCRIPTION

Understanding the Problem

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact