Prompt and scope
Implement an interval set with add([l,r)), remove([l,r)), contains(x), and overlaps([l,r)). Adjacent or overlapping intervals should merge automatically, while removal may split an interval. Explain open and closed boundaries, empty ranges, and complexity.
This tests ordered collections, invariants, and boundary handling. Python’s bisect documentation says bisection finds an insertion point while list insertion may still be O(n). State the data-size assumption and whether a tree is needed instead of claiming every operation is O(log n).
What the interviewer is testing
First, can you fix half-open semantics and handle adjacency? Second, can insertion and removal scan only potentially intersecting neighbors instead of every interval? Third, can you choose an array, balanced tree, or interval tree from scale and prove the invariant?
Questions to clarify before answering
- Are intervals closed, open, or half-open? Assume
[l,r), so[0,1)and[1,2)do not intersect. - Are endpoints floating point? Assume comparable integers; define precision and NaN rules if not.
- Should adjacent intervals merge? Assume yes, to keep a normalized representation.
- What are scale and read/write mix? Small sets can use a sorted array; large sets may need a balanced or interval tree.
- What does removing a missing range do? Assume idempotent and retain only the portion that exists.
A 30-second answer framework
“I would use half-open intervals and keep them sorted, disjoint, and non-adjacent. add uses binary search to find the first possible intersection, then scans right to merge overlapping or adjacent entries. remove scans intersections and preserves non-empty left and right remainders. contains checks the predecessor interval; overlaps checks the first interval whose end exceeds the query start. An array has O(log n) search but O(n) shifts; for larger sets I would use a balanced or interval tree.”
Step-by-step deep dive
Step 1: Define the normalized invariant
Store sorted, disjoint, non-adjacent half-open intervals [l,r) with l < r; empty intervals never enter. After normalization, a point belongs to at most one interval, so updates can focus on local neighbors.
Step 2: Choose storage
For a few thousand intervals and light writes, a sorted array is simple and reliable; binary search locates a position while insertion and deletion shift elements. For high write and query volume, use an ordered-key balanced tree. Add an augmented interval tree only when coverage counts or maximum overlap depth are required.
Step 3: Locate insertion neighbors
Use bisect_left to find the first start not less than l, then inspect one predecessor because it may extend through l. Scan right while the next start is at most the current merged end; adjacent intervals are included in the merge.
add(l, r):
i = first index with start >= l, then i = max(0, i - 1)
while i < len(intervals) and intervals[i].end >= l:
l = min(l, intervals[i].start)
r = max(r, intervals[i].end)
delete intervals[i]
insert [l, r) at iStep 4: Implement removal and splitting
Find the first interval that may intersect [l,r) and process until the next start is at least r. For each interval, retain non-empty portions of [start,l) and [r,end). Because the input is normalized, removal does not create adjacent ranges that need another merge.
Step 5: Implement point and range queries
For contains(x), find the last interval with start <= x and check x < end. For overlaps([l,r)), find the first interval with end > l; it overlaps if start < r. An empty query range returns false. Every comparison follows half-open semantics.
Step 6: Prove correctness
The insertion loop removes only ranges that overlap or touch the new range and replaces their union with one interval, so coverage is preserved. Removal deletes only the intersection and keeps the two differences. Sorting and non-adjacency are restored after each operation, and each query needs only one candidate predecessor or successor.
Step 7: Analyze complexity
Array location is O(log n), but shifting and deleting merged entries can be O(n), where n is interval count. Scanning k neighboring intervals adds O(k). A balanced tree can provide O(log n + k) local updates with more implementation and memory cost. Do not confuse binary-search cost with complete-operation cost.
Step 8: Design boundary tests
Test an empty set, empty range, adjacent merge, full containment, partial overlap, spanning several intervals, middle deletion, endpoint deletion, negatives, repeated operations, and a large query range. Differential-test random operations against a pointwise boolean-array model.
Trade-offs and boundaries
Trade-off 1: Half-open or closed intervals
Half-open ranges compose naturally, have length r-l, and fit time and array-index use cases. A closed-interval business must consistently change adjacency, length, and integer-overflow rules; changing only comparison operators is unsafe.
Trade-off 2: Array or balanced tree
Arrays are short and cache-friendly for read-heavy, small-to-medium sets. Trees handle many insertions and deletions but require ordered keys and iterator-invalidation rules. Choose from actual n, write ratio, and latency budget.
Trade-off 3: Merge adjacent ranges or preserve provenance
Merging reduces entries and simplifies queries. If intervals represent permissions, reservations, or accounting periods whose original boundaries matter, retain source metadata or use a representation that does not discard segments.
Failure drills and evolution plan
Drill 1: Many adjacent inserts
Insert 10,000 adjacent intervals in reverse order. Verify one normalized interval remains with no missing endpoint, then measure array shifts to decide whether a tree is needed.
Drill 2: Random insertion and removal
Generate random add, remove, contains, and overlaps operations and compare with a pointwise model. Check especially that deleting the middle of one interval and later inserting correctly merges two sides.
Drill 3: Boundary and invalid input
Test l == r, l > r, very large integers, and NaN. Define whether empty ranges return, reversed ranges error or swap, and floating input is rejected.
Common mistakes and follow-ups
Mistake 1: Confusing adjacent and overlapping
Half-open [0,1) and [1,2) do not intersect, though a normalized set may still merge them. Define intersection and merge conditions separately.
Mistake 2: Checking only the right neighbor
The predecessor can cross the new left endpoint. Inspect one predecessor after binary search.
Mistake 3: Leaving empty intervals after removal
Filter every difference with start >= end, or contains can report a phantom hit.
Mistake 4: Claiming bisect makes insertion O(log n)
Python explicitly notes that list insertion shifts are O(n). State search, shift, and scan costs separately.
Mistake 5: Ignoring floating-point boundaries
NaN does not follow normal ordering, and approximate equality makes adjacency unstable. Define precision normalization before allowing floats.
Mistake 6: Dropping provenance
If intervals represent permissions, reservations, or accounting periods, a union can lose source meaning. Keep metadata or do not merge those segments.