How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Waymo.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Waymo during technical interviews.

Find Shortest Knight Path | Waymo Coding Question

Find Shortest Knight Path

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an `N x N` chessboard, a start cell `(sr, sc)`, and a target cell `(tr, tc)`, compute the minimum number of moves for a knight to reach the target. A knight moves in eight possible `L`-shaped directions: `(±2, ±1)` and `(±1, ±2)`. Requirements: - Return the length of the shortest path in number of moves. - If the target cannot be reached, return `-1`. - You should define the function signature and input/output format yourself. Follow-up questions: 1. How would your solution change if some cells are blocked and cannot be visited? 2. How would you solve it if the board were infinite instead of bounded?

Quick Answer: This question evaluates a candidate's ability to model grid-based movement as a graph and apply shortest-path traversal techniques, testing algorithmic problem-solving, state representation, and complexity analysis in the Coding & Algorithms domain.

Part 1: Find the Shortest Knight Path on a Bounded N x N Chessboard

You are given an N x N chessboard using 0-based indexing, a start cell start = (sr, sc), and a target cell target = (tr, tc). A knight can move in eight L-shaped directions: (+2, +1), (+2, -1), (-2, +1), (-2, -1), (+1, +2), (+1, -2), (-1, +2), and (-1, -2). Return the minimum number of knight moves needed to reach the target. If the target cannot be reached on this bounded board, return -1.

Constraints

1 <= n <= 500
start and target are tuples (r, c) with 0 <= r, c < n
Use 0-based board coordinates

Examples

Input: (8, (0, 0), (1, 2))

Expected Output: 1

Explanation: The target is exactly one legal knight move away.

Input: (4, (0, 0), (3, 3))

Expected Output: 2

Explanation: One shortest path is (0, 0) -> (1, 2) -> (3, 3).

Input: (1, (0, 0), (0, 0))

Expected Output: 0

Explanation: Start and target are the same cell.

Input: (2, (0, 0), (1, 1))

Expected Output: -1

Explanation: On a 2 x 2 board, a knight cannot make any legal move from (0, 0).

Input: (8, (0, 0), (7, 7))

Expected Output: 6

Explanation: A shortest path exists in 6 moves on a standard 8 x 8 board.

Hints

Model each cell as a graph node and each legal knight move as an edge.
Because every move has the same cost, breadth-first search gives the shortest path.

Part 2: Find the Shortest Knight Path When Some Cells Are Blocked

You are given an N x N chessboard using 0-based indexing, a start cell start = (sr, sc), a target cell target = (tr, tc), and a list of blocked cells. A knight can move in the usual eight L-shaped directions, but it may not land on blocked cells. Return the minimum number of knight moves needed to reach the target. If the target cannot be reached, return -1. If the start or target cell is blocked, return -1.

Constraints

1 <= n <= 500
start and target are tuples (r, c) with 0 <= r, c < n
blocked contains 0 or more board cells
Use 0-based board coordinates

Examples

Input: (6, (0, 0), (5, 5), [(1, 2)])

Expected Output: 4

Explanation: The blocked cell removes one immediate option, but a shortest path still exists in 4 moves, such as (0, 0) -> (2, 1) -> (4, 2) -> (3, 4) -> (5, 5).

Input: (5, (0, 0), (4, 4), [(1, 2), (2, 1)])

Expected Output: -1

Explanation: From (0, 0), the only legal knight moves are (1, 2) and (2, 1), and both are blocked.

Input: (5, (2, 2), (2, 2), [])

Expected Output: 0

Explanation: Start and target are the same cell, so no moves are needed.

Input: (5, (0, 0), (4, 4), [(4, 4)])

Expected Output: -1

Explanation: The target cell is blocked, so it cannot be visited.

Input: (5, (0, 0), (4, 4), [(0, 0)])

Expected Output: -1

Explanation: The start cell is blocked, so the knight cannot begin.

Hints

This is still a shortest-path problem on an unweighted graph, so BFS is a strong fit.
Treat blocked cells as removed nodes, and check the start and target before running the search.

Part 3: Find the Shortest Knight Path on an Infinite Chessboard

You are given two cells start = (sx, sy) and target = (tx, ty) on an infinite chessboard. A knight can move in eight L-shaped directions: (+2, +1), (+2, -1), (-2, +1), (-2, -1), (+1, +2), (+1, -2), (-1, +2), and (-1, -2). Return the minimum number of knight moves needed to reach the target. The board is unbounded in every direction, and coordinates may be negative.

Constraints

-10^9 <= sx, sy, tx, ty <= 10^9
Coordinates are integers
The board is infinite, so every target is reachable

Examples

Input: ((0, 0), (0, 0))

Expected Output: 0

Explanation: No movement is needed.

Input: ((0, 0), (1, 2))

Expected Output: 1

Explanation: This is one direct knight move.

Input: ((0, 0), (1, 0))

Expected Output: 3

Explanation: A knight cannot move one square straight in fewer than 3 moves.

Input: ((0, 0), (2, 2))

Expected Output: 4

Explanation: This is a known special case for knight distance on an infinite board.

Input: ((0, 0), (7, 7))

Expected Output: 6

Explanation: A larger example that shows why a direct formula is useful.

Hints

Use symmetry: only the absolute difference between the coordinates matters, and you can reorder so x >= y.
There are a couple of small special cases, and then parity helps adjust the final answer.

Quick Overview

This question evaluates a candidate's ability to model grid-based movement as a graph and apply shortest-path traversal techniques, testing algorithmic problem-solving, state representation, and complexity analysis in the Coding & Algorithms domain.