K-Means Clustering

Problem Overview

• Determine the minimized maximum distance from any data point to its nearest cluster center by optimally placing k centers in a 1D feature space.
• Input: location[n] and k; Output: an integer minimized max distance; Constraints: 1 ≤ n ≤ 1e5, 1 ≤ k ≤ n, 1 ≤ location[i] ≤ 1e9.
• Domain: k-means clustering quality in one dimension using absolute distance |x−y|.
• From Atlassian interviews; a coding interview problem and common interview question on clustering and optimization.