Meta·Machine Learning Engineer·Onsite - Coding / Algorithms·Senior

Senior

Jun 2026

Summary

Meta MLE coding round, one problem that looked like a grid traversal warmup but kept growing. The bomb mechanic was the real test and I wasn't fully prepared for how state-heavy it gets.

Questions Asked (1)

You have a 2D grid maze with walls, open cells, a start, and an end. You're using BFS or DFS to find the shortest path. Now add a new cell type: bombs. When the traveler steps on a bomb, all wall cells within a blast radius of 2 (your choice of Chebyshev or Manhattan distance) are destroyed and become passable. Implement a helper that returns which cells get destroyed, and update your search so the planner correctly reasons about different possible detonation states.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I went with Manhattan distance first and the interviewer was fine with that, just wanted me to document the choice.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem constraints and define the blast radius helper. Then, model the search state to include which bombs have been detonated, and adapt BFS/DFS to explore states with different wall configurations. Discuss trade-offs between state space explosion and optimality, and propose optimizations like memoization or A* with admissible heuristics.

Pro tip: Emphasize that the state must include the set of detonated bombs (or equivalently, the current wall configuration) to avoid incorrect paths; a common pitfall is to treat bombs as one-time triggers without tracking their effect on the grid.

1. Clarify requirements and assumptions

Ask about blast radius metric (Chebyshev vs Manhattan), whether bombs can be detonated multiple times, and if the traveler can choose to detonate or must detonate upon stepping. Confirm if the goal is to find the shortest path in terms of steps.

2. Implement the blast helper

Write a function that, given a bomb position and radius, returns all wall cells within the blast radius that become passable. Consider using a set to avoid duplicates and handle boundaries.

3. Define the search state

Extend the state to include the set of detonated bombs (or a bitmask if bombs are few). The state is (position, detonated_bombs). This ensures the search correctly reasons about different wall configurations.

4. Adapt BFS/DFS for state space

Modify the search to explore transitions: moving to adjacent cells (if passable) and detonating a bomb (if stepping on it). Update the wall configuration upon detonation. Use a visited set for states to avoid cycles.

5. Analyze complexity and optimizations

Discuss the exponential blow-up in states (2^B * N*M). Propose optimizations: only track bombs that affect the path, use A* with a heuristic, or precompute blast effects. Mention trade-offs between optimality and efficiency.

Key Points to Mention

State representation: (position, set of detonated bombs) to handle different wall configurations.
Blast radius helper: efficient computation using loops or precomputed patterns.
BFS guarantees shortest path if all edges have equal weight; DFS may not be optimal.
Complexity: O(2^B * N * M) where B is number of bombs; discuss pruning or heuristics.
Handling multiple bombs: order of detonation matters; state must capture which bombs are used.
Trade-offs: memory vs time, optimality vs speed, and potential use of A* with admissible heuristic.

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