Solution: Range Module
Let’s solve the Range Module problem using the Custom Data Structures pattern.
We'll cover the following
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
Implement the RangeModule class with the following specifications:
Constructor(): Initializes a new instance of the data structure.
Add Range(): Adds the half-open interval
to the ranges being tracked. If the interval overlaps with existing ranges, it should add only the numbers within that are not already being tracked. Query Range(): Returns true if every real number within the interval
is currently being tracked, and false otherwise. Remove Range(): Removes tracking for every real number within the half-open interval
.
Constraints:
left
right
At most,
calls will be made to Add Range(), Query Range(), and Remove Range().
Solution
Let’s look at the step-by-step implementation of the functions:
Add Range(left, right): This function adds a new interval
[left, right]
to the list of intervals, merging it with any overlapping intervals.If the new interval is completely outside the existing intervals:
Append the new interval to the end if it is to the right of all existing intervals.
Insert the new interval at the beginning if it is to the left of all existing intervals.
If the new interval overlaps with existing intervals:
Find the overlapping intervals using the
checkIntervals
method.Calculate the minimum start and maximum end of the overlapping intervals and the new interval to determine the new interval’s boundaries.
Replace the overlapping intervals with this newly merged interval to keep the list nonoverlapping.
Remove Range(left, right): This function removes a given interval
[left, right]
from the list of intervals, splitting any overlapping intervals as needed.Do nothing if no intervals exist or the removal range is outside the existing intervals.
Find the overlapping intervals using the
checkIntervals
method.For each overlapping interval:
If the interval starts before the removal range, create a new interval from the start to the beginning of the removal range.
If the interval ends after the removal range, create a new interval from the end of the removal range to the end of the interval.
Replace the overlapping intervals with the new ones excluding the removal range, keeping the list non-overlapping.
Query Range(left, right): This function checks if any of the existing intervals fully cover a given interval
[left, right]
.If there are no intervals, return FALSE.
Find the overlapping intervals using the
checkIntervals
method.Verify the start and end boundaries to check if the range
[left, right]
is fully contained within one of the identified intervals.
Check Intervals(left, right): This helper function identifies the indexes of intervals that overlap or touch a given interval
[left, right]
.Use a binary search-like approach with an initial mid-point
mid
that starts at half the array size.While
mid
is greater than or equal toIncrement
minRange
bymid
if the end of the interval atminRange + mid - 1
is less thanleft
.Decrement
maxRange
bymid
if the start of the interval atmaxRange - mid + 1
is greater thanright
.Halve
mid
to refine the search area.
Return the indexes
minRange
andmaxRange
that mark the boundaries of the overlapping intervals.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.