Snapchat·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Snapchat SWE interview with a grid-based BFS problem that sounds straightforward until you actually try to implement it under pressure. The follow-up angles on binary search tripped me up a bit.

Questions Asked (1)

You have a 2D grid where cells are either grass, fire, or walls. Starting from the top-left, you need to reach the bottom-right safehouse. Fire spreads each minute to adjacent grass cells, and walls block it. You can wait at the start before moving. What is the maximum number of minutes you can wait and still safely reach the safehouse? Return 10^9 if you can always make it, -1 if you never can.

Algorithms & Data Structures

Author's notes

My first instinct was just BFS from start to end, which is wrong because the fire is moving too.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a time-expanded graph or use binary search on the waiting time, checking feasibility with BFS. Precompute fire arrival times for each cell using multi-source BFS from all initial fires, then for a given wait time, run BFS from start to safehouse ensuring you arrive before the fire. The answer is the maximum wait time that allows a safe path, or 10^9 if you can wait indefinitely, -1 if impossible even with zero wait.

Pro tip: Clarify that waiting at the start is equivalent to delaying your departure, and that you can also wait at intermediate cells if needed—but the problem only asks for waiting at the start. Mention that binary search works because feasibility is monotonic: if you can wait T minutes, you can wait any T' < T.

1. Understand the problem and constraints

Restate the problem: grid with grass, fire, walls; fire spreads each minute; you start at top-left, want to reach bottom-right; you can wait at start. Determine if waiting indefinitely is possible (10^9), impossible (-1), or a finite maximum.

2. Precompute fire arrival times

Run multi-source BFS from all initial fire cells to compute the earliest time each cell catches fire. Use a 2D array fireTime, with INF for unreachable cells.

3. Define feasibility check for a given wait time

For a candidate wait time W, run BFS from start to safehouse, only moving to cells where your arrival time (W + steps) is strictly less than fireTime[cell]. Also ensure start and safehouse are not on fire at time W and W+steps respectively.

4. Binary search for maximum wait time

Binary search W in [0, upper bound]. If feasible, try larger; else try smaller. Upper bound can be max fireTime or a large number if fire never reaches safehouse. Handle edge cases: if start or safehouse is fire initially, return -1; if safehouse never catches fire and reachable, return 10^9.

5. Return the result

After binary search, if no W >= 0 is feasible, return -1. If feasible for all W up to a large bound (e.g., safehouse never burns), return 10^9. Otherwise return the maximum feasible W.

Key Points to Mention

Multi-source BFS to compute fire spread times efficiently.
Binary search on the waiting time due to monotonic feasibility.
BFS for pathfinding with time constraints (arrival before fire).
Handling edge cases: start/safehouse initially on fire, unreachable safehouse, fire never reaches safehouse.
Time complexity: O(R*C log(maxTime)) with BFS per check, or O(R*C) with time-expanded graph.
Clarify that waiting at intermediate cells is not allowed unless specified; only waiting at start is considered.

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