Katkat
Back

Choose K pickup locations minimizing L1 distance

UberMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates facility-location and spatial optimization skills under the Manhattan (L1) metric, testing algorithm design, combinatorial optimization, and handling geometric data.

Coding: K Shuttle Pickup Locations (L1)

You are given the coordinates of N people on a 2D grid. You want to open K shuttle pickup locations (pickup points) so that the sum of Manhattan (L1) distances from each person to their nearest pickup location is minimized.

Input

  • An integer N (number of people).
  • An array points of length N, where points[i] = (xi, yi) are integer coordinates.
  • An integer K (number of pickup locations).

Output

  • Return the minimum possible total L1 distance: [ \sum_{i=1}^{N} \min_{j=1..K} (|x_i - X_j| + |y_i - Y_j|) ] where ((X_j, Y_j)) are the chosen pickup locations.

Clarifications / assumptions (state in your solution)

  • Are pickup locations required to be at integer coordinates?
  • Are pickup locations required to be chosen from existing people’s coordinates, or can they be anywhere?

Constraints (you may assume)

Provide an algorithm appropriate for interview constraints (e.g., N up to a few thousand, K up to N).