Quick Overview

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.

Implement K-Means and Detect Divisible Subarrays

Company: Microsoft

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Quick Answer: 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.

Part 1: Implement K-Means Clustering

Implement Lloyd's K-means clustering algorithm for a list of points. Use the first k points as the initial centroids. In each iteration, assign every point to the nearest centroid using squared Euclidean distance; if two centroids are tied, choose the smaller centroid index. Then recompute each centroid as the coordinate-wise mean of the points assigned to it. If a cluster becomes empty, keep its centroid unchanged for that iteration. Stop early when every centroid moves by at most tolerance in Euclidean distance, or after max_iterations iterations. After finishing, compute assignments one final time using the final centroids and return them. If max_iterations is 0, return the initial centroids and their assignments.

Constraints

  • 1 <= n <= 500
  • 1 <= d <= 20
  • 1 <= k <= n
  • 0 <= max_iterations <= 100
  • 0.0 <= tolerance
  • All points have the same dimension

Examples

Input: ([[0, 0], [0, 2], [10, 10], [10, 12]], 2, 10, 0.0)

Expected Output: ([[0.0, 1.0], [10.0, 11.0]], [0, 0, 1, 1])

Explanation: After a few iterations, the first two points form one cluster and the last two form the other.

Input: ([[0], [2], [1]], 2, 10, 0.0)

Expected Output: ([[0.5], [2.0]], [0, 1, 0])

Explanation: Point [1] is initially tied between the two centroids and must choose the smaller index.

Hints

  1. Write one helper to assign points to centroids, and another step to average points inside each cluster.
  2. When a cluster gets no points, do not move that centroid for that iteration.

Part 2: 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. Aim for an O(n) solution.

Constraints

  • 1 <= len(nums) <= 100000
  • 0 <= nums[i] <= 1000000000
  • 1 <= k <= 1000000000

Examples

Input: ([23, 2, 4, 6, 7], 6)

Expected Output: True

Explanation: The subarray [2, 4] sums to 6, which is divisible by 6.

Input: ([23, 2, 6, 4, 7], 13)

Expected Output: False

Explanation: No contiguous subarray of length at least 2 has sum divisible by 13.

Hints

  1. If two prefix sums have the same remainder modulo k, the sum between them is divisible by k.
  2. Store the earliest index where each remainder appears so you can enforce subarray length at least 2.

Loading coding console...