FastPrepK-Means Delivery Zones
Problems/K-Means Delivery Zones

K-Means Delivery Zones

DoorDash logoDoorDash● MediumFULLTIMEPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: A DoorDash machine learning scientist interview report says the technical round asked the candidate to code k-means clustering by hand. The report gives no other detail.

It does not say how to pick the starting centers, how to measure distance, how to break ties, what to do when a center gets no points, when to stop, or what to return. Here, the first k points are the starting centers, even if some of them are the same. A point joins the center with the smallest squared distance, and ties go to the smaller center number. Each round assigns every point first, then moves each center to the average of its points, which can be a fraction. A center with no points stays where it is. You run maxIterations rounds and return each point's center from the last round. There are up to 300 integer points with 1 to 4 coordinates from -10^4 to 10^4, up to 8 centers and up to 50 rounds.

The judged task matches the report at about 55%.

DoorDash wants to split customer locations into k delivery zones. Each location is a point, and every point has the same number of integer coordinates. Implement k-means clustering from scratch. Follow the rules below exactly, so that everyone gets the same answer.

The squared distance between two points is the sum of the squared differences of their coordinates. For example, between (1, 2) and (4, 6) it is 3^2 + 4^2 = 25.

  1. There are k centers, numbered 0 to k - 1. Center j starts at points[j]. Two centers may start at the same place.
  2. Run maxIterations rounds. Each round has two steps:
    1. Assign: every point joins the center with the smallest squared distance to it. If several centers are equally close, the point joins the one with the smallest number.
    2. Update: every center moves to the mean (average) of the points that joined it, one coordinate at a time. The mean can be a fraction, such as 6.5. A center that no point joined stays where it is.
  3. Return an array answer where answer[i] is the center that points[i] joined in the last round.

If a round gives exactly the same assignment as the round before, nothing can change anymore, so you may stop early. The answer stays the same.

Function

kMeans(points: int[][], k: int, maxIterations: int) → int[]

Examples

Example 1

points = [[1],[2],[10],[11],[3]]k = 2maxIterations = 10return = [0,0,1,1,0]

The centers start at the first two points: center 0 is at 1 and center 1 is at 2.

Round 1: point 1 is closest to center 0. Points 2, 10, 11 and 3 are closest to center 1 (for 3, the squared distances are 4 and 1). Center 1 moves to (2 + 10 + 11 + 3) / 4 = 6.5.

Round 2: points 1, 2 and 3 are now closer to center 0 (for 3: 4 versus 12.25), and 10 and 11 stay with center 1. The centers move to (1 + 2 + 3) / 3 = 2 and (10 + 11) / 2 = 10.5.

Round 3 gives the same assignment, so nothing changes anymore. The answer is [0, 0, 1, 1, 0].

Example 2

points = [[0,0],[0,0],[4,0],[2,0]]k = 2maxIterations = 5return = [1,1,0,0]

Both centers start at (0, 0), because the first two points are the same.

Round 1: every point is equally close to both centers, so every point joins center 0, the smaller index. Center 0 moves to (1.5, 0). Center 1 got no points, so it stays at (0, 0).

Round 2: the two points at (0, 0) are now closer to center 1 (squared distance 0 versus 2.25). (4, 0) and (2, 0) stay with center 0 (6.25 versus 16, and 0.25 versus 4). Center 0 moves to (3, 0).

Round 3 gives the same assignment. The answer is [1, 1, 0, 0].

Example 3

points = [[0,0],[1,1],[5,5],[6,6],[2,2]]k = 2maxIterations = 2return = [0,0,1,1,1]

The centers start at (0, 0) and (1, 1).

Round 1: only (0, 0) joins center 0. The other four points are closer to center 1; for (2, 2) the squared distances are 8 and 2. Center 1 moves to (3.5, 3.5).

Round 2: (1, 1) switches to center 0 (2 versus 12.5). (2, 2) stays with center 1 (8 versus 4.5). The assignment is [0, 0, 1, 1, 1].

That was round maxIterations = 2, so we stop and return [0, 0, 1, 1, 1]. (A third round would move (2, 2) to center 0.)

Constraints

  • 1 <= points.length <= 300
  • 1 <= points[i].length <= 4
  • All points have the same number of coordinates.
  • -10^4 <= points[i][j] <= 10^4
  • 1 <= k <= 8
  • k <= points.length
  • 1 <= maxIterations <= 50
  • In every test, if two centers are not exactly equally close to a point, their squared distances differ by more than 10^-3. So ordinary double math gives the exact answer.

More DoorDash problems

  • Customer Bootstrap APIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Dasher Pay with Store Waits and Peak HoursPHONE SCREEN · Seen Nov 2026
  • Random Dasher Set OperationsONSITE INTERVIEW · Seen Nov 2026
All DoorDash interview questionsSee DoorDash hiring insights
Saved
public int[] kMeans(int[][] points, int k, int maxIterations) {
    // Write your code here.
}
Checking account…