Implement K-means from first principles without numerical libraries, with fixed initialisation, tie handling, convergence rules and a policy for empty clusters.

def kmeans(points, init, max_iter=100, tol=1e-9):
    cents = [list(c) for c in init]
    for _ in range(max_iter):
        groups = [[] for _ in cents]
        for p in points:
            d = [sum((a - b) ** 2 for a, b in zip(p, c))
                 for c in cents]
            groups[d.index(min(d))].append(p)
        new = []
        for c, g in zip(cents, groups):
            if not g:
                new.append(c)
                continue
            n = len(g)
            new.append([sum(x) / n for x in zip(*g)])
        shift = max(sum((a - b) ** 2
                        for a, b in zip(c, m))
                    for c, m in zip(cents, new))
        cents = new
        if shift <= tol:
            break
    return cents, groups

State each rule before coding. Given initial centroids make runs deterministic. A tie goes to the lowest-index centroid, which taking the first minimum does. An empty cluster keeps its previous centroid; reseeding at the farthest point is the alternative. Stop when no centroid moves more than a tolerance, or at the iteration cap. Interviewers weigh these edge cases more than the loop.