Range Module

Range Module

What is this problem about?

The Range Module problem asks you to design a module that tracks which ranges of real numbers are currently being monitored. It supports three operations: add a range, remove a range, and query whether a range is fully tracked. This hard design coding problem uses an ordered set of intervals with merging. The design, ordered set, and segment tree interview pattern is the core.

Why is this asked in interviews?

Meta, Amazon, Coupang, and Google ask this because it's a real-world interval management problem — tracking monitored IP ranges, time intervals, or network segments. The ordered set approach with interval merging is the standard solution.

Algorithmic pattern used

Sorted map of non-overlapping intervals. Maintain intervals in a sorted ordered map. addRange(l, r): find all overlapping intervals, merge with [l, r] into one. removeRange(l, r): split intervals that overlap with [l, r], remove the overlapping portion. queryRange(l, r): check if the entire [l, r] is covered by a single stored interval.

Example explanation

Initially empty. addRange(3,8): intervals={(3,8)}. addRange(6,10): merge with (3,8) → intervals={(3,10)}. queryRange(2,6): is [2,6] fully in (3,10)? No (2<3). Return false. queryRange(5,9): [5,9] ⊆ [3,10] ✓. Return true. removeRange(5,7): split (3,10) → {(3,5),(7,10)}.

Common mistakes candidates make

• Not merging overlapping intervals on add.
• Not correctly splitting intervals on remove (must keep partial overlaps as new intervals).
• Off-by-one at boundaries (ranges are half-open [l, r) in some formulations).
• Using a list instead of sorted map (O(n) per operation instead of O(log n)).

Interview preparation tip

Range Module is one of the hardest interval management problems. The key operations — merge on add, split on remove — require careful boundary handling with the sorted map. Practice interval problems in order of complexity: Merge Intervals → Insert Interval → Range Module. The sorted map approach is O(log n + k) per operation where k = intervals affected.