Frontend School

Merge K Sorted Sensor Data Streams

DSA
medium

Merge K Sorted Sensor Data Streams

Medium
Heap
Priority Queue
Merge
Iterators

Overview

In large-scale IoT deployments, collecting and processing data from numerous sensors is a common task. Often, each sensor generates a stream of readings that are naturally ordered by time or value. For comprehensive analysis, it's frequently necessary to consolidate these individual sensor streams into a single, unified, and globally sorted data stream. This problem challenges you to efficiently merge k such sorted data streams, where the total volume of data can be very large, making in-memory storage of all streams impractical.

What you need to do / Task

Implement the mergeKSortedStreams function. This function takes an array of StreamIterator objects, where each iterator represents a sorted stream of numbers. Your goal is to merge all these streams into a single, sorted array of numbers containing all readings from all input streams.

You must interact with each stream exclusively through its StreamIterator interface. Do not assume the underlying data structure of the stream.

The StreamIterator interface is defined as follows:

interface StreamIterator {
    /**
     * Advances the iterator and returns the next value in the stream.
     * If the stream has more elements, returns `{ value: number, done: false }`.
     * If the stream is exhausted, returns `{ value: undefined, done: true }`.
     */
    next(): { value: number | undefined, done: boolean };
}

Input & output

Input:

  • streams: An array of StreamIterator objects. Each StreamIterator provides numbers in non-decreasing order.

Output:

  • A number[] representing a single, sorted array containing all numbers from all input streams.

Clarifications

  • Empty streams: Some input StreamIterator objects might be empty from the start (i.e., their first next() call returns { value: undefined, done: true }). Your solution should handle these gracefully.
  • Duplicate values: Streams may contain duplicate values, and duplicates may exist across different streams. All duplicates should be preserved in the final merged array.
  • Large N: The total number of readings across all streams can be very large, so an efficient solution is required.

Examples

1

Example 1

Input:

streams = [[1,5,9], [2,3,8], [4,6,7]]

Output:

[1,2,3,4,5,6,7,8,9]

Note:

Merges three sorted streams into a single sorted array.

2

Example 2

Input:

streams = [[10], [], [1,2]]

Output:

[1,2,10]

Note:

Handles empty streams and streams with a single element.

3

Example 3

Input:

streams = [[1,1,3], [1,2,2], [3]]

Output:

[1,1,1,2,2,3,3]

Note:

Preserves duplicate values and merges streams with varying lengths.

Constraints

Constraints & assumptions

  • 1 <= streams.length <= 10^5 (number of input streams, k)
  • The total number of readings across all streams N <= 10^6.
  • 0 <= reading <= 10^9 for any number returned by StreamIterator.next().
  • Each stream is guaranteed to produce numbers in non-decreasing order.
  • The StreamIterator.next() method is synchronous.

Out of scope

  • Handling invalid StreamIterator implementations (e.g., next() returning non-numeric values or violating sorted order).
  • Asynchronous stream processing.

What interviewers evaluate

  • Correctness: The merged array must be perfectly sorted and contain all elements from all input streams.
  • Efficiency (Time Complexity): The solution should process N total elements efficiently, typically aiming for O(N log K) where K is the number of streams.
  • Efficiency (Space Complexity): The solution should use auxiliary space efficiently, typically aiming for O(K) to store elements from active streams.
  • Code Clarity and Structure: The code should be well-organized, readable, and demonstrate good programming practices.

Loading editor...