Guide a mouse to find cheese with APIs
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are controlling a mouse in an unknown 2D grid maze. Some cells are blocked (walls), some are open, and **at most one** open cell contains a piece of cheese. You do **not** know the maze layout or the cheese location in advance.
You can only interact with the maze through the following API on a `Mouse` object (conceptually similar to an interview “black-box” robot API):
- `bool canMove(Direction dir)`: returns whether the adjacent cell in direction `dir` is open.
- `void move(Direction dir)`: moves the mouse one cell in direction `dir`. (You may assume you will only call `move` when `canMove(dir)` is true.)
- `bool atCheese()`: returns whether the mouse is currently on the cheese cell.
`Direction` is one of `{UP, DOWN, LEFT, RIGHT}`.
### Task
Implement a function `bool findCheese(Mouse mouse)` that:
- Returns `true` and **moves the mouse onto the cheese** if the cheese is reachable from the start.
- Returns `false` if the cheese does not exist or is not reachable.
### Notes / Constraints
- The grid is finite but its dimensions are unknown.
- The mouse starts on an open cell.
- You may move the mouse arbitrarily during the search (including revisiting cells).
- Aim for an algorithm that is guaranteed to terminate.
Quick Answer: This question evaluates the ability to reason about graph exploration and stateful API interaction in an unknown 2D grid, assessing competencies in search strategy design, correctness, and termination properties within the Coding & Algorithms domain.
You are given a finite 2D maze that simulates the original black-box Mouse API interview problem. The maze uses these characters:
- 'S' = starting cell of the mouse
- 'C' = cheese cell
- '.' = open cell
- '#' = wall
There is exactly one 'S' and at most one 'C'.
In the original API version, the mouse only knows whether it can move one step in a direction, can move there, and can check whether it is currently standing on the cheese. Your task is to return the same result that a correct API-based search would return:
- Return True if the cheese exists and is reachable from 'S'.
- Return False if the cheese does not exist or cannot be reached.
A correct strategy must always terminate on a finite maze, even if the maze contains cycles.
Constraints
- 1 <= number of rows, number of columns <= 100
- Each cell is one of 'S', 'C', '.', '#'
- Exactly one cell is 'S'
- At most one cell is 'C'
- All rows have the same length
Examples
Input: (['S.C'],)
Expected Output: True
Explanation: The mouse can move right twice to reach the cheese.
Input: (['S#C'],)
Expected Output: False
Explanation: The wall blocks the only direct path from the start to the cheese.
Input: (['S..#', '##.#', 'C...'],)
Expected Output: True
Explanation: A valid path is RIGHT, RIGHT, DOWN, DOWN, LEFT, LEFT.
Input: (['S'],)
Expected Output: False
Explanation: This is a single-cell maze with no cheese.
Input: (['S..', '###', '..C'],)
Expected Output: False
Explanation: The cheese is in a disconnected open region separated by a full wall row.
Hints
- Treat each open cell as a node in a graph and use a visited set so you do not loop forever in cycles.
- In the API version, depth-first search works well: move into a new cell, explore, and if it fails, move back using the opposite direction.