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.
Hints
- For a fixed (a, b), this is an unweighted shortest-path problem on a grid graph, so BFS gives the minimum number of moves.
- The move set for (a, b) is identical to the move set for (b, a), so you can compute one and mirror the answer.
Part 2: Minimum Reversal Moves with Forbidden Positions
Positions are numbered from 1 to n. A token starts at position p, and some positions are forbidden and can never 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 needed to move the token there, or -1 if it is impossible. The input uses 1-indexed positions.
Constraints
- 1 <= n <= 200000
- 1 <= p <= n
- 1 <= k <= n
- 0 <= len(banned) < n
- All values in banned are distinct
- The starting position p is not forbidden
Examples
Input: (1, 1, [], 1)
Expected Output: [0]
Explanation: Only one position exists, so the token is already at the answer with distance 0.
Input: (5, 4, [2], 1)
Expected Output: [-1, -1, -1, 0, -1]
Explanation: A reversal of length 1 changes nothing, so only the starting position is reachable.
Hints
- If the token is at 0-indexed position i and you reverse a segment [l, l+k-1], its new position becomes 2*l + k - 1 - i.
- For a fixed current position, all next positions lie in one interval and all have the same parity. BFS is still the right idea, but you need a fast way to skip already-used positions of each parity.