Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Meta phone screen, looked like a follow-up to a BFS grid problem with a twist thrown in mid-session. The one-way cell constraint made it more interesting than a standard shortest-path question.

Questions Asked (1)

You have a grid where some cells are one-way intersections that force movement in a specific direction. Modify your BFS solution to handle these directional constraints and still return the shortest path.

Algorithms & Data Structures

Author's notes

The base BFS I had was fine but the one-way cell part tripped me up for a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Explain that BFS still works but neighbor generation must respect the directional constraint: from a one-way cell, only the forced direction is allowed. Emphasize that the core BFS structure (queue, visited set, distance tracking) remains unchanged, and the shortest path guarantee holds because all edges have unit weight.

Pro tip: Mention that you would clarify the exact semantics of one-way intersections (e.g., whether they override normal movement or only apply when entering) and test edge cases like a one-way cell pointing off-grid or creating a dead end.

1. Clarify the problem

Confirm the grid representation, what a one-way intersection looks like, and whether movement is restricted only when leaving that cell. Ask about edge cases such as one-way cells at borders or unreachable targets.

2. Adapt neighbor generation

In the BFS loop, when processing a cell, check if it is a one-way intersection. If so, only consider the forced direction as a valid neighbor; otherwise, consider all four directions.

3. Maintain BFS invariants

Keep the queue, visited set, and distance tracking unchanged. Ensure that each cell is enqueued at most once and that distances are updated correctly.

4. Handle edge cases and validate

Test scenarios like one-way cells pointing into walls, cycles formed by one-way cells, and grids where the target is unreachable. Verify that the algorithm still returns the shortest path when one exists.

5. Analyze complexity

State that time and space complexity remain O(rows * cols) because each cell is processed once and neighbor checks are constant time.

Key Points to Mention

BFS explores level by level, so the first time we reach the target, it's the shortest path.
One-way intersections only restrict outgoing edges; incoming edges are unaffected unless specified otherwise.
Neighbor generation must be conditional: check cell type before adding neighbors.
Visited set prevents infinite loops and ensures each cell is processed once.
Edge cases: one-way cells at boundaries, dead ends, and unreachable targets.
Complexity remains O(V+E) = O(rows * cols) since each cell has at most 4 outgoing edges.

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