Quick Overview

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

Choose K pickup locations minimizing L1 distance

Company: Uber

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## 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`).

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

You are given the coordinates of **N people** on a 2D grid and an integer **K**. Open **K shuttle pickup locations** so that the **sum of Manhattan (L1) distances** from each person to their **nearest** pickup location is minimized, and return that minimum total distance. For this executable version, adopt the standard facility-location simplification (state your assumptions in an interview): **each pickup location must be placed at one of the given people's coordinates.** Two people may share the same coordinate, and a pickup location may coincide with multiple people. If `K >= N`, every person can host (or share) a pickup point, so the total distance is `0`. **Function signature:** `chooseKLocations(points, k)` returns an integer — the minimum achievable total L1 distance. ### Definitions For person `i` at `(xi, yi)` and the chosen set of centers `C`, their cost is `min over (X, Y) in C of (|xi - X| + |yi - Y|)`. The answer is the sum of these costs over all people, minimized over all valid choices of `C` with `|C| = K`. ### Examples - `points = [[0,0],[0,1],[10,10],[10,11]]`, `k = 2` -> `2` (centers at `(0,0)` and `(10,10)`; the two remaining people are each 1 away). - `points = [[0,0],[2,0],[4,0]]`, `k = 1` -> `4` (center at the median `(2,0)`; costs `2 + 0 + 2`). - `points = [[0,0],[3,4]]`, `k = 2` -> `0` (each person hosts a pickup point). ### Note on approach General K-medians is NP-hard, but with the centers-must-be-people restriction and small interview-sized inputs you can return the exact optimum by enumerating every K-subset of points and scoring each in O(N) — overall `O(C(N,K) * N * K)`. State this complexity and, in a real interview, also discuss heuristics (k-means/k-medians style local search, or DP for the 1D case) for larger inputs.

Constraints

  • 1 <= N (number of people) -- inputs are small enough that brute force over K-subsets is feasible.
  • 1 <= K; if K >= N the answer is 0.
  • Coordinates are integers (may be negative).
  • Pickup locations must be placed at one of the given people's coordinates.
  • Duplicate coordinates are allowed.

Examples

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

Expected Output: 2

Explanation: Place centers at (0,0) and (10,10). Person (0,1) is 1 away, person (10,11) is 1 away, the two centers cost 0. Total = 2.

Input: ([[0, 0], [2, 0], [4, 0]], 1)

Expected Output: 4

Explanation: With one center, the optimal point among the three is the median (2,0): |0-2| + 0 + |4-2| = 2 + 0 + 2 = 4.

Hints

  1. Clarify the rules first: must centers be integer coordinates, and must they be chosen from existing people? Here we assume centers must be one of the given points -- a standard facility-location simplification that makes an exact answer tractable.
  2. If K >= N, you can give every person their own pickup point, so the total distance is 0. Handle this special case up front.
  3. For each candidate set of K centers, the cost of a person is the L1 distance to their NEAREST center -- not to all of them. Take the min over centers, then sum over people.
  4. With centers restricted to the given points and small N, enumerate every K-subset of points (itertools.combinations) and keep the best total. This is exact.
  5. For larger inputs, discuss heuristics: k-medians local search (Lloyd-style swap), or note that the 1D version decomposes (sort + DP) while the 2D L1 version couples x and y through the assignment.

Loading coding console...