Merge K Lists

Python data engineering interview problem. Difficulty: advanced. Pattern: Heaps. About 18 minutes. Part of the Pro drill bank.

Merge k sorted lists into one sorted list. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

Several sorted partitions of a dataset must become one sorted stream without losing equal values. Merge every ascending list in lists into one ascending list. Empty lists are allowed, and each input value must appear exactly once in the output. Write merge_k_lists(lists: list) -> list. The three lists [1,4,5], [1,3,4] and [2,6] merge to [1,1,2,3,4,4,5,6]. The starter file already contains the function name, harness and print lines. Keep them and fill only the function body.

Requirements

• Keep all values from all lists.
• Return one ascending list.
• Handle any number of input lists and empty lists.

Constraints

• Each inner list is already sorted.
• Return a list and preserve duplicate values.

Examples

Input: merge_k_lists([[1, 4, 5], [1, 3, 4], [2, 6]]) Output: [1, 1, 2, 3, 4, 4, 5, 6] Heap merges heads.

Topics: lakebench, python, merge, heap.

More Python interview questions · All interview problems · Learn data engineering