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 question evaluates algorithmic problem-solving skills with emphasis on discrete geometry, parity and symmetry reasoning, optimization for shortest-path movement, and careful edge-case handling.