Coding questions · Dark Alpha Capital
Minimize Total Assignment Distance
This question evaluates competency in combinatorial optimization, assignment/matching problems, and reasoning about Manhattan distance cost metrics. Commonly asked to assess algorithmic reasoning about constrained assignments, search and complexity trade-offs, it belongs to the Coding & Algorithms domain and emphasizes practical application of algorithm design and implementation rather than purely conceptual theory.
You are given the coordinates of n analysts and m field devices on a 2D grid, where 1 <= n <= 10 and n <= m <= 15. Each analyst must be assigned exactly one distinct device, and each device can be assigned to at most one analyst.
The cost of assigning analyst i at (ax[i], ay[i]) to device j at (dx[j], dy[j]) is the Manhattan distance:
|ax[i] - dx[j]| + |ay[i] - dy[j]|
Return the minimum possible total assignment cost after assigning a unique device to every analyst.
Design an algorithm efficient enough for the given constraints.
Minimum Assignment Distance
Examples
Example 1
Input: ([(0,0),(2,2)], [(0,1),(2,3),(10,10)])
Output: 2
Explanation: Assign each analyst to a distinct nearest combination.
Example 2
Input: ([(0,0)], [(5,5),(1,1)])
Output: 2
Explanation: Single analyst picks closest device.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.