Design Interval Membership Queries with Linear, Logarithmic, and Constant-Time Options
GoogleSoftware Engineer · Technical Screen
Last updated
Design interval membership with linear scans, predecessor binary search, or bounded-universe direct addressing, comparing insertion, memory, adjacency, inclusive boundaries, overflow safety, and workload fit.
Interview Prompt
Design a class with addNonOverlappingInterval(start, end) and contains(x).
Compare a straightforward O(n) query, an O(log n) query, and an O(1) query under
an explicitly bounded integer universe. Explain insertion cost, memory cost,
boundary semantics, overflow concerns, and which representation you would choose
for different workloads.
Constraints & Assumptions
- Intervals are closed and valid with
start <= end. - New intervals are guaranteed not to overlap existing intervals, but may be adjacent.
- For the constant-time option only, assume integer coordinates in a known finite domain.
- Do not claim O(1) memory for a bitset whose size depends on the coordinate universe.
Clarifying Questions to Ask
- Should adjacent intervals be merged?
- Are intervals added online, and how frequent are queries relative to inserts?
- What are the coordinate bounds and can an interval span nearly the whole domain?
Follow-up questions
- How would interval deletion change each design?
- What if intervals may overlap and must be merged on insertion?
- Can you obtain near-constant query time for a huge sparse universe without direct addressing?
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.