Interval Speed Limit: Find All Road Intervals Where a Vehicle Exceeds the Speed Limit
Interview Experience
Problem
A road is divided into segments, each with a posted speed limit. A vehicle's speed is measured at discrete distance intervals. Find all road intervals (as [start_km, end_km] pairs) where the measured speed exceeds the speed limit for that segment. Merge adjacent or overlapping violations into single intervals.
python
def speed_violations(
speed_limits: list[tuple[float, float, float]], # (start_km, end_km, limit_kph)
measurements: list[tuple[float, float]] # (position_km, speed_kph)
) -> list[tuple[float, float]]:
**Returns** list of [start, end] violation intervals
pass
Example:
speed_limits = [(0, 10, 80), (10, 20, 100)]
measurements = [(2, 95), (5, 85), (9, 75), (12, 110), (15, 105)]
-> [(2.0, 5.0), (12.0, 15.0)]
# position 2 and 5 exceed limit 80; 9 does not; 12 and 15 exceed 100
Follow-ups
- How do you assign each measurement to the correct speed-limit segment efficiently (binary search vs. interval tree)?
- How would you interpolate between measurement points to estimate the exact position where speed crossed the limit?
- What is the time complexity of your merging step, and can it be done in O(n) if inputs are already sorted?
- How would you adapt this for average-speed cameras that compute average speed between two fixed points?
Full Details
Problem
A road is divided into segments, each with a posted speed limit. A vehicle's speed is measured at discrete distance intervals. Find all road intervals (as [start_km, end_km] pairs) where the measured speed exceeds the speed limit for that segment. Merge adjacent or overlapping violations into single intervals.
python
def speed_violations(
speed_limits: list[tuple[float, float, float]], # (start_km, end_km, limit_kph)
measurements: list[tuple[float, float]] # (position_km, speed_kph)
) -> list[tuple[float, float]]:
**Returns** list of [start, end] violation intervals
pass
Example:
speed_limits = [(0, 10, 80), (10, 20, 100)]
measurements = [(2, 95), (5, 85), (9, 75), (12, 110), (15, 105)]
-> [(2.0, 5.0), (12.0, 15.0)]
# position 2 and 5 exceed limit 80; 9 does not; 12 and 15 exceed 100
Follow-ups
- How do you assign each measurement to the correct speed-limit segment efficiently (binary search vs. interval tree)?
- How would you interpolate between measurement points to estimate the exact position where speed crossed the limit?
- What is the time complexity of your merging step, and can it be done in O(n) if inputs are already sorted?
- How would you adapt this for average-speed cameras that compute average speed between two fixed points?
About This Question
This is a candidate experience report from a nuro interview during the phone round.
It covers the following topics: Coding, Phone, Onsite, Binary Search .