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

Intermediate

Jun 2026

Summary

Coding round at Waymo for a software engineer role. One meaty graph traversal problem with follow-ups, and they wanted runnable code with a main method, not pseudocode.

Questions Asked (1)

Given an N x N chessboard, a starting cell, and a target cell, find the minimum number of moves for a chess knight to travel from start to target. The board is bounded, so the knight cannot leave the grid. Return -1 if the target is unreachable.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

BFS was the right call and I knew it, but I still spent a couple minutes talking through DFS before landing there.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a shortest path on an unweighted graph where each cell is a node and knight moves are edges. Use BFS from the start cell to find the minimum moves to the target, returning -1 if unreachable. Discuss time and space complexity, and consider optimizations like bidirectional BFS for large boards.

Pro tip: Mention that BFS is optimal for unweighted graphs and that bidirectional BFS can significantly reduce the search space, especially for large N. Also, note that the knight's graph is bipartite, so parity can sometimes quickly rule out unreachable targets.

1. Clarify the problem and constraints

Confirm the board size N, the start and target coordinates, and that the knight moves in standard L-shapes. Ask about edge cases like start equals target or N=1.

2. Choose the right algorithm

Recognize this as an unweighted shortest path problem and select BFS. Explain why BFS guarantees the minimum number of moves.

3. Implement BFS with a queue and visited set

Use a queue to explore moves level by level, marking visited cells to avoid cycles. Track the number of moves as you go.

4. Handle unreachable cases and return -1

If the queue empties without reaching the target, return -1. Also check if start equals target and return 0 immediately.

5. Analyze complexity and discuss optimizations

State O(N^2) time and space for standard BFS. Mention bidirectional BFS or A* with a heuristic for potential improvements.

Key Points to Mention

BFS is optimal for unweighted graphs, ensuring the minimum number of moves.
Time and space complexity: O(N^2) for an N x N board.
Use a visited set or 2D boolean array to avoid revisiting cells.
Edge cases: start equals target (return 0), unreachable target (return -1), and small boards (N=1,2,3).
Optimization: bidirectional BFS can reduce search space from O(b^d) to O(b^(d/2)).
Parity check: knight moves always change the color of the square, so if start and target are the same color, the number of moves must be even; this can quickly rule out some unreachable cases.

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