Compute minimum escape time in a grid
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a 2D floor plan grid. Each cell is one of:
- `.` empty space (walkable)
- `#` wall/blocked (not walkable)
- `P` a person
- `E` an exit
A person can move 1 step per minute to the 4-neighbors (up/down/left/right) through walkable cells. Multiple people can occupy the same cell at the same time (ignore collisions).
Task:
1) Determine whether **every** person can reach **some** exit.
2) If everyone can escape, return the **minimum time until all people have escaped**, assuming each person walks optimally (i.e., the maximum over people of their shortest-path distance to any exit).
If some person cannot reach any exit, return `-1`.
Explain an algorithm and its time/space complexity.
Quick Answer: This question evaluates a candidate's competence in graph traversal, shortest-path computation, and reachability analysis on grid-based representations.
Return the time until all people reach some exit optimally, or -1 if any person cannot reach an exit.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (['P.E','...'],)
Expected Output: 2
Explanation: One person reaches the nearest exit in two steps.
Input: (['P#E'],)
Expected Output: -1
Explanation: A wall can make escape impossible.
Hints
- Run multi-source BFS from all exits.
- Then read each person distance.