Course4all

Data Stream as Disjoint Intervals

Expert Answer & Key Takeaways

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on State Management and API Design. ### Core Principles 1. Encapsulation: Keep data private and expose functionality through well-defined methods. 2. Trade-offs: Every design choice has a cost. Is it better to have O(1)O(1) read and O(N)O(N) write, or vice versa? 3. State Consistency: Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for O(1)O(1) caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - HashMap: Provides O(1)O(1) lookups for keys to their corresponding nodes. - DLL: Provides O(1)O(1) addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in Queue using Stacks or Dynamic Arrays. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is O(1)O(1), and "flipping" elements to another stack happens only when necessary, averaging O(1)O(1) per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., Circular Queue, Hit Counter). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., Bounded Blocking Queue). - Use Mutexes (Locks) to prevent data races. - Use Condition Variables (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. Identify the API: What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. Define the State: What variables represent the current state? (Size, Capacity, Pointers). 3. Choose the Data Structures: Select the combination that minimizes time complexity for the most frequent operations. 4. Dry Run: Trace the state changes through a sequence of operations based on your chosen structure.

Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1,a2,…,ana_1, a_2, \dots, a_n, summarize the numbers seen so far as a list of disjoint intervals.

Requirement

  • addNum(val): Add integer to the stream.
  • getIntervals(): Return the summary as a list of intervals.
Hard

Examples

Input: addNum(1), getIntervals(), addNum(3), getIntervals(), addNum(2), getIntervals()
Output: [[1, 1]], [[1, 1], [3, 3]], [[1, 3]]
Approach 1

Level I: List of Numbers + Rebuild on Query

Intuition

Store all individual numbers in a Set to handle duplicates. For getIntervals, convert the set to a sorted list and iterate through it to form intervals whenever numbers are not consecutive.
⏱ Add: O(1), Get: O(N log N) for sorting.💾 O(N).

Detailed Dry Run

Input: 1, 3, 2. Set: {1, 2, 3}. Sorted: [1, 2, 3]. Intervals: [[1, 3]].
java
class SummaryRanges {
    Set<Integer> set = new HashSet<>();
    public void addNum(int val) { set.add(val); }
    public int[][] getIntervals() {
        if(set.isEmpty()) return new int[0][0];
        List<Integer> list = new ArrayList<>(set); Collections.sort(list);
        List<int[]> res = new ArrayList<>();
        int start = list.get(0), end = list.get(0);
        for(int i=1; i<list.size(); i++) {
            if(list.get(i) == end + 1) end = list.get(i);
            else { res.add(new int[]{start, end}); start = end = list.get(i); }
        }
        res.add(new int[]{start, end});
        return res.toArray(new int[0][]);
    }
}
Approach 2

Level II: Sorted List (Manual Merging)

Intuition

Maintain a list of disjoint intervals sorted by start time. For addNum, find the insertion spot and check if it can merge with neighbor intervals. This is O(N)O(N) due to list shifting.
⏱ Add: O(N), Get: O(1).💾 O(N).
java
class SummaryRanges {
    List<int[]> intervals = new ArrayList<>();
    public void addNum(int val) { /* O(N) binary search + shift */ }
    public int[][] getIntervals() { return intervals.toArray(new int[0][]); }
}
Approach 3

Level III: Balanced BST / TreeMap

Intuition

Use a TreeMap to store intervals as start -> end. When a new number x is added, find the interval that ends just before it and the one that starts just after it. Merge them if possible.
⏱ Add: O(log N), Get: O(N).💾 O(N).
java
class SummaryRanges {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    public void addNum(int val) {
        Integer low = map.floorKey(val), high = map.ceilingKey(val);
        if (low != null && map.get(low) >= val) return;
        boolean mergeLow = (low != null && map.get(low) == val - 1);
        boolean mergeHigh = (high != null && high == val + 1);
        if (mergeLow && mergeHigh) {
            map.put(low, map.get(high)); map.remove(high);
        } else if (mergeLow) {
            map.put(low, val);
        } else if (mergeHigh) {
            map.put(val, map.get(high)); map.remove(high);
        } else map.put(val, val);
    }
    public int[][] getIntervals() {
        int[][] res = new int[map.size()][2]; int i = 0;
        for (int k : map.keySet()) res[i++] = new int[]{k, map.get(k)};
        return res;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionDesign Phone Directory
Next Question →Range Sum Query 2D - Mutable