Determine Complete Interval Coverage
Company: Waymo
Role: Site Reliability Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You need to process a stream of real-valued points on a one-dimensional target segment from 0 to 50.
Each time a point `x` arrives, it contaminates the interval `[x - 0.5, x + 0.5]`. Contamination is permanent, and intervals from different points may overlap.
Design a function that receives one point at a time as a `double` and returns a `bool` indicating whether the entire target segment `[0, 50]` is fully contaminated after processing that point.
Notes:
- Points may arrive in any order.
- A point may be any real value; only its overlap with `[0, 50]` matters.
- You should support repeated updates efficiently.
Quick Answer: This question evaluates understanding of interval coverage, streaming or online algorithms, and data structures for maintaining dynamic unions of intervals as points arrive.
You process a stream of real-valued points on the one-dimensional target segment `[0, 50]`. Each arriving point `x` permanently contaminates the closed interval `[x - 0.5, x + 0.5]` (a length-1 region). Contamination never goes away, and the regions from different points may overlap.
Implement `solution(points)` which receives the full sequence of points (as a list of doubles, in arrival order) and returns a list of booleans of the same length: the i-th boolean is `true` if and only if the entire target segment `[0, 50]` is fully contaminated after the first `i+1` points have been processed.
**Notes**
- Points may arrive in any order.
- A point may be any real value; only the overlap of its interval with `[0, 50]` matters (points whose interval lies entirely outside `[0, 50]` change nothing).
- Updates should be supported efficiently (amortized near-constant time per point), so merging intervals as they arrive is preferred over rescanning everything each time.
In an interview this would be modeled as a stateful object whose update method takes one `double` and returns one `bool`; here the equivalent contract is a single function over the whole stream so the behavior after every point can be checked deterministically.
Constraints
- The target segment is fixed at [0, 50].
- Each point contaminates exactly the closed interval [x - 0.5, x + 0.5].
- Contamination is permanent and cumulative across all processed points.
- Points are real numbers (doubles) and may be negative or exceed 50.
- 0 <= number of points <= 10^6; the solution must support efficient incremental updates.
Examples
Input: ([0.5, 1.5, 2.5],)
Expected Output: [False, False, False]
Explanation: Three points cover [0,1], [1,2], and [2,3], so only [0,3] of the target [0,50] is contaminated after each arrival. The segment is never fully covered, so every answer is False.
Input: ([],)
Expected Output: []
Explanation: No points arrive, so no coverage status is produced.
Hints
- Maintain the union of contaminated regions as a set of disjoint, merged intervals kept sorted by start point rather than tracking every individual point.
- When a new interval [x-0.5, x+0.5] arrives, merge it with any existing intervals it overlaps or touches, then check whether the single interval that starts at (or before) 0 also reaches 50.
- The whole segment [0,50] is covered exactly when one merged interval has start <= 0 and end >= 50. Use a small epsilon for floating-point comparisons, and clip incoming intervals to [0,50] so points outside the target are naturally ignored.