Implement K-Means from Scratch | Dataford Interview Questions

Implement K-means without using numpy.

Asked in the virtual onsite (VO1) stage. Coding round; from the visible post text.

Implement kmeans(points, k, max_iters) using only Python's standard library. Initialize the first centroid with points[0], then repeatedly choose the unselected point farthest from its nearest selected centroid, breaking ties by original order. Assign each point to its nearest centroid, breaking distance ties in favor of the lower cluster index. Recompute centroids as coordinate-wise means. If a cluster is empty, keep its previous centroid. Stop when assignments no longer change or after max_iters iterations.

Return (centroids, labels), where centroids is a list of coordinate lists and labels[i] is the assigned cluster for points[i].

Constraints

1 <= k <= len(points)
1 <= max_iters <= 100
Each point has the same positive number of dimensions
Coordinates are finite numeric values
Initialization and assignment ties are resolved by original order and lower cluster index respectively

Function Signature

def kmeans(points, k, max_iters):

Your question is Implement K-Means from Scratch. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem