Snapchat·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

Snapchat coding round, got a grid fire-spreading problem that's essentially a well-known LC hard. Knew the general shape of the solution but the implementation details took longer than I'd like to admit.

Questions Asked (1)

On a grid with empty cells, walls, and fire sources, fire spreads outward each minute. You start at the top-left and need to reach the bottom-right safehouse. Find the maximum number of minutes you can wait at the start and still guarantee reaching the safehouse safely. Return a large constant if you can wait indefinitely, or -1 if it's impossible.

Algorithms & Data Structures

Author's notes

I recognized the fire-spreading part pretty fast and jumped straight to multi-source BFS for fire arrival times.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a time-expanded graph or use multi-source BFS to compute fire arrival times and person arrival times. Then binary search on the waiting time, checking feasibility by simulating the person's movement while ensuring they always arrive before the fire. If the person can reach the safehouse without waiting, return a large constant; if even waiting 0 minutes fails, return -1.

Pro tip: Clarify edge cases upfront: what if the start or safehouse is initially on fire? Also, mention that the fire spread is independent of the person's movement, so precomputing fire times is valid.

1. Understand the problem and constraints

Restate the problem: grid with walls, fire sources, start top-left, target bottom-right. Fire spreads each minute. Find maximum wait time to still reach safely. Clarify if fire spreads to all 4 directions and if waiting at start is allowed.

2. Precompute fire arrival times

Run multi-source BFS from all fire sources to compute the earliest time each cell catches fire. Use a 2D array fireTime where fireTime[r][c] is the minute fire reaches (r,c), or infinity if never.

3. Define feasibility check for a given wait time

For a candidate wait time W, simulate the person's earliest arrival using BFS from start, starting at time W. A cell (r,c) is safe to enter at time t if t < fireTime[r][c]. The person can move to adjacent cells each minute. Check if target is reachable with arrival time < fireTime[target].

4. Binary search for maximum wait time

The feasibility is monotonic: if you can wait W minutes, you can wait any smaller time. Binary search W between 0 and a safe upper bound (e.g., number of cells). If W=0 is infeasible, return -1. If feasible for very large W (e.g., > max possible time), return a large constant.

5. Handle edge cases and return result

Check if start or target is initially on fire. If start is on fire at time 0, impossible. If target never catches fire and is reachable, can wait indefinitely. Otherwise, return the maximum W found.

Key Points to Mention

Multi-source BFS to compute fire spread times efficiently.
BFS for person movement with time constraints (arrival time < fire time).
Binary search on the waiting time due to monotonic feasibility.
Time complexity: O(R*C log(R*C)) with binary search, or O(R*C) if using a single BFS with time dimension.
Edge cases: start or target on fire, unreachable target, fire never reaches target.
Use of large constant for indefinite waiting (e.g., 10^9) and -1 for impossible.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.