Problem
Ask
Submissions

Problem: Range Module

Medium
30 min
Explore how to build a Range Module data structure that tracks half-open intervals of numbers. Learn to add ranges without overlap, query full coverage within intervals, and remove ranges, preparing you for coding interview questions involving custom data structures.

Statement

Design a Range Module data structure that effectively tracks ranges of numbers using half-open intervals and allows querying these ranges. A half-open interval [left,right)[left, right) includes all real numbers nn where leftn<rightleft\leq n <right.

Implement the RangeModule class with the following specifications:

  • Constructor(): Initializes a new instance of the data structure.

  • Add Range(): Adds the half-open interval [left, right)[left,~right) to the ranges being tracked. If the interval overlaps with existing ranges, it should add only the numbers within [left, right)[left,~right) that are not already being tracked.

  • Query Range(): Returns true if every real number within the interval [left, right)[left,~right) is currently being tracked, and false otherwise.

  • Remove Range(): Removes tracking for every real number within the half-open interval [left, right)[left,~right).

Constraints:

  • 11 \leq left << right 104\leq 10^4

  • At most, 10310^3 calls will be made to Add Range(), Query Range(), and Remove Range().

Problem
Ask
Submissions

Problem: Range Module

Medium
30 min
Explore how to build a Range Module data structure that tracks half-open intervals of numbers. Learn to add ranges without overlap, query full coverage within intervals, and remove ranges, preparing you for coding interview questions involving custom data structures.

Statement

Design a Range Module data structure that effectively tracks ranges of numbers using half-open intervals and allows querying these ranges. A half-open interval [left,right)[left, right) includes all real numbers nn where leftn<rightleft\leq n <right.

Implement the RangeModule class with the following specifications:

  • Constructor(): Initializes a new instance of the data structure.

  • Add Range(): Adds the half-open interval [left, right)[left,~right) to the ranges being tracked. If the interval overlaps with existing ranges, it should add only the numbers within [left, right)[left,~right) that are not already being tracked.

  • Query Range(): Returns true if every real number within the interval [left, right)[left,~right) is currently being tracked, and false otherwise.

  • Remove Range(): Removes tracking for every real number within the half-open interval [left, right)[left,~right).

Constraints:

  • 11 \leq left << right 104\leq 10^4

  • At most, 10310^3 calls will be made to Add Range(), Query Range(), and Remove Range().