Design Interval Membership Queries with Linear, Logarithmic, and Constant-Time Options

## 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? ### What a Strong Answer Covers - Unsorted interval list with O(n) membership and cheap append under the non-overlap guarantee. - Sorted intervals with predecessor binary search and the cost of maintaining order. - A direct-address bitset or difference/prefix representation for bounded integers, with honest initialization and update costs. - Inclusive boundary correctness and safe size arithmetic. - A workload-based recommendation rather than presenting one asymptotic result as universally best. ### 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?