Bird
Raised Fist0
Interview PrepintervalshardGoogleAmazon

Data Stream as Disjoint Intervals

Choose your preparation mode4 modes available
</>
IDE
def addNum(self, val: int) -> None: def getIntervals(self) -> list:public void addNum(int val) public int[][] getIntervals()void addNum(int val) vector<vector<int>> getIntervals()function addNum(val) function getIntervals()
class SummaryRanges:
    def __init__(self):
        # Write your solution here
        pass
    def addNum(self, val: int) -> None:
        pass
    def getIntervals(self) -> list:
        pass
class SummaryRanges {
    public SummaryRanges() {
        // Write your solution here
    }
    public void addNum(int val) {
        // Write your solution here
    }
    public int[][] getIntervals() {
        // Write your solution here
        return new int[0][0];
    }
}
#include <vector>
using namespace std;

class SummaryRanges {
public:
    SummaryRanges() {
        // Write your solution here
    }
    void addNum(int val) {
        // Write your solution here
    }
    vector<vector<int>> getIntervals() {
        // Write your solution here
        return {};
    }
};
class SummaryRanges {
    constructor() {
        // Write your solution here
    }
    addNum(val) {
        // Write your solution here
    }
    getIntervals() {
        // Write your solution here
        return [];
    }
}
0/10
Common Bugs to Avoid
Wrong: [[1,3],[7,7]] instead of [[1,7]]Failed to merge intervals connected by multiple adjacent numbers.✅ Merge all intervals overlapping or adjacent to val, not just one side.
Wrong: [[1,1],[3,3],[7,7]] after adding 2Missing merge of intervals when new val bridges two intervals.✅ Check intervals before and after val and merge if val connects them.
Wrong: Intervals change after adding duplicatesNot checking for duplicates before adding val.✅ Skip adding val if it already exists in intervals.
Wrong: Intervals merged incorrectly including non-adjacent intervalsGreedy merging all intervals instead of only adjacent ones.✅ Merge only intervals adjacent to val, not all intervals.
Wrong: TLE on large inputUsing brute force or sorting all numbers on each getIntervals call.✅ Use balanced tree or sorted container with incremental merging on insert.
✓
Test Cases
t1_01basic
Input{"calls":[{"method":"addNum","args":[1]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[3]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[7]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[2]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[6]},{"method":"getIntervals","args":[]}]}
Expected[[[1,1]],[[1,1],[3,3]],[[1,1],[3,3],[7,7]],[[1,3],[7,7]],[[1,3],[6,7]]]

After adding 1, intervals are [[1,1]]. Adding 3 adds a new interval [[3,3]]. Adding 7 adds [[7,7]]. Adding 2 merges [1,1] and [3,3] into [1,3]. Adding 6 merges [6,6] and [7,7] into [6,7].

t1_02basic
Input{"calls":[{"method":"addNum","args":[5]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[10]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[6]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[8]},{"method":"getIntervals","args":[]},{"method":"addNum","args":[7]},{"method":"getIntervals","args":[]}]}
Expected[[[5,5]],[[5,5],[10,10]],[[5,6],[10,10]],[[5,6],[8,8],[10,10]],[[5,10]]]

Add 5 → [[5,5]]. Add 10 → [[5,5],[10,10]]. Add 6 merges with 5 → [[5,6],[10,10]]. Add 8 → [[5,6],[8,8],[10,10]]. Add 7 merges [5,6],[8,8],[10,10] into [[5,10]].

t2_01edge
Input{"calls":[{"method":"getIntervals","args":[]}]}
Expected[]

No numbers added, so intervals list is empty.

t2_02edge
Input{"calls":[{"method":"addNum","args":[100]},{"method":"getIntervals","args":[]}]}
Expected[[[100,100]]]

Single element added forms one interval [100,100].

t2_03edge
Input{"calls":[{"method":"addNum","args":[0]},{"method":"addNum","args":[1]},{"method":"addNum","args":[2]},{"method":"getIntervals","args":[]}]}
Expected[[[0,2]]]

Adding numbers 0,1,2 creates a continuous interval [0,2].

t2_04edge
Input{"calls":[{"method":"addNum","args":[5]},{"method":"addNum","args":[5]},{"method":"addNum","args":[5]},{"method":"getIntervals","args":[]}]}
Expected[[[5,5]]]

Adding the same number multiple times does not change intervals after first addition.

t3_01corner
Input{"calls":[{"method":"addNum","args":[1]},{"method":"addNum","args":[3]},{"method":"addNum","args":[5]},{"method":"addNum","args":[7]},{"method":"addNum","args":[9]},{"method":"addNum","args":[4]},{"method":"getIntervals","args":[]}]}
Expected[[[1,1],[3,5],[7,7],[9,9]]]

Adding 4 merges [3,3] and [5,5] into [3,5], but does not merge with 1 or 7.

t3_02corner
Input{"calls":[{"method":"addNum","args":[2]},{"method":"addNum","args":[2]},{"method":"addNum","args":[2]},{"method":"getIntervals","args":[]}]}
Expected[[[2,2]]]

