Compute Minimum L-Moves on Infinite Grid
Company: UiPath
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
On an infinite 2D grid, a chess-like piece moves in L-shapes: from (x, y) it can go to (x±1, y±
2) or (x±2, y±
1). Given integer target coordinates (tx, ty) with |tx|, |ty| ≤ 1e9, implement a function minLMoves(tx, ty) that returns the minimum number of moves needed to reach (tx, ty) starting from (0,
0). Exploit symmetry to optimize your solution and handle edge cases carefully. Explain your algorithm, prove correctness intuitively, and analyze time and space complexity.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute Minimum L-Moves on Infinite Grid states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
On an infinite 2D grid, a chess-knight-like piece moves in L-shapes: from (x, y) it can jump to (x±1, y±2) or (x±2, y±1) — eight possible moves in total. Starting from the origin (0, 0), return the minimum number of moves needed to reach the target cell (tx, ty).
The target may have very large coordinates (|tx|, |ty| up to 1e9), so a plain breadth-first search over the grid is far too slow and memory-hungry. You must exploit the problem's symmetry and derive a closed-form (O(1)) answer.
Implement `minLMoves(tx, ty)` returning that minimum move count.
Symmetry to exploit:
- The eight L-moves are symmetric across both axes, so the answer depends only on (|tx|, |ty|). Reduce to the first quadrant by taking absolute values.
- The answer is also symmetric in its two arguments, so you may further assume x ≥ y.
Key idea: after reducing to x ≥ y ≥ 0, let delta = x - y. Each move changes the coordinate sum's parity and lets you 'spend' the gap efficiently. Two small corner cases, (1, 0) and (2, 2), break the general pattern and must be special-cased (their true answers are 3 and 4, not what the bulk formula yields).
Constraints
- -1e9 <= tx, ty <= 1e9
- The piece starts at the origin (0, 0).
- Eight legal moves from (x, y): (x±1, y±2) and (x±2, y±1).
- A move count always exists (the grid is infinite and the piece can reach any cell).
- A BFS solution is correct in principle but will TLE / run out of memory for |tx|, |ty| near 1e9 — an O(1) closed form is required.
Examples
Input: (0, 0)
Expected Output: 0
Explanation: Already at the origin; no moves needed.
Input: (1, 1)
Expected Output: 2
Explanation: (0,0) -> (2,-1) -> (1,1): two L-moves reach the near-diagonal cell.
Hints
- The eight moves are symmetric across both the x- and y-axes, so the answer is unchanged by the signs of tx and ty. Replace them with their absolute values immediately.
- The move set is also symmetric in swapping the two coordinates, so without loss of generality assume x >= y after taking absolute values.
- Brute-force BFS on small targets (say all x,y in 0..12) to build a ground-truth table, then look for a pattern in terms of delta = x - y and y.
- Two cells refuse to fit the bulk pattern: (1, 0) needs 3 moves and (2, 2) needs 4. Special-case them before applying the general formula.
- Branch on whether y exceeds delta = x - y: when it does you correct toward the diagonal in chunks of 3, otherwise you advance along one axis in chunks of 4 — each correction adds 2 'extra' moves.