Data Stream as Disjoint Intervals

Data Stream as Disjoint Intervals

What is this problem about?

The Data Stream as Disjoint Intervals interview question asks you to design a class that receives a stream of non-negative integers and summarizes the numbers seen so far as a list of disjoint intervals. For example, if you see 1, 2, and 3, they form the interval [1, 3]. If you then see 5, the intervals are [1, 3] and [5, 5]. This Data Stream as Disjoint Intervals coding problem is about real-time data aggregation.

Why is this asked in interviews?

Amazon and Google ask this to test your ability to choose the right data structure for efficient inserts and searches. A simple list would be O(N) to insert, making the overall process slow. Using an Ordered Set or a TreeMap allows you to find neighboring intervals in O(log N) and merge them in O(1). It evaluates your system design thinking within an algorithmic context.

Algorithmic pattern used

This utilizes the Design, Binary Search, Ordered Set interview pattern.

1. Ordered Storage: Use a data structure that keeps intervals sorted by their start points (like std::set in C++ or TreeMap in Java).
2. Binary Search: When a new number val arrives, find the existing intervals immediately before and after it.
3. Merging Logic:
   • If val is already inside an interval, do nothing.
   • If val bridges the gap between the left and right intervals, merge all three.
   • If val connects to only one side, extend that interval.
   • Otherwise, create a new [val, val] interval.

Example explanation

Current Intervals: [1, 2], [4, 5].

1. Add 3: val=3 is left+1 (2+1) and right-1 (4-1). Merge into [1, 5].
2. Add 7: Not adjacent to anything. New state: [1, 5], [7, 7].
3. Add 6: Adjacent to [5, 5] and [7, 7]. Merge into [1, 7].

Common mistakes candidates make

• Full Re-sort: Sorting the whole list every time a number is added, leading to O(N^2 log N) complexity.
• Redundant Entries: Adding a number like 2 when the interval [1, 5] already exists.
• Handling Boundries: Forgetting to check if the new number is exactly one greater than the end of the previous interval or one less than the start of the next.

Interview preparation tip

Be comfortable with TreeMap (Java) or std::set/map (C++). Knowing how to use floorKey, ceilingKey, lower, and higher is essential for interval merging problems.