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

Last updated: Mar 29, 2026

Quick Overview

This question evaluates understanding of clustering and metric-based optimization, focusing on L1 distance and interval covering in a one-dimensional setting and belongs to the Machine Learning and algorithms domain with a practical application focus on algorithm design and optimization.

Atlassian

Jul 12, 2025, 6:59 PM

Data Scientist

Technical Screen

Machine Learning

1D k-Center (Minimax L1) Clustering

Problem

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

Distance between a point x and a center c is |x − c|.
Centers may be placed anywhere on the real line (not necessarily at input points).
Output the minimum possible maximum distance (the optimal radius).

Goal

Return the optimal radius R* such that all points can be covered by k intervals of radius R* around the chosen centers, and no smaller radius suffices.

Notes

Think of this as covering all sorted points with k intervals of length 2R.
Typical approach: sort, binary search on R, and use a greedy feasibility check.
If you must return an integer and the true optimum is a half-integer, you can either output a floating value (e.g., with 1e-6 precision) or scale coordinates by 2 to keep everything integral.

Solution

Show

Submit Your Answer to Earn 20XP

Loading comments...

Browse More Questions

More Machine Learning•More Atlassian•More Data Scientist•Atlassian Data Scientist•Atlassian Machine Learning•Data Scientist Machine Learning