Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Meta SWE coding round focused on extending a maze solver with direction-restricted cells. Pretty much a pure algorithmic problem with a clear setup but a tricky extension that required thinking carefully about state and BFS traversal logic.

Questions Asked (1)

You have a working BFS-based maze solver on a 2D grid with walls, open cells, a start, and an end. Some cells now have movement restrictions, like blocking backward movement or only allowing certain directions. Modify the BFS expansion logic so it only enqueues neighbors that are permitted from the current cell, and update the tests to cover the new behavior.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The base BFS part was fine, I've done that enough times.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the movement restriction model: are they per-cell direction constraints, or do they depend on the incoming direction? Then, modify the BFS expansion to check a permission function before enqueuing each neighbor, ensuring the visited set still prevents cycles. Finally, update tests to cover allowed and blocked moves, including edge cases like start/end restrictions and multiple paths.

Pro tip: Emphasize that the visited set must be updated only when a neighbor is actually enqueued, not when it's merely considered, to avoid marking unreachable cells as visited. Also, discuss how to handle restrictions that depend on the direction of arrival, which may require storing the incoming direction in the queue.

1. Clarify the restriction model

Ask whether restrictions are per-cell (e.g., cell only allows moving right) or depend on the direction of entry (e.g., cannot move backward relative to how you entered). This determines whether the queue needs to store direction state.

2. Design the permission check

Define a function or data structure that, given the current cell, incoming direction (if needed), and a candidate neighbor, returns whether the move is allowed. This encapsulates the restriction logic.

3. Modify BFS expansion

In the neighbor loop, before enqueuing, call the permission check. Only enqueue and mark visited if allowed. If direction-dependent, store the direction in the queue along with the cell.

4. Update tests

Add test cases for: allowed moves, blocked moves, direction-dependent restrictions (e.g., no backtracking), start/end with restrictions, and multiple paths where one is blocked. Ensure existing tests still pass.

5. Analyze complexity and trade-offs

Discuss time/space complexity: still O(R*C) if direction state is constant, but may increase if storing direction. Mention alternative approaches like Dijkstra if restrictions have costs.

Key Points to Mention

The visited set should only be updated when a neighbor is enqueued, not when considered, to avoid incorrect pruning.
If restrictions depend on the direction of arrival, the BFS queue must store the incoming direction, effectively expanding the state space to (cell, direction).
The permission check should be a separate, testable function to keep BFS logic clean and maintainable.
Tests should cover edge cases: start cell with restrictions, end cell unreachable due to restrictions, and cycles that might be allowed or blocked.
Time complexity remains O(R*C) if direction state is constant, but may become O(R*C*D) where D is number of directions if direction is stored.
Consider whether restrictions are symmetric (e.g., if A allows moving to B, does B allow moving to A?) and handle accordingly.

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