Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Interviewed for a SWE role at Uber and got the classic knight moves BFS problem. Pretty standard algorithmic round, nothing too wild.

Questions Asked (1)

Given an infinite chessboard and a knight starting at [0, 0], find the minimum number of moves required to reach a target square [x, y].

Algorithms & Data Structures

Author's notes

BFS was the obvious approach and I went with it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then propose BFS on a bounded board as a baseline. For an infinite board, derive a closed-form solution using symmetry and special cases, and discuss trade-offs between approaches.

Pro tip: Mention that for large coordinates, the answer is roughly max(ceil(x/2), ceil(y/2), ceil((x+y)/3)) with adjustments for small values, showing you understand the mathematical optimization beyond brute force.

1. Clarify the problem

Ask about constraints: Is the board truly infinite? Are x and y non-negative? Can the knight move in all 8 directions? Confirm that the target is reachable (always true on infinite board).

2. Consider BFS for small targets

For small coordinates, BFS from [0,0] until target is reached is straightforward. Use a queue and a visited set, but note that on an infinite board, BFS may explore many nodes if target is far.

3. Derive closed-form for large targets

Use symmetry to reduce to first quadrant. For large x,y, the minimum moves is max(ceil(x/2), ceil(y/2), ceil((x+y)/3)). Handle special cases like (0,0), (1,0), (2,2), etc., with precomputed values.

4. Validate with examples

Test the formula on known cases: (0,0)->0, (1,0)->3, (2,2)->4, (3,3)->2, etc. Explain how to adjust for parity or small offsets.

5. Discuss trade-offs and implementation

Compare BFS (O(x*y) time) vs closed-form (O(1) time). For an interview, code the closed-form with special cases, or BFS if constraints are small. Mention that BFS can be optimized with bidirectional search.

Key Points to Mention

BFS as a baseline for small targets, with time complexity O(x*y) and space O(x*y).
Symmetry: reduce to first quadrant by taking absolute values.
Closed-form formula: max(ceil(x/2), ceil(y/2), ceil((x+y)/3)) for large x,y.
Special cases: (0,0)->0, (1,0)->3, (2,2)->4, (1,1)->2, (0,2)->2, etc.
Parity and offset adjustments: sometimes need to add 1 or 2 moves to satisfy parity.
Trade-offs: BFS is simple but slow for large coordinates; closed-form is O(1) but requires careful case handling.

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