Adding the same number multiple times does not change intervals after first addition.

t3_03corner
Input{"calls":[{"method":"addNum","args":[0]},{"method":"addNum","args":[10000]},{"method":"getIntervals","args":[]}]}
Expected[[[0,0],[10000,10000]]]

Adding numbers at minimum and maximum allowed values creates two separate intervals.

t4_01performance
Input{"calls":[{"method":"addNum","args":[0]},{"method":"addNum","args":[1]},{"method":"addNum","args":[2]},{"method":"addNum","args":[3]},{"method":"addNum","args":[4]},{"method":"addNum","args":[5]},{"method":"addNum","args":[6]},{"method":"addNum","args":[7]},{"method":"addNum","args":[8]},{"method":"addNum","args":[9]},{"method":"addNum","args":[10]},{"method":"addNum","args":[11]},{"method":"addNum","args":[12]},{"method":"addNum","args":[13]},{"method":"addNum","args":[14]},{"method":"addNum","args":[15]},{"method":"addNum","args":[16]},{"method":"addNum","args":[17]},{"method":"addNum","args":[18]},{"method":"addNum","args":[19]},{"method":"addNum","args":[20]},{"method":"addNum","args":[21]},{"method":"addNum","args":[22]},{"method":"addNum","args":[23]},{"method":"addNum","args":[24]},{"method":"addNum","args":[25]},{"method":"addNum","args":[26]},{"method":"addNum","args":[27]},{"method":"addNum","args":[28]},{"method":"addNum","args":[29]},{"method":"addNum","args":[30]},{"method":"addNum","args":[31]},{"method":"addNum","args":[32]},{"method":"addNum","args":[33]},{"method":"addNum","args":[34]},{"method":"addNum","args":[35]},{"method":"addNum","args":[36]},{"method":"addNum","args":[37]},{"method":"addNum","args":[38]},{"method":"addNum","args":[39]},{"method":"addNum","args":[40]},{"method":"addNum","args":[41]},{"method":"addNum","args":[42]},{"method":"addNum","args":[43]},{"method":"addNum","args":[44]},{"method":"addNum","args":[45]},{"method":"addNum","args":[46]},{"method":"addNum","args":[47]},{"method":"addNum","args":[48]},{"method":"addNum","args":[49]},{"method":"addNum","args":[50]},{"method":"addNum","args":[51]},{"method":"addNum","args":[52]},{"method":"addNum","args":[53]},{"method":"addNum","args":[54]},{"method":"addNum","args":[55]},{"method":"addNum","args":[56]},{"method":"addNum","args":[57]},{"method":"addNum","args":[58]},{"method":"addNum","args":[59]},{"method":"addNum","args":[60]},{"method":"addNum","args":[61]},{"method":"addNum","args":[62]},{"method":"addNum","args":[63]},{"method":"addNum","args":[64]},{"method":"addNum","args":[65]},{"method":"addNum","args":[66]},{"method":"addNum","args":[67]},{"method":"addNum","args":[68]},{"method":"addNum","args":[69]},{"method":"addNum","args":[70]},{"method":"addNum","args":[71]},{"method":"addNum","args":[72]},{"method":"addNum","args":[73]},{"method":"addNum","args":[74]},{"method":"addNum","args":[75]},{"method":"addNum","args":[76]},{"method":"addNum","args":[77]},{"method":"addNum","args":[78]},{"method":"addNum","args":[79]},{"method":"addNum","args":[80]},{"method":"addNum","args":[81]},{"method":"addNum","args":[82]},{"method":"addNum","args":[83]},{"method":"addNum","args":[84]},{"method":"addNum","args":[85]},{"method":"addNum","args":[86]},{"method":"addNum","args":[87]},{"method":"addNum","args":[88]},{"method":"addNum","args":[89]},{"method":"addNum","args":[90]},{"method":"addNum","args":[91]},{"method":"addNum","args":[92]},{"method":"addNum","args":[93]},{"method":"addNum","args":[94]},{"method":"addNum","args":[95]},{"method":"addNum","args":[96]},{"method":"addNum","args":[97]},{"method":"addNum","args":[98]},{"method":"addNum","args":[99]},{"method":"getIntervals","args":[]}]}
⏱ Performance - must finish in 2000ms

Adding 100 sequential numbers and then getting intervals tests O(n) insertion and retrieval performance within 2 seconds.

Practice

(1/5)
1. You are given a list of meeting time intervals represented as pairs of start and end times. You need to determine if a single person can attend all meetings without any overlaps. Which approach guarantees an optimal and efficient solution?
easy
A. Use dynamic programming to find the maximum number of non-overlapping intervals.
B. Sort intervals by start time and check for any overlap by comparing each interval's start with the previous interval's end.
C. Use a brute force nested loop to compare every pair of intervals for overlap.
D. Sort intervals by end time and greedily select intervals that finish earliest to maximize the number of meetings attended.

Solution

  1. Step 1: Understand the problem requirement

    The problem asks if a single person can attend all meetings without overlap, so we must check if any intervals overlap.
  2. Step 2: Identify the correct approach

    Sorting intervals by start time and checking if any interval starts before the previous one ends guarantees detection of overlaps efficiently.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sorting by start time and checking overlaps is the standard approach [OK]
Hint: Sort by start time and check overlaps [OK]
Common Mistakes:
  • Confusing sorting by end time with start time for overlap detection
2. Consider the following Python function that returns the maximum number of non-overlapping intervals. What is the value of the variable removals after the second iteration of the loop when the input is [[1,3],[2,4],[3,5]]?
from typing import List

def max_non_overlapping_intervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    removals = 0
    last_end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] < last_end:
            removals += 1
            last_end = min(last_end, intervals[i][1])
        else:
            last_end = intervals[i][1]
    return len(intervals) - removals

intervals = [[1,3],[2,4],[3,5]]
print(max_non_overlapping_intervals(intervals))
easy
A. 1
B. 3
C. 2
D. 0

Solution

  1. Step 1: Trace first iteration (i=1)

    Intervals sorted by start: [[1,3],[2,4],[3,5]]. last_end=3. At i=1, intervals[1][0]=2 < 3, so removals=1, last_end=min(3,4)=3.
  2. Step 2: Trace second iteration (i=2)

    At i=2, intervals[2][0]=3 <= last_end=3 is false, so last_end=5, removals remains 1.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    removals incremented once at i=1 only [OK]
Hint: Check overlap condition carefully at each iteration [OK]
Common Mistakes:
  • Off-by-one error in loop iteration
  • Misunderstanding when to increment removals
  • Confusing last_end update logic
3. The following code attempts to implement the optimal car pooling solution. Which line contains a subtle bug that can cause incorrect capacity checks?
def carPooling(trips, capacity):
    max_location = 0
    for _, start, end in trips:
        max_location = max(max_location, end)
    diff = [0] * (max_location + 1)
    for num, start, end in trips:
        diff[start] += num
        diff[end] += num  # Bug here
    current_passengers = 0
    for i in range(max_location + 1):
        current_passengers += diff[i]
        if current_passengers > capacity:
            return false
    return true
medium
A. Line that increments diff[end] by num instead of decrementing
B. Line that updates max_location in the first loop
C. Line that increments diff[start] by num
D. Line that checks if current_passengers exceeds capacity

Solution

  1. Step 1: Understand difference array updates

    Passengers boarding at start location increase count; passengers leaving at end location must decrease count.
  2. Step 2: Identify incorrect update

    Line incrementing diff[end] by num adds passengers instead of removing them, causing incorrect capacity calculation.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Increment at end location breaks capacity tracking [OK]
Hint: End location must decrement passengers, not increment [OK]
Common Mistakes:
  • Incrementing instead of decrementing at end
  • Forgetting to update difference array
  • Checking capacity before summing passengers
4. What is the time complexity of the sweep line algorithm for finding the minimum number of platforms required given n trains, and why?
medium
A. O(n log n) due to sorting arrivals and departures separately and merging them.
B. O(n^2) because each event is compared with all others to count overlaps.
C. O(n) because we only iterate through arrivals and departures once.
D. O(n log n) because events are sorted and then processed in a single pass.

Solution

  1. Step 1: Identify sorting as the main cost

    We create 2n events and sort them by time, which takes O(n log n).
  2. Step 2: Single pass processing after sorting

    After sorting, we iterate through events once, O(n), updating counts.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates, linear sweep after [OK]
Hint: Sorting events dominates time complexity [OK]
Common Mistakes:
  • Assuming O(n) because of single pass ignoring sorting
  • Confusing nested loops brute force with sweep line
  • Thinking sorting arrivals and departures separately is enough
5. Suppose the intervals list can contain overlapping intervals initially (not guaranteed sorted or disjoint), and you want to insert a new interval and return the merged list. Which modification to the optimal approach is necessary to handle this variant correctly?
hard
A. Insert the new interval in the correct position without sorting, then merge only intervals overlapping with the new interval.
B. Append the new interval, then sort and merge all intervals including the original overlapping ones.
C. Skip sorting and merge intervals only if they overlap with the new interval to improve efficiency.
D. Use a balanced tree data structure to insert and merge intervals dynamically without sorting.

Solution

  1. Step 1: Understand initial intervals may overlap

    Since intervals are not guaranteed sorted or disjoint, merging must consider all intervals, not just those overlapping newInterval.
  2. Step 2: Modify approach to handle all overlaps

    Appending newInterval and sorting all intervals ensures correct order, then merging all intervals handles existing overlaps and new overlaps caused by insertion.
  3. Step 3: Why other options fail

    Options B and C assume partial merging which misses existing overlaps; D is overcomplicated and not required.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Sorting and merging all intervals handles arbitrary overlaps [OK]
Hint: Sort and merge all intervals when initial list may overlap [OK]
Common Mistakes:
  • Assuming initial intervals are sorted and disjoint
  • Trying partial merges only around new interval
  • Skipping sorting leads to incorrect merges
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard