Minimize max L1 radius with k centers in 1D

Q: Minimize max L1 radius with k centers in 1D

This is a Machine Learning interview question from Atlassian for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Machine Learning interview questions?

Machine Learning questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master machine learning interviews.

Question

You are given an array A of n integers (values may be negative and may repeat) and an integer k (1 ≤ k ≤ n). Place k cluster centers anywhere on the real line to minimize the maximum L1 distance (absolute value) from any data point to its nearest center. Return this minimized maximum distance r*. Design an algorithm faster than O(nk). Requirements: 1) Sort A and use a decision version that, for a candidate radius r, greedily covers points with intervals of length 2r to check if ≤ k centers suffice; then binary-search the smallest feasible r on [0, max(A)-min(A)]. Aim for O(n log R) time, where R is the search range, and O(1) extra space beyond the sorted array. 2) Output both r* and one valid set of k center positions achieving r*; centers may be any real numbers. 3) Prove correctness of the greedy feasibility test and the binary search, and argue why centers need not be restricted to data points to achieve the optimal r* (but also discuss whether restricting centers to data points changes r* in 1D under L1, and how the algorithm would adapt if such a restriction were imposed). 4) Handle large coordinates up to 1e9 and n up to 2e5; ensure numerical stability if r* is half-integer. 5) Provide worked examples, including duplicates and tightly clustered vs. widely separated points, and give exact r* values for those cases. Analyze time and space complexity.

Minimize max L1 radius with k centers in 1D

Comments (0)