The List Merger

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L4
Asked in
Goldman Sachs

Problem

Return one ascending list holding every value from a and b, two already-sorted lists of integer keys exported by separate shards of the same partitioned table. Because the shards arrive sorted, the combine must stay linear in their total length without calling sort() or sorted(), and either shard may come back empty.

No shortcuts.

Example 1

Input:

a = [1,3,5], b = [2,4,6]

Output:

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

Example 2

Input:

a = [1,1,1], b = [1,1]

Output:

[1,1,1,1,1]

Worked solution and explanation

This is merge sort's final step with the sort taken off the table. Everyone writes the loop that compares the two heads and takes the smaller one. What separates candidates is what happens when one list runs dry. Stop the moment either index hits its end, and [1, 2, 3] merged with [7, 8, 9, 10, 11] comes back as just [1, 2, 3]. Worse, an empty a returns nothing at all even when b holds [2, 4, 7].

The ban on sorted(a + b) is the point of the exercise. That one-liner is correct, but it is O((n+m) log(n+m)) and throws away the ordering the shards already paid for. The interviewer wants to see you spend the sortedness you were handed.

Walking the two heads

Step 1: Keep one index per list

i marks the next unread key in a, and j marks the next one in b. Because both lists are ascending, the smallest unread key overall is always a[i] or b[j]. Nothing deeper in either list can beat them.

Step 2: Take the smaller head and advance only that index

Compare a[i] with b[j], append the smaller one, and move just that index forward. On a tie, <= takes from a first. Both copies still land in the result, which is how the all-1 example keeps all five values.

Step 3: Drain whatever is left

The main loop stops as soon as either list is used up, but the other list may still hold keys. Every one of them is at least as large as anything already appended, so copy them over in order. Write both drain loops: you do not know in advance which side finishes first, and an empty list finishes before the loop even starts.

Two-pointer merge in linear time
def merge_sorted(a, b):
    result = []
    i = 0
    j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    while i < len(a):
        result.append(a[i])
        i += 1
    while j < len(b):
        result.append(b[j])
        j += 1
    return result

Common follow-up questions