Quick Overview

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.

Minimize Total Assignment Distance

Company: Dark Alpha Capital

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

Assign each analyst to a distinct device minimizing total Manhattan distance.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

Input: ([(0,0),(2,2)], [(0,1),(2,3),(10,10)])

Expected Output: 2

Explanation: Assign each analyst to a distinct nearest combination.

Input: ([(0,0)], [(5,5),(1,1)])

Expected Output: 2

Explanation: Single analyst picks closest device.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.

Loading coding console...