Merge K Sorted Feed Lists | Dataford Interview Questions

Merge K Sorted Feed Lists

Medium

CodingLinked ListsSortingHeapAsked 2 times

Problem

In a Meta-style feed aggregation service, multiple independently sorted streams must be combined into one globally sorted result. Given k sorted integer lists, merge them into a single sorted list.

Formal Specification

Implement a function that takes lists, where lists[i] is a sorted list of integers in non-decreasing order, and returns a single list containing all values from every input list in non-decreasing order.

Input: lists: List[List[int]]
Output: List[int]

Constraints

0 <= k <= 10^4
0 <= len(lists[i]) <= 10^4
-10^9 <= lists[i][j] <= 10^9
Each list is sorted in non-decreasing order
The total number of elements across all lists is at most 10^5

Function Signature

def merge_k_sorted_lists(lists):

You are practicing as a guest. Sign up free to run your code against the sample data. Your draft stays right here.

def solve(rows):
    counts = {}
    for row in rows:
        ...
    return result

Next questions

Merge K Sorted Linked ListsMedium

Merge K Sorted ListsMedium

Merge K Sorted Lists OptimizationHard

Python 3.10