Coding questions · Snapchat

Compute minimum escape time in a grid

This question evaluates a candidate's competence in graph traversal, shortest-path computation, and reachability analysis on grid-based representations.

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:

Determine whether every person can reach some exit.
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.

Minimum Escape Time In Grid

Examples

Example 1

Input: (['P.E','...'],)
Output: 2

Explanation: One person reaches the nearest exit in two steps.

Example 2

Input: (['P#E'],)
Output: -1

Explanation: A wall can make escape impossible.

Hints

Run multi-source BFS from all exits.
Then read each person distance.