Your Search Engine Combines Results From Multiple Pre-Sorted Indexes Into One Ranked List

The Scenario: "We are building a Federated Search Aggregator. When a user types a query, we hit five different database shards in parallel. Each shard returns a list of document IDs sorted by their relevance score.

To present the final results to the user, we need to merge these $K$ sorted lists into one master list. Since we are operating at Google-scale, the total number of results ($N$) can be in the millions, but the number of shards ($K$) is small. How do you merge these efficiently without re-sorting the entire dataset

Language

Sample Test Cases

Case 1

Input

[[1,3,5],[2,4,6]]

Expected Output

[1,2,3,4,5,6]

Case 2

Input

[[[1, 5], [2, 4]], [[3, 3], [4, 2]]]

Expected Output

[[1, 5], [2, 4], [3, 3], [4, 2]]

Case 3

Input

[[1,1,1],[1,1]]

Expected Output

[1,1,1,1,1]

Case 4

Input

[[[10, 10], [20, 8]], [[5, 9], [15, 7]], [[25, 6]]]

Expected Output

[[10, 10], [5, 9], [20, 8], [15, 7], [25, 6]]

Case 5

Input

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

Expected Output

[1,2]

Case 6

Input

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

Expected Output

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

Your Search Engine Combines Results From Multiple Pre-Sorted Indexes Into One Ranked List

Sample Test Cases

Comments (0)

Your Search Engine Combines Results From Multiple Pre-Sorted Indexes Into One Ranked List

Sample Test Cases

Comments (0)