Coding interview: Implement a mutable range module

Prompt and scope

Implement three operations over half-open intervals [left, right): add coverage, test whether a query is fully covered, and remove coverage. Assume 1 <= left < right <= 10^9 and up to 10^4 calls, matching the public Range Module problem. State what happens when left >= right if your API accepts defensive input.

What the interviewer is testing

The core test is whether you can choose and preserve a data-structure invariant while intervals are inserted, deleted, and queried. The expected representation is a sorted canonical collection of disjoint intervals; LeetCode lists an ordered set and segment tree as relevant approaches. Magicsheet labels the problem hard and tags ordered sets and segment trees. The question also exposes half-open boundary discipline, iterator safety, and complexity accounting.

Clarifying questions to ask

1. Are endpoints inclusive? This answer uses [left, right).
2. Should touching ranges such as [1,3) and [3,5) be merged? This answer merges them into one canonical interval.
3. Are all endpoints known before execution? The base design is online, so they are not.
4. What should invalid left >= right input do? Return without changing state, or reject it explicitly.
5. Is the domain bounded and static enough to justify a segment tree? That affects the alternative design.

Step-by-step solution

1. Choose the representation and invariant

Use an ordered map from interval start to end. std::map keeps keys sorted and documents logarithmic search, insertion, and removal; ascending iteration lets the algorithm walk only nearby intervals. Normalize touching coverage, so after every operation the map contains no pair with previousEnd >= nextStart.

2. Add coverage

Start at the first interval whose end is at least left (or the first interval after the predecessor). While the current start is at most the growing right, expand left and right to include that interval, then mark it for erasure. Erase the marked contiguous range and insert the merged interval. Empty state and a range disjoint from both neighbors need no special structure.

3. Remove coverage and query coverage

For removal, visit intervals with start < right and end > left. For each overlap, retain [oldStart,left) when oldStart < left, and retain [right,oldEnd) when right < oldEnd; erase the original before inserting fragments. For a query, inspect the interval whose start is the greatest start not exceeding left; return true only if it exists and its end is at least right. With half-open endpoints, [1,3) does not cover [3,4).

Correctness and complexity

The invariant proves correctness by induction. Adding replaces every interval connected to the new range with their union, so no covered point is lost and the result is canonical. Removing replaces each overlap with exactly the portions outside the removed range. Querying the predecessor is sufficient because sorted disjoint intervals make any earlier interval end no later, and any later interval start greater than left cannot contain left.

Let n be the number of stored intervals and k the number touched by an update. A query is O(log n). An update performs O(log n) searches plus O(k) iterator traversal and erasure; implementations that re-search every key can instead be O(k log n). Space is O(n). A segment tree is reasonable for a known bounded coordinate universe, while coordinate compression requires all endpoints offline and is unsuitable for arbitrary online calls.

Model answer

“I would implement a normalized ordered map of half-open, sorted, disjoint intervals. Add locates and merges every overlapping or touching interval, remove deletes overlaps and keeps at most two boundary fragments, and query checks the predecessor of the requested start. The key proof obligation is that each operation preserves the canonical union. Query costs O(log n); an update costs O(log n + k) when erasing a contiguous iterator range and uses O(n) space. I would compare this online map with a segment tree only after confirming the coordinate domain and whether all endpoints are known.”

Common mistakes

• Treating endpoints as closed → adjacent ranges appear to overlap incorrectly → define [left,right) first.
• Leaving touching intervals separate → later queries and updates encounter avoidable duplicates → normalize adjacency.
• Removing while incrementing an invalidated iterator → skips nodes or accesses freed storage → save the next iterator or erase a known range.
• Splitting without preserving both sides → coverage disappears on one boundary → test middle removal and full containment.
• Claiming every update is O(log n) → one operation may touch many intervals → include k in the bound.
• Using coordinate compression online → unseen endpoints invalidate indices → use an ordered structure or rebuild from a complete offline set.

Follow-ups and extensions

Which boundary cases must be tested?

Test an empty module, repeated adds, a query exactly at an end, touching adds [1,3) then [3,5), removal of a middle slice, removal covering an entire interval, no-overlap removal, nested ranges, and endpoints 0 and 10^9 when the API permits them.

How would you test the invariant?

After every randomized operation, assert sorted starts, end > start, and previousEnd < nextStart. Compare query results against a small boolean array or a brute-force union model on a tiny coordinate domain. This catches off-by-one and fragment-loss bugs.

When would a segment tree win?

Choose a segment tree when the coordinate universe is bounded or compressible and range aggregation or lazy propagation matters. It gives predictable logarithmic operations but adds node and lazy-state complexity; the ordered map is simpler for sparse, online intervals.