Katkat
Back

Implement a Half-Open Interval Range Module

AmazonSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests proficiency with balanced binary search trees or interval management techniques to efficiently track and manipulate sets of half-open intervals.

Problem Statement

Design a RangeModule class that tracks a set of half-open intervals [left, right), where left is inclusive and right is exclusive. Your module must support the following three operations:

  1. addRange(left, right): Adds the half-open interval [left, right), tracking every real number in that interval. If an interval overlaps with existing tracked intervals, they should be merged into a single continuous interval.
  2. queryRange(left, right): Returns true if and only if every real number in the interval [left, right) is currently being tracked, and false otherwise.
  3. removeRange(left, right): Stops tracking every real number currently being tracked in the interval [left, right). This may split existing intervals into smaller ones.

Constraints

  • 0 <= left < right <= 10^9
  • Up to 20,000 calls to addRange, queryRange, and removeRange.

Examples

# Example usage:
rm = RangeModule()
rm.addRange(10, 20)
rm.removeRange(14, 16)
print(rm.queryRange(10, 14)) # Output: True
print(rm.queryRange(13, 15)) # Output: False
print(rm.queryRange(16, 17)) # Output: True

Edge Cases

  • Operations on intervals that partially overlap with multiple existing intervals.
  • Adding or removing intervals that completely cover or are completely covered by existing ones.
  • Operations that result in no change to the current set of intervals.

Hints

Hint 1

Consider using a data structure that maintains sorted keys, such as a balanced binary search tree or a sorted list, to store the start and end points of intervals.

Hint 2

For 'addRange', identify all existing intervals that overlap with the new range, merge them into one, and update the collection accordingly.

Hint 3

For 'queryRange', use binary search to locate the specific interval that would contain the requested range and check for full coverage.

Follow-up questions

  • How would the implementation change if we were dealing with closed intervals [left, right] instead of half-open intervals?
  • Can you analyze the time complexity of your operations in terms of N, the number of currently tracked disjoint intervals?
  • If the number of operations were increased to 10^7, how would you optimize the memory usage or the speed of your data structure?