Minimize Max Distance to Gas Station

HardBinary Searchbinary search on answer

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Gas stations sit on a number line at the strictly increasing integer positions in stations. You must add exactly k new stations, and each new station may go at **any real position**, not just integers. After adding them, let penalty be the largest distance between two adjacent stations. Return the smallest possible penalty. Answers within 10^-6 of the true value are accepted.

Examples

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.5
Put one new station in the middle of each of the 9 gaps; every gap becomes 0.5.
Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1
Output: 14.0
The only gap longer than 14 is 65 to 84 (length 19); splitting it leaves 84 to 98 (length 14) as the largest gap.

Constraints

  • 2 <= stations.length <= 2000
  • 0 <= stations[i] <= 10^8
  • `stations` is strictly increasing
  • 1 <= k <= 10^6

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search on answer problems