Implement a Half-Open Interval Range Module

Question

Implement a data structure that manages a half-open interval range, allowing for adding and removing intervals, as well as querying whether a number is within any of the stored intervals.

Codemia · Accepted Answer

To implement a Half-Open Interval Range Module, we can use a list to store the intervals in a sorted manner. This allows us to efficiently add, remove, and query intervals. The key operations will involve merging overlapping intervals when adding, and ensuring we maintain the sorted order for efficient querying. The main operations can be defined as follows: 1. **Add Interval**: Iterate through the existing intervals to find the correct position to insert the new interval, merging any overlapping intervals in the process. 2. **Remove Interval**: Similar to adding, but we will split intervals if the removal range overlaps. 3. **Query**: Check if a number lies within any of the stored intervals using binary search for efficiency. Here is a sample implementation in Python: ```python class RangeModule: def __init__(self): self.intervals = [] def addRange(self, left: int, right: int) -> None: new_intervals = [] i = 0 while i < len(self.intervals) and self.intervals[i][1] < left: new_intervals.append(self.intervals[i]) i += 1 while i < len(self.intervals) and self.intervals[i][0] <= right: left = min(left, self.intervals[i][0]) right = max(right, self.intervals[i][1]) i += 1 new_intervals.append((left, right)) new_intervals.extend(self.intervals[i:]) self.intervals = new_intervals def query(self, point: int) -> bool: left, right = 0, len(self.intervals) - 1 while left <= right: mid = (left + right) // 2 if self.intervals[mid][0] <= point < self.intervals[mid][1]: return True elif self.intervals[mid][1] <= point: left = mid + 1 else: right = mid - 1 return False def removeRange(self, left: int, right: int) -> None: new_intervals = [] for interval in self.intervals: if interval[1] <= left or interval[0] >= right: new_intervals.append(interval) else: if interval[0] < left: new_intervals.append((interval[0], left)) if interval[1] > right: new_intervals.append((right, interval[1])) self.intervals = new_intervals ``` The time complexity for adding an interval is O(n) in the worst case, where n is the number of intervals, due to the need to merge overlapping intervals. The space complexity is O(n) as well, since we may need to store a new list of intervals. Querying a point has a time complexity of O(log n) due to the binary search, while removing an interval also runs in O(n) in the worst case. It is important to consider edge cases such as: - Adding an interval that completely overlaps existing intervals. - Removing an interval that is entirely within another interval. - Querying points that are at the boundaries of intervals. Handling these cases correctly ensures that the module behaves as expected in all scenarios.

Implement a Half-Open Interval Range Module

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string