Determine Complete Interval Coverage
WaymoSite Reliability Engineer · Technical ScreenLast updated
This question evaluates understanding of interval coverage, streaming or online algorithms, and data structures for maintaining dynamic unions of intervals as points arrive.
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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.