FastPrepPaginated K-Way Unique Merge

Paginated K-Way Unique Merge

Airwallex logoAirwallex● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Each row in sources is one data source's nondecreasing record-id stream. A source can be fetched only in consecutive pages of at most pageSize records.

Merge all sources into one strictly increasing sequence, removing duplicate ids within or across sources. Process records in streaming order; the output models calls to a writer that accepts one id at a time.

Function

mergePagedSources(sources: int[][], pageSize: int) → int[]

Examples

Example 1

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

The sorted streams merge and duplicate 1, 4, and 7 appear once.

Example 2

sources = [[],[2,2,2],[1,3]]pageSize = 1return = [1,2,3]

Empty sources and duplicates are supported.

Example 3

sources = [[5,6],[1,2,3]]pageSize = 10return = [1,2,3,5,6]

A short page exhausts each source.

Constraints

  • 0 <= sources.length <= 10^4.
  • Every source is nondecreasing; the total record count is at most 2 * 10^5.
  • 1 <= pageSize <= 10^5.

More Airwallex problems

See Airwallex hiring insights
public int[] mergePagedSources(int[][] sources, int pageSize) {
    // Write your solution here.
}
sources[[1,4,7],[1,2,7,9],[3,4,8]]
pageSize2
expected[1,2,3,4,7,8,9]
Checking account…