UiPath·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Got a coding round at UiPath for an ML Engineer role and they threw a pure algorithms problem at me, which I wasn't really expecting. It was a knight-moves-on-infinite-grid variant and the scale of the coordinates meant BFS alone would've been a disaster.

Questions Asked (1)

On an infinite 2D grid, a piece moves in L-shapes (like a chess knight). Given a target coordinate where each axis can be up to 1 billion in magnitude, write a function that returns the minimum number of moves to reach that target from the origin. You must exploit symmetry, handle edge cases, and explain your algorithm with complexity analysis.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was BFS and I even started writing it out before realizing coordinates go up to 1e9.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Reduce the problem to the first quadrant using symmetry, then derive a closed-form formula for the minimum moves by analyzing small cases and identifying patterns. For large coordinates, use the formula directly, handling edge cases like (0,0), (1,0), and (2,2) separately.

Pro tip: Mention that the knight's move problem can be solved in O(1) time and space, which is crucial for coordinates up to 1e9. Also, relate it to potential ML applications like path planning in grid worlds, showing breadth.

1. Symmetry Reduction

Use absolute values to map the target to the first quadrant (x >= 0, y >= 0) and sort so that x >= y. This simplifies the problem without loss of generality.

2. Base Cases and Small Examples

Compute minimum moves for small coordinates manually or via BFS to identify patterns. Note special cases: (0,0) -> 0, (1,0) -> 3, (2,2) -> 4.

3. Derive Formula

For large x and y, the minimum moves is max(ceil(x/2), ceil((x+y)/3)) adjusted to have the same parity as x+y. Alternatively, use the known formula: if x < y swap; if x==1 and y==0 return 3; if x==2 and y==2 return 4; else return max(ceil(x/2), ceil((x+y)/3)) + ((max(ceil(x/2), ceil((x+y)/3)) + x + y) % 2).

4. Complexity Analysis

The algorithm runs in O(1) time and O(1) space, as it only involves arithmetic operations on the input coordinates.

5. Edge Cases and Testing

Explicitly handle edge cases like (0,0), (1,0), (2,2), and large values. Test with random coordinates against a BFS for small values to validate the formula.

Key Points to Mention

Symmetry reduction to first quadrant and sorting coordinates.
Special cases: (0,0), (1,0), (2,2) require separate handling.
Closed-form formula using max(ceil(x/2), ceil((x+y)/3)) with parity adjustment.
O(1) time and space complexity, essential for large coordinates.
Validation of formula with BFS for small coordinates.
Potential ML applications: path planning, grid-based environments.

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