Implement a Range Module with Add, Query, and Remove

Question

The question asks the candidate to implement a Range Module that supports adding, querying, and removing ranges of integers efficiently.

Codemia · Accepted Answer

To implement a Range Module, we need to efficiently manage ranges of integers. The operations we need to support are adding a range, querying if a number is within any range, and removing a range. A good approach is to use a data structure that allows us to manage intervals, such as a list or a balanced binary search tree. We can use a list to store the ranges as pairs of start and end points. For the `addRange` method, we will merge overlapping intervals. The `queryRange` method will check if a number falls within any of the stored intervals. The `removeRange` method will split intervals as needed. Here is a simple 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 queryRange(self, left: int, right: int) -> bool: for start, end in self.intervals: if start <= left < end: return True return False def removeRange(self, left: int, right: int) -> None: new_intervals = [] for start, end in self.intervals: if end <= left or start >= right: new_intervals.append((start, end)) else: if start < left: new_intervals.append((start, left)) if end > right: new_intervals.append((right, end)) self.intervals = new_intervals ``` The time complexity for the `addRange` and `removeRange` methods is O(n) in the worst case, where n is the number of intervals, as we may need to iterate through all intervals. The `queryRange` method has a time complexity of O(n) as well. The space complexity is O(n) for storing the intervals. It is important to handle edge cases such as adding a range that is completely within an existing range, or removing a range that does not exist. Additionally, we should consider what happens when ranges are added in a non-sorted order. Interviewers are looking for clarity in explaining the thought process and the ability to reason about the efficiency of the solution. They appreciate candidates who can identify edge cases and articulate their handling, as well as those who can write clean and efficient code.

Implement a Range Module with Add, Query, and Remove

Walmart Labs

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

Walmart Labs 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