##### Scenario You have a one-dimensional data set and want to compress it by choosing k representative points while guaranteeing every data point stays close to some representative. ##### Question Given an array of n integers and an integer k, place k cluster centers to minimize the maximum L1 distance between any point and its nearest center. Output this minimum possible distance. ##### Hints Consider sorting, binary searching the radius, and greedy or DP feasibility checks.

Atlassian machine learning and algorithms prompt on one-dimensional k-center clustering with L1 distance, covering sorting, binary search on radius, greedy feasibility, interval covering, precision, and complexity.

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.

What difficulty level is this interview question?

This is a medium difficulty Machine Learning question, commonly asked during Technical Screen rounds at Atlassian.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Atlassian during technical interviews.

Minimize L1 Distance with k Cluster Centers in Array

One-Dimensional k-Center Clustering With L1 Distance

You are given an array of n integers on a number line and an integer k, where 1 <= k <= n. Place k cluster centers on the real line to minimize the maximum L1 distance between any point and its nearest center.

Return the minimum possible maximum distance, also called the optimal radius.

Constraints & Assumptions

Distance is absolute difference: |x - c| .
Centers may be placed anywhere on the real line, not necessarily at input points.
Duplicate input points are allowed.
If the optimal radius is a half-integer and an integer answer is required, state how you would handle precision or scale coordinates by 2.

Clarifying Questions to Ask Guidance

Should the result be an exact integer, a floating-point radius, or a scaled integer?
Are centers required to be input points?
What are the constraints on n , coordinate range, and k ?
Do we need to return the centers or only the minimum radius?

What a Strong Answer Covers Guidance

Sort the points first.
Convert the problem to covering sorted points with at most k intervals of length 2R .
Use binary search on radius R .
Use a greedy feasibility check: start at the leftmost uncovered point p , place a center at p + R , cover all points up to p + 2R , and repeat.
Explain why greedy is optimal for a fixed radius in one dimension.
Analyze complexity, typically O(n log range) for binary search with greedy feasibility.
Discuss floating precision versus integer scaling, duplicates, and edge cases such as k >= n .

Follow-up Questions Guidance

How would the solution change if centers must be selected from input points?
Can you solve the sum of L1 distances variant with dynamic programming?
What happens when k = 1 ?
How would you reconstruct the chosen centers?

One-Dimensional k-Center Clustering With L1 Distance

Return the minimum possible maximum distance, also called the optimal radius.

Constraints & Assumptions

Distance is absolute difference: |x - c| .

Centers may be placed anywhere on the real line, not necessarily at input points.

Duplicate input points are allowed.

If the optimal radius is a half-integer and an integer answer is required, state how you would handle precision or scale coordinates by 2.

Clarifying Questions to Ask Guidance

Should the result be an exact integer, a floating-point radius, or a scaled integer?

Are centers required to be input points?

What are the constraints on n , coordinate range, and k ?

Do we need to return the centers or only the minimum radius?

What a Strong Answer Covers Guidance

Sort the points first.

Convert the problem to covering sorted points with at most k intervals of length 2R .

Use binary search on radius R .

Use a greedy feasibility check: start at the leftmost uncovered point p , place a center at p + R , cover all points up to p + 2R , and repeat.

Explain why greedy is optimal for a fixed radius in one dimension.

Analyze complexity, typically O(n log range) for binary search with greedy feasibility.

Discuss floating precision versus integer scaling, duplicates, and edge cases such as k >= n .

Follow-up Questions Guidance

How would the solution change if centers must be selected from input points?

Can you solve the sum of L1 distances variant with dynamic programming?

What happens when k = 1 ?

How would you reconstruct the chosen centers?

Minimize L1 Distance with k Cluster Centers in Array

Quick Overview

Minimize L1 Distance with k Cluster Centers in Array

One-Dimensional k-Center Clustering With L1 Distance

Constraints & Assumptions

Clarifying Questions to Ask Guidance

What a Strong Answer Covers Guidance

Follow-up Questions Guidance

Write your answer

Minimize L1 Distance with k Cluster Centers in Array

Quick Overview

Minimize L1 Distance with k Cluster Centers in Array

One-Dimensional k-Center Clustering With L1 Distance

Constraints & Assumptions

Clarifying Questions to Ask Guidance

What a Strong Answer Covers Guidance

Follow-up Questions Guidance

Write your answer