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 Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at UiPath.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at UiPath during technical interviews.

Compute Minimum L-Moves on Infinite Grid

Quick Overview

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.

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.

Input: (1, 0)

Expected Output: 3

Explanation: Corner case. The closest single jumps overshoot, so reaching the immediate (1,0) neighbor takes 3 moves.

Input: (2, 2)

Expected Output: 4

Explanation: Corner case. (2,2) lies just off every 2-move reach pattern and needs 4 moves.

Input: (5, 5)

Expected Output: 4

Explanation: On the main diagonal far from the origin, four balanced L-moves cover (5,5).

Input: (-3, 4)

Expected Output: 3

Explanation: Signs are irrelevant by symmetry; equivalent to (3,4) -> after swapping x>=y treat as (4,3). Three moves suffice.

Input: (0, 1)

Expected Output: 3

Explanation: Symmetric to (1,0); the same corner case, 3 moves.

Input: (2, 1)

Expected Output: 1

Explanation: (2,1) is a single legal L-move from the origin.

Input: (-2, -1)

Expected Output: 1

Explanation: Absolute values give (2,1), one move; signs do not change the count.

Input: (1000000000, 1000000000)

Expected Output: 666666668

Explanation: Large diagonal target; the O(1) formula handles 1e9 instantly where BFS would be infeasible.

Input: (1000000000, 0)

Expected Output: 500000000

Explanation: Far along one axis: roughly half as many moves as the coordinate, matching the formula.

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.

Quick Overview