Interview Prepcustom-data-structureshardGoogleAmazon

Range Module (Add/Remove/Query Ranges)

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

</>

IDE

class RangeModule:
    def __init__(self):
        pass
    def addRange(self, left: int, right: int) -> None:
        pass
    def queryRange(self, left: int, right: int) -> bool:
        pass
    def removeRange(self, left: int, right: int) -> None:
        pass

class RangeModule:
    def __init__(self):
        # Write your solution here
        pass
    def addRange(self, left: int, right: int) -> None:
        pass
    def queryRange(self, left: int, right: int) -> bool:
        pass
    def removeRange(self, left: int, right: int) -> None:
        pass

class RangeModule {
    public RangeModule() {
        // Write your solution here
    }
    public void addRange(int left, int right) {
    }
    public boolean queryRange(int left, int right) {
        return false;
    }
    public void removeRange(int left, int right) {
    }
}

#include <vector>
using namespace std;

class RangeModule {
public:
    RangeModule() {
        // Write your solution here
    }
    void addRange(int left, int right) {
    }
    bool queryRange(int left, int right) {
        return false;
    }
    void removeRange(int left, int right) {
    }
};

class RangeModule {
    constructor() {
        // Write your solution here
    }
    addRange(left, right) {
    }
    queryRange(left, right) {
        return false;
    }
    removeRange(left, right) {
    }
}

0/10

Common Bugs to Avoid

Wrong: queryRange returns false for a range fully covered by merged intervalsIntervals are not merged correctly on addRange, leaving gaps between intervals.✅ Merge intervals by expanding boundaries when overlapping or adjacent: dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w-wt[i-1]])

Wrong: queryRange returns true for a range partially removedremoveRange does not split intervals properly, leaving removed parts still tracked.✅ Split intervals at removal boundaries and remove only overlapping parts.

Wrong: queryRange returns true when no intervals existEmpty intervals list not handled; queryRange returns true by default or errors.✅ Return false if intervals list is empty or no interval covers the query range.

Wrong: TLE on large inputsLinear scan of intervals for each operation causing O(n) per call.✅ Use balanced tree or binary search to achieve O(log n) per operation.

✓

Test Cases

t1_01basic

Input["addRange(10, 20)","removeRange(14, 16)","queryRange(10, 14)","queryRange(13, 15)","queryRange(16, 17)"]

Expected["null","null","true","false","true"]

After adding [10,20), removing [14,16) splits the range into [10,14) and [16,20). Querying [10,14) returns true, [13,15) returns false because 14-15 is removed, and [16,17) returns true.

t1_02basic

Input["addRange(5, 10)","addRange(15, 20)","removeRange(7, 17)","queryRange(5, 7)","queryRange(10, 15)","queryRange(17, 20)"]

Expected["null","null","null","true","false","true"]

After adding [5,10) and [15,20), removing [7,17) removes [7,10) and [15,17). Querying [5,7) returns true, [10,15) returns false (gap), and [17,20) returns true.

Practice

(1/5)

1. You need to design a data structure that supports fast search, insertion, and deletion of integers, with average logarithmic time complexity. The structure should maintain multiple levels of linked lists with probabilistic promotion of nodes to higher levels. Which approach best fits this requirement?

easy

A. A multi-level linked list with randomized node promotion (Skiplist)

B. A hash table with chaining for collision resolution

C. A balanced binary search tree like AVL or Red-Black Tree

D. A simple sorted singly linked list with linear search

2. Given the following code snippet for the optimal Twitter design, what is the output of getNewsFeed(1) after these operations?

twitter = Twitter()
twitter.postTweet(1, 5)
twitter.postTweet(2, 6)
twitter.followees[1] = {2}
print(twitter.getNewsFeed(1))

Assume getNewsFeed returns a list of tweetIds sorted from most recent to oldest.

easy

A. [6]

B. [5, 6]

C. [5]

D. [6, 5]

4. Examine the following buggy remove method from the optimized Insert Delete GetRandom O(1) with duplicates data structure. Which line contains the subtle bug that can cause incorrect behavior or runtime errors?

def remove(self, val: int) -> bool:
    if val not in self.idx_map or not self.idx_map[val]:
        return false
    remove_idx = self.idx_map[val].pop()
    last_val = self.nums[-1]
    self.nums[remove_idx] = last_val
    self.idx_map[last_val].add(remove_idx)
    # BUG: missing discard of old index for last_val
    self.nums.pop()
    if not self.idx_map[val]:
        del self.idx_map[val]
    return true

medium

A. Missing line to discard old index of last_val from idx_map[last_val]

B. Line adding remove_idx to idx_map[last_val] (self.idx_map[last_val].add(remove_idx))

C. Line popping remove_idx from idx_map[val] (remove_idx = self.idx_map[val].pop())

D. Line removing the last element from nums (self.nums.pop())

Range Module (Add/Remove/Query Ranges)

Start learning this pattern below

Practice

Solution

Step 1: Identify the need for probabilistic multi-level structure

Step 2: Match with known data structures

Final Answer:

Quick Check:

Solution

Step 1: Trace postTweet calls

Step 2: Trace getNewsFeed(1)

Final Answer:

Quick Check:

Solution

Step 1: Understand the eviction criteria

Step 2: Identify data structures supporting O(1) operations

Final Answer:

Quick Check:

Solution

Step 1: Understand index updates during removal

Step 2: Identify missing discard

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse impact

Step 2: Modify increment tracking

Final Answer:

Quick Check: