Implement K-Means Clustering
Updated
Problem statement
Implement K-Means clustering without a clustering library. There are no random choices. Initialize the k centroids from the first k points, in input order. Duplicate initial centroids are allowed.
Perform at most rounds assignment passes. In each pass:
- For each point, compare squared Euclidean distances to the current centroids. Scan cluster indices from 0 upward. Replace the current best only if a later distance is smaller by more than
10^-9; otherwise keep the earlier index. - If all labels equal those from the previous pass, stop.
- Replace each nonempty cluster's centroid by the coordinate-wise mean of its assigned points. Keep an empty cluster's previous centroid.
Return each point's zero-based cluster index from the last assignment pass. Do not run an extra assignment after the pass limit. Keep the input points unchanged.
Function
clusterPoints(points: int[][], k: int, rounds: int) → int[]Examples
Example 1
points = [[0,0],[10,10],[1,0],[9,10]]k = 2rounds = 10return = [0,1,0,1]The first two points initialize centroids 0 and 1. The two points near the origin join 0, and the two near (10,10) join 1. Updated centroids (0.5,0) and (9.5,10) preserve these assignments.
Example 2
points = [[0],[4],[2]]k = 2rounds = 1return = [0,1,0]On the single assignment pass, point 2 is equally distant from centroids 0 and 4. The smaller cluster index wins, so it joins cluster 0.
Constraints
- 1 <= points.length <= 100
- Each point has 1 to 5 coordinates.
- -100 <= points[i][j] <= 100
- 1 <= k <= 10
- k <= points.length
- 1 <= rounds <= 50
- All points have the same dimension.
More Apple Phone Screen questions
- Subarray Product Less Than KPHONE SCREEN · Seen Nov 2026
- Evaluate DivisionPHONE SCREEN · Seen Nov 2026
- Reverse a Linked ListPHONE SCREEN · Seen Nov 2026
- Validate a BST with a Custom ComparisonPHONE SCREEN · Seen Nov 2026
- Design a Food Rating SystemPHONE SCREEN · Seen Oct 2026
- Days Until Poisoned Plants StabilizePHONE SCREEN · Seen Oct 2026
- Capture Surrounded Regions with Union-FindPHONE SCREEN · Seen Oct 2026
- Maintain a Consistent-Hashing RingPHONE SCREEN · Seen Oct 2026
- Count Nodes in a ChainPHONE SCREEN · Seen Oct 2026
- Run-Length DecodingPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Deterministic K-Means AssignmentsLyft · PHONE SCREENLyft interview questions
- Online Chess Move ValidationOpenAI · PHONE SCREENOpenAI interview questions
- Deterministic K-Means AssignmentsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Knockout Tournament Win ProbabilityGoogle · PHONE SCREENGoogle interview questions
- Scaled Dot-Product AttentionAmazon · PHONE SCREEN
- Deterministic K-Means AssignmentsMicrosoft · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- Automation Pipeline, Part 1: Single WorkerPlaid · PHONE SCREENPlaid interview questions
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Apply Affine Array TransformationsByteDance · PHONE SCREENByteDance interview questions
- Exponential Backoff DelaysWonderful · PHONE SCREEN
Apple interview experiences
- Apple SWE Phone Screen: Subarray Products: 1 Experience
- Apple New Grad SWE Java, Coding and Manager Rounds: 1 Experience
- Apple AI Coding and Related Interviews: 17 Experiences
- Apple India SWE New Grad Interviews: 5 Experiences
- Apple New Grad SWE Phone Screens: 12 Experiences (Part 3 of 3)
- Apple New Grad SWE and Embedded: 16 Experiences (Part 2 of 3)