Find shortest path in an OOP maze
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are working in a codebase that models a maze using object-oriented classes. The maze contains open cells and walls. You are given an entrance cell and an exit cell.
Implement a function that returns the length of the shortest path from entrance to exit using 4-directional movement (up/down/left/right). If no path exists, return `-1`.
## Provided Interfaces (conceptual)
Assume you are given objects with methods similar to:
- `maze.get_entrance() -> Cell`
- `maze.get_exit() -> Cell`
- `maze.get_neighbors(cell: Cell) -> List[Cell]`
Returns adjacent cells you can move to (already excludes walls/out-of-bounds).
- `cell.id` (or any stable identity / coordinates)
You may assume `Cell` objects can be used to identify visited states (via `id`, coordinates, or hashing).
## Input
- A `Maze` object as described.
## Output
- Integer shortest distance (number of moves) from entrance to exit, or `-1`.
## Constraints
- Maze can be large; your solution should be `O(V+E)` where `V` is number of reachable cells.
## Example
If the shortest route requires 7 moves, return `7`.
Quick Answer: This question evaluates graph traversal and shortest-path reasoning within an object-oriented codebase, focusing on state representation, neighbor exploration, visited-state management, and time/space complexity analysis.
Represent the conceptual Maze API as entrance id, exit id, and adjacency map, then return shortest move count or -1.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('A', 'D', {'A':['B','C'], 'B':['D'], 'C':[], 'D':[]})
Expected Output: 2
Explanation: Shortest route A-B-D.
Input: ('A', 'A', {'A':['B']})
Expected Output: 0
Explanation: Entrance equals exit.
Input: ('A', 'Z', {'A':['B'], 'B':[]})
Expected Output: -1
Explanation: Unreachable exit.
Hints
- Pick a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.