Pinterest·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Pinterest coding screen with a grid traversal problem. Pretty straightforward on the surface but they wanted you to actually talk through complexity, not just code it up.

Questions Asked (1)

A robot vacuum on a 2D grid can move in 8 directions including diagonals. Starting from a given cell, find all cells reachable from that position assuming no obstacles, and return the count or a marked grid. Implement using BFS or DFS and discuss time/space complexity.

Algorithms & Data Structures

Author's notes

Went with BFS because I always reach for queues on grid problems, not sure that was the right call to lead with.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints (grid size, start cell, output format) and then implement BFS or DFS to explore all reachable cells using 8-directional movement. After traversal, return either the count of reachable cells or a marked grid, and analyze time and space complexity.

Pro tip: Mention that BFS is often preferred for grid traversal because it naturally explores level by level and can be more memory-efficient for large grids, but DFS is simpler to implement recursively. Also, note that with no obstacles, the entire grid is reachable, so the answer is always the total number of cells—this shows you understand the problem deeply.

1. Clarify requirements and constraints

Ask about grid dimensions, whether the start cell is guaranteed to be within bounds, and whether the output should be a count or a marked grid. Confirm that movement includes all 8 directions and that there are no obstacles.

2. Choose BFS or DFS and explain rationale

Decide between BFS and DFS based on factors like recursion depth, memory usage, and simplicity. Briefly justify your choice, e.g., BFS for level-order exploration or DFS for concise code.

3. Implement traversal with visited tracking

Write code to traverse the grid from the start cell, marking visited cells to avoid revisiting. Use a queue for BFS or a stack/recursion for DFS, and explore all 8 neighboring cells.

4. Return result and analyze complexity

After traversal, return the count of visited cells or the marked grid. Analyze time complexity as O(N*M) since each cell is visited once, and space complexity as O(N*M) for the visited set and queue/stack in the worst case.

Key Points to Mention

8-directional movement: include all combinations of row and column offsets (-1, 0, 1) except (0,0).
Visited tracking: use a 2D boolean array or a set to avoid infinite loops and redundant work.
BFS vs DFS trade-offs: BFS uses a queue and explores level by level; DFS uses a stack or recursion and may be simpler but can hit recursion limits.
Time complexity: O(N*M) where N and M are grid dimensions, as each cell is processed once.
Space complexity: O(N*M) for the visited structure and the queue/stack in the worst case.
Edge cases: start cell at boundaries, 1x1 grid, and the fact that with no obstacles all cells are reachable.

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