Minimize Total Assignment Distance
Dark Alpha CapitalSoftware Engineer · Technical ScreenLast updated
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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.