Katkat
Back

Implement K-Means and Detect Divisible Subarrays

MicrosoftMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to implement an iterative clustering algorithm (K-means) and to reason about subarray sums modulo k, testing competencies in numerical computation, centroid management, edge-case handling, and efficient algorithm design.

Solve both coding tasks.

Part A: Implement K-Means Clustering

Implement K-means clustering for a set of points.

Given:

  • points: a list of n points, where each point is a list of d numeric coordinates.
  • k: the number of clusters.
  • max_iterations: the maximum number of Lloyd iterations to run.
  • tolerance: stop early if every centroid moves by at most this Euclidean distance.

Use the first k points as the initial centroids. In each iteration:

  1. Assign every point to the nearest centroid using squared Euclidean distance. Break ties by choosing the smallest centroid index.
  2. Recompute each centroid as the coordinate-wise mean of the points assigned to it.
  3. If a cluster becomes empty, keep its centroid unchanged for that iteration.

Return the final centroid coordinates and the cluster assignment for each input point.

Discuss edge cases such as invalid k, duplicate points, empty clusters, and convergence.

Part B: Detect a Divisible-Sum Subarray

Given an integer array nums and a positive integer k, return true if there exists a contiguous subarray of length at least 2 whose sum is divisible by k. Otherwise return false.

A sum is divisible by k if sum % k == 0.

Example:

  • Input: nums = [23, 2, 4, 6, 7], k = 6
  • Output: true
  • Explanation: The subarray [2, 4] has sum 6, which is divisible by 6.

Constraints:

  • 1 <= nums.length <= 100000
  • 0 <= nums[i] <= 1000000000
  • 1 <= k <= 1000000000

Aim for an O(n) solution.