How should I practice Intersect Multiple Interval Lists?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Intersect Multiple Interval Lists associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Intersect Multiple Interval Lists

Google● HardFULLTIMEONSITE INTERVIEW

Learn

Problem statement

You are given intervalLists, an array of lists of closed integer intervals. An interval [start, end] includes both endpoints. A list may be unsorted and may contain overlapping intervals.

First normalize every list by sorting and merging its overlapping intervals. Then return all maximal nonempty closed intervals that occur in every normalized list, sorted by start.

If intervalLists contains no lists or any list is empty, return an empty array.

Follow-up

How would you process each already-normalized list as a stream when the complete lists do not fit in memory?

Function

intersectIntervalLists(intervalLists: int[][][]) → int[][]

Examples

Example 1

intervalLists = [[[0,2],[5,10],[13,23]],[[1,5],[8,12],[15,24]]]return = [[1,2],[5,5],[8,10],[15,23]]

The result contains every closed overlap shared by the two lists, including the single-point interval [5,5].

Example 2

intervalLists = [[[1,4],[3,7]],[[2,5]],[[0,3],[6,9]]]return = [[2,3]]

The first list normalizes to [[1,7]]. The interval shared by all three normalized lists is [2,3].

Example 3

intervalLists = [[[1,2]],[]]return = []

No interval can occur in every list when one list is empty.

Constraints

Each interval has exactly two endpoints [start, end] with start <= end.
Every endpoint fits in a signed 32-bit integer.
The returned intervals are maximal, pairwise disjoint, and sorted by start.