Problem
Ask
Submissions

Problem: Range Module

Medium
30 min
Explore how to implement a Range Module data structure that manages ranges of numbers with half-open intervals. Understand how to add new ranges, query existing ranges, and remove ranges effectively. This lesson helps you build custom data structures for specialized problems while enhancing your coding interview pattern skills.

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 implement a Range Module data structure that manages ranges of numbers with half-open intervals. Understand how to add new ranges, query existing ranges, and remove ranges effectively. This lesson helps you build custom data structures for specialized problems while enhancing your coding interview pattern skills.

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().