FastPrepMerge Multiple Sorted Streams

Merge Multiple Sorted Streams

Bloomberg LP logoBloomberg LP● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

You are given streams, where each inner array is an independently sorted stream of integers in nondecreasing order. Merge every value from every stream into one nondecreasing array.

Preserve every occurrence, including duplicates. Empty streams are valid. Process the inputs as independent ordered streams rather than concatenating and sorting all values again.

Function

mergeSortedStreams(streams: int[][]) → int[]

Examples

Example 1

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

The next smallest available head is selected until every stream is exhausted. Both copies of 2 remain in the result.

Example 2

streams = [[],[-5,0,6],[1],[1,10]]return = [-5,0,1,1,6,10]

Empty streams contribute nothing, and equal values from different streams are both preserved.

Example 3

streams = []return = []

With no streams, the merged result is empty.

Constraints

  • 0 <= streams.length <= 100
  • 0 <= streams[i].length
  • The total number of values across all streams is at most 100000.
  • -1000000000 <= streams[i][j] <= 1000000000
  • Every inner array is sorted in nondecreasing order.

More Bloomberg LP problems

See Bloomberg LP hiring insights
public int[] mergeSortedStreams(int[][] streams) {
    // Write your solution here
}
streams[[1,4,7],[2,2,9],[3,8]]
expected[1,2,2,3,4,7,8,9]
Checking account…