Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Meta SWE coding round with a multi-part grid maze problem. Four sub-questions building on the same grid setup, reachability through path counting. The layered structure felt intentional, like they were watching how you extend a solution rather than just whether you could solve it.

Questions Asked (1)

Given an m x n grid where cells are either free or blocked, and a start and target position, answer four sub-questions in sequence: (1) is the target reachable from the start, (2) what is the shortest number of steps to reach it, (3) return one valid shortest path as a coordinate list, and (4) count the total number of distinct shortest paths.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The first two parts were fine, BFS is BFS.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and then propose a unified BFS solution that naturally answers all four sub-questions: BFS gives reachability, shortest distance, and a shortest path via parent pointers; augment BFS to count shortest paths by summing counts from predecessors. Discuss trade-offs between BFS and other approaches (e.g., A* for pathfinding, DP for counting) and mention optimizations like bidirectional BFS for large grids.

Pro tip: Mention that the counting sub-question requires careful handling of multiple predecessors and that using a queue with distance tracking avoids revisiting nodes, ensuring O(mn) time. Also, note that returning a path can be done by backtracking from the target using parent pointers, and that storing parents for all nodes is O(mn) space, which is acceptable but can be optimized if only one path is needed.

1. Clarify requirements and constraints

Ask about grid size, movement directions (4 or 8), whether start/target can be blocked, and if the grid can be modified. Confirm that all sub-questions should be answered in sequence and that a single traversal is preferred.

2. Choose BFS as the core algorithm

Explain that BFS from the start explores cells in increasing distance order, so it can determine reachability, shortest distance, and a shortest path. For counting, augment BFS to track the number of shortest paths to each cell.

3. Implement BFS with distance and path tracking

Use a queue for BFS, a distance array initialized to -1, and a parent array to reconstruct the path. When visiting a neighbor, if unvisited, set distance and parent; if already visited with distance+1, update path count by adding the current cell's count.

4. Answer sub-questions in order

After BFS, check if target is reachable (distance != -1), report distance, reconstruct path by backtracking from target to start using parents, and report the path count stored at the target.

5. Discuss trade-offs and optimizations

Mention that BFS is O(mn) time and space, which is optimal for unweighted grids. For very large grids, bidirectional BFS can reduce search space. For counting, if the grid is huge, consider modular arithmetic to avoid overflow.

Key Points to Mention

BFS guarantees shortest path in unweighted graphs and naturally provides distance and reachability.
Path counting requires summing the number of shortest paths from all predecessors when a node is reached at the same distance.
Parent pointers allow reconstruction of one shortest path by backtracking from target to start.
Time and space complexity: O(mn) for BFS, which is optimal for this problem.
Edge cases: start equals target, blocked start or target, no path exists.
Trade-offs: bidirectional BFS for performance, DP for counting if grid is a DAG, but BFS is simpler and handles cycles.

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