How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Uber during technical interviews.

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.

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

Expected Output: 0

Explanation: A single person hosts the only pickup location, so the distance is 0.

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

Expected Output: 0

Explanation: All people share one coordinate; one center there gives 0 total distance even with K=1 < N.

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

Expected Output: 2

Explanation: Two clusters {0,1} and {5,6}. Centers at (1,0) and (5,0): costs 1 + 0 + 0 + 1 = 2.

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

Expected Output: 0

Explanation: K equals N, so each person becomes its own pickup location and the total distance is 0.

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

Expected Output: 16

Explanation: With one center the best choice is the central point (0,0); each of the four corners is L1 distance 4 away (16 total) and (0,0) itself is 0. No corner center does better.

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

Expected Output: 10

Explanation: Choose any three of the four corners as centers; the remaining corner's nearest center is an adjacent corner at L1 distance 10. Total = 10.

Hints

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.
If K >= N, you can give every person their own pickup point, so the total distance is 0. Handle this special case up front.
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.
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.
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.

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.