Solve Knight and Reversal Problems
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
The online assessment contained two coding problems:
1. **Generalized knight shortest path**: Given an integer `n`, consider an `n x n` chessboard with coordinates from `(0, 0)` to `(n-1, n-1)`. For each ordered pair of positive integers `(a, b)` where `1 <= a, b < n`, a piece can move from `(x, y)` to any of the eight positions formed by applying `(+/-a, +/-b)` or `(+/-b, +/-a)`. For every `(a, b)`, compute the minimum number of moves needed to reach `(n-1, n-1)` starting from `(0, 0)`, or `-1` if the target is unreachable.
2. **Minimum segment reversals**: Positions are numbered from `1` to `n`. A token starts at position `p`, and some positions are forbidden and cannot be occupied. In one move, you may choose any contiguous segment of length `k` that contains the token, reverse that segment, and the token moves to its mirrored position inside the chosen segment. For every position from `1` to `n`, compute the minimum number of reversals required to move the token there, or `-1` if it cannot be reached. The assessment version used 1-indexed positions.
Quick Answer: This question evaluates graph modeling, state-space exploration, and shortest-path/reachability reasoning for nonstandard movement rules and constrained state transformations.
Part 1: Generalized Knight Distance Matrix
Given an integer n, consider an n x n chessboard with cells labeled from (0, 0) to (n-1, n-1). For each ordered pair of positive integers (a, b) such that 1 <= a, b < n, a piece may move from (x, y) to any of the eight cells obtained by adding (+/-a, +/-b) or (+/-b, +/-a). Return an (n-1) x (n-1) matrix where the value at row a-1 and column b-1 is the minimum number of moves needed to reach (n-1, n-1) starting from (0, 0). If the target cannot be reached for that (a, b), store -1 instead.
Constraints
- 1 <= n <= 25
- Coordinates are 0-indexed from (0, 0) to (n-1, n-1)
- For every pair (a, b), 1 <= a, b < n
Examples
Input: (1,)
Expected Output: []
Explanation: There are no valid pairs (a, b) when n = 1, so the result is an empty matrix.
Input: (2,)
Expected Output: [[1]]
Explanation: Only (a, b) = (1, 1) exists, and the piece reaches (1, 1) in one move.
Input: (3,)
Expected Output: [[2, 4], [4, 1]]
Explanation: For example, with (2, 2) the target is reached directly in one move, while the standard knight move (1, 2) needs four moves on a 3 x 3 board.