Data Stream as Disjoint Intervals

HardIntervalsdesign

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Numbers arrive one at a time from a stream of non-negative integers. At any point, you must be able to summarize everything seen so far as a list of **disjoint, maximal** closed intervals. Implement SummaryRanges: - SummaryRanges() starts with an empty stream. - addNum(value) adds value to the stream. Repeated values are allowed and have no extra effect. - getIntervals() returns the summary as a list of [start, end] pairs, **sorted by start**. Consecutive integers belong to the same interval, so 1, 2, 3 is reported as [1, 3] and never as [1, 2], [3, 3]. If there are many addNum calls and relatively few distinct intervals, addNum should cost O(log k) plus the work to merge, where k is the number of intervals.

Examples

Input: ["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","addNum","getIntervals"] [[],[5],[],[7],[],[6],[],[5],[1],[]]
Output: [null,null,[[5,5]],null,[[5,5],[7,7]],null,[[5,7]],null,null,[[1,1],[5,7]]]
Adding 6 bridges [5,5] and [7,7] into [5,7]. Adding 5 again changes nothing, and 1 starts a new interval that sorts first.
Input: ["SummaryRanges","getIntervals","addNum","addNum","getIntervals"] [[],[],[0],[10000],[]]
Output: [null,[],null,null,[[0,0],[10000,10000]]]
With nothing added the summary is empty. Values at both ends of the range stay separate.

Constraints

  • 0 <= value <= 10^4
  • At most 3 * 10^4 calls are made to `addNum` and `getIntervals`.
  • At most 100 calls are made to `getIntervals`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More design problems