DSA interview question

Minimise the Maximum Distance to a Gas Station

Hard · Data structures · Topics: binary search on answer, array, heap

The problem

A highway authority has gas stations at sorted positions along a road and budget for K more. New stations can go anywhere, including at fractional positions. Where should they go so that the largest gap between neighbouring stations is as small as possible? The answer is a real number. Greedily splitting the currently largest gap works with a heap, but the cleaner technique is binary search on the real-valued answer. For a target gap d, each existing gap g needs ceil(g / d) − 1 new stations, and the target is feasible if the total is at most K.

Example: stations [1, 2, ..., 10], K = 9 → 0.5 (one new station in the middle of every gap).

Function signature

double minimiseMaxDistance(const vector<int>& stations, int k);  // sorted positions, answer within 1e-6

Test cases

Input `(stations, k)`	Output	Explanation
`([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 9)`	0.500000	Halve every gap of 1
`([23, 24, 36, 39, 46, 56, 57, 65, 84, 98], 1)`	14.000000	Split the 19-wide gap; the 14-wide gap remains the largest
`([1, 2], 1)`	0.500000
`([1, 13, 17, 23], 5)`	3.000000	The 12-gap takes 3 stations, the 4-gap 1, the 6-gap 1

(Confirm: stations are sorted and distinct; new stations can be placed at any real position; the answer is accepted within 10⁻⁶.)

How interviewers phrase it

"Minimise the maximum distance to a gas station" (LeetCode 774, Hard).
A test of binary search on real numbers, and of the heap-based greedy alternative.

Clarifying questions to ask

Can new stations go at fractional positions? (Yes.)
What precision is required?
Are the positions sorted?

Follow-ups to expect

"How many stations does a gap g need for a target d?"
"How do you binary-search on real numbers?"
"What's the heap approach?"
"Why can't you just split the largest gap in half each time?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview