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.

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.

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.

Minimum Assignment Distance

mediumDark Alpha CapitalSoftware Engineer

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

View full question (all parts)

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.

Examples

Example 1
Input
([(0,0),(2,2)], [(0,1),(2,3),(10,10)])
Output
2
Notes
Assign each analyst to a distinct nearest combination.
Example 2
Input
([(0,0)], [(5,5),(1,1)])
Output
2
Notes
Single analyst picks closest device.

Constraints

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

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Sample call
solution([(0,0),(2,2)], [(0,1),(2,3),(10,10)])
Language
Case 1
Input
([(0,0),(2,2)], [(0,1),(2,3),(10,10)])
Expected
2
Case 2
Input
([(0,0)], [(5,5),(1,1)])
Expected
2

Browse More Questions