## Problem You are given a sorted array of integer positions and an integer `k`. Choose exactly `k` positions from the array and minimize the maximum distance between any two consecutively chosen positions. ```python def minimize_max_distance(positions: list[int], k: int) -> int: pass ``` ``` Input: positions = [1, 3, 8, 12, 17], k = 3 Output: 7 # Choose positions 1, 8, 17 -> gaps are 7 and 9 -> max gap = 9... # Optimal: 1, 8, 15... wait, 15 not in array. # Optimal: 1, 8, 17 -> gaps 7, 9 -> answer 9? # OR: 3, 8, 17 -> gaps 5, 9 -> answer 9 # OR: 1, 8, 12 -> gaps 7, 4 -> answer 7 <-- optimal Input: positions = [0, 5, 9, 14], k = 2 Output: 14 ``` ## Follow-ups 1. Can you solve this with binary search on the answer? What predicate would you check? 2. What is your time complexity? Can you do better than O(n log n)? 3. If `k` equals the length of the array, what is the answer? 4. How would you reconstruct the actual chosen positions, not just the minimum max distance?

InterviewDB Question

Minimize Maximum Distance Between Chosen Points

phone

Question Details

Problem You are given a sorted array of integer positions and an integer k. Choose exactly k positions from the array and minimize the maximum distance between any two consecutively chosen positions. Follow-ups Can you solve this with binary search o…

Full Details

🔒

Unlock full leaked content

Full insider details, leaked discussions, and candidate experiences.

Get Premium →

Topics

Coding Mle Onsite Phone

Minimize Maximum Distance Between Chosen Points

Question Details

Full Details

Topics

More from LinkedIn