← Meta Interview Insights

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

Senior
May 2026

Summary

Meta SWE coding round, two-part question on pathfinding. Part A was a clean BFS warmup, Part B was where things got interesting and a bit messy for me.

Questions Asked (2)

Q1

Given an m×n binary grid where 0 is open and 1 is an obstacle, find the shortest path from the top-left to the bottom-right cell using four-directional movement, returning -1 if no path exists. Describe your algorithm, prove correctness, and analyze time and space complexity.

Algorithms & Data Structures
Author's notes

BFS, straightforward.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use BFS to find the shortest path in an unweighted grid, treating each cell as a node and moves to adjacent open cells as edges. Start from the top-left, explore level by level, and return the distance when reaching the bottom-right or -1 if unreachable. Then prove correctness by arguing BFS explores nodes in non-decreasing distance order, and analyze time and space as O(mn).

Pro tip: Explicitly state that BFS is optimal for unweighted shortest paths, and mention that you'd handle edge cases like start or end being blocked. Also, note that you can optimize space by using a visited matrix or modifying the grid in-place if allowed.

1. Clarify problem and edge cases

Confirm grid dimensions, movement directions, and that start/end are open. Discuss handling of blocked start/end and empty grid.

2. Choose BFS and outline algorithm

Explain that BFS is ideal for unweighted shortest path. Initialize a queue with start cell and distance 0, and a visited set or matrix.

3. Detail BFS traversal

While queue not empty, dequeue cell, check if it's the target, and if not, enqueue all valid unvisited neighbors with distance+1. Mark visited when enqueuing.

4. Prove correctness

Argue that BFS explores nodes in order of increasing distance, so the first time we reach the target, the distance is minimal. Also, if target not reached, no path exists.

5. Analyze complexity

Time: O(mn) since each cell is enqueued at most once. Space: O(mn) for queue and visited matrix in worst case.

Key Points to Mention

  • BFS guarantees shortest path in unweighted graphs.
  • Use a queue for level-order traversal and a visited matrix to avoid cycles.
  • Check for invalid start or end cells (obstacles) and return -1 immediately.
  • Distance can be tracked by storing (row, col, dist) in queue or using level-size loops.
  • Time complexity O(mn) and space complexity O(mn) due to queue and visited storage.
  • Alternative: bidirectional BFS can reduce time in practice, but worst-case remains O(mn).

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

Q2

You control a robot in an unknown finite 2D room with walls and obstacles. Using only move(), and optionally turnLeft()/turnRight() and atTarget(), design an algorithm to explore the room, find the target, and return the minimum number of steps from the start. Address coordinate tracking without a map, backtracking, optimality of the step count, and complexity in terms of reachable cells R.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This one hurt a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Propose a systematic exploration algorithm like DFS with backtracking, using relative coordinate tracking and a stack to record the path. After finding the target, compute the shortest path by BFS on the discovered graph or by analyzing the backtracking path to eliminate cycles.

Pro tip: Emphasize that while DFS guarantees finding the target, BFS on the discovered graph ensures the minimum step count; mention that the robot's limited sensing (only move, turn, atTarget) means you must build the map incrementally.

1. Define coordinate system and state

Establish a relative coordinate system with the start as origin and initial direction as north. Track the robot's position and orientation as it moves, updating coordinates based on moves and turns.

2. Explore using DFS with backtracking

Perform a depth-first search to explore all reachable cells. Use a stack to remember the path and backtrack when hitting dead ends, marking visited cells to avoid revisiting.

3. Detect target and record path

When atTarget() returns true, record the current path from start to target. This path may not be optimal due to backtracking.

4. Compute shortest path

Construct a graph of discovered cells and edges, then run BFS from start to target to find the minimum number of steps. Alternatively, analyze the DFS path to remove cycles.

5. Analyze complexity

The exploration visits each reachable cell at most twice (once forward, once backtrack), so time complexity is O(R). Space complexity is O(R) for the stack and visited set.

Key Points to Mention

  • Relative coordinate tracking without a global map: maintain position and orientation relative to start.
  • DFS with backtracking ensures complete exploration of finite connected component.
  • BFS on the discovered graph guarantees minimum step count from start to target.
  • Marking visited cells prevents infinite loops and ensures termination.
  • Complexity: O(R) time and space, where R is the number of reachable cells.
  • Trade-off: DFS exploration may not yield shortest path directly, so post-processing is needed.

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