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 hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

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

Solve Knight and Reversal Problems | Uber Coding Question

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.

Input: (4,)

Expected Output: [[3, 2, 3], [2, -1, -1], [3, -1, 1]]

Explanation: Some move pairs can reach the target quickly, while others such as (2, 2) cannot reach (3, 3) at all on a 4 x 4 board.

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.

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

Expected Output: [1, 0, 1, -1]

Explanation: With k = 2, each move swaps the token with an adjacent position. Position 4 is forbidden, so only positions 1 and 3 are reachable.

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

Expected Output: [1, -1, 0, -1, 1]

Explanation: From the center, reversing a length-3 segment can move the token to positions 1 or 5 in one move. Positions 2 and 4 are never reached.

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

Expected Output: [3, 0, 1, 2, -1, 2]

Explanation: The forbidden position blocks some mirrored destinations, so the shortest paths are: 2->3, then 3->4 or 6, and position 1 is reached in three moves.

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.

Quick Overview

This question evaluates graph modeling, state-space exploration, and shortest-path/reachability reasoning for nonstandard movement rules and constrained state transformations.