Katkat
Back

Implement one-cluster k-means

SealthMachine Learning Engineer · Onsite
EasyMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to implement a one-cluster k-means algorithm (finding the geometric centroid) and understanding of the mathematical property that minimizes sum of squared errors.

Problem Statement

In k-means clustering, the goal is to partition data into k clusters such that the within-cluster sum of squares (WCSS) is minimized. For the special case where k = 1, the problem simplifies to finding a single point (the centroid) that minimizes the sum of squared Euclidean distances to all other points in a dataset.

Given a list of d-dimensional points, implement a function find_one_cluster_centroid(points) that returns the optimal centroid. The input is a list of lists, where points[i] represents the coordinates of the i-th point.

Constraints

  • n (number of points) is between 1 and 10^5.
  • d (dimensionality) is between 1 and 100.
  • Coordinates are floating-point numbers.

Example 1

Input:

points = [[1.0, 2.0], [3.0, 4.0], [5.0, 6.0]]

Output:

[3.0, 4.0]

Explanation: The mean of the x-coordinates is (1+3+5)/3 = 3, and the mean of the y-coordinates is (2+4+6)/3 = 4.

Example 2

Input:

points = [[0.0, 0.0, 0.0]]

Output:

[0.0, 0.0, 0.0]

Implementation Signature

def find_one_cluster_centroid(points: list[list[float]]) -> list[float]:
    # Your code here

Hints

Hint 1

Recall that the centroid of a set of points in Euclidean space is simply the arithmetic mean of their coordinates.

Hint 2

The arithmetic mean is computed independently for each dimension across all points.

Hint 3

Ensure your code handles cases where the input list contains only one point or multiple points with zero values.

Follow-up questions

  • How does the computational complexity change if the number of points (n) is much larger than the memory available in RAM?
  • If we wanted to find the point in the dataset that minimizes the sum of absolute differences instead of squared differences (the geometric median), how would the implementation change?
  • How would you adapt this implementation to be an online algorithm that processes points one-by-one as they arrive?