The Merge

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
L3
Asked in
Goldman Sachs

Problem

Given two already-sorted lists a and b, return a single sorted list containing all their elements. Do NOT use sorted() or sort(). Use the O(n+m) merge procedure.

Chaos in. Order out.

Example 1

Input:

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

Output:

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

Example 2

Input:

a = [], b = [10,20]

Output:

[10,20]

Worked solution and explanation

Why this problem exists in real interviews

This tests the two-pointer merge technique, the building block of merge sort and distributed stream merging. It verifies that candidates can achieve O(n + m) merging without falling back to concatenation plus sorting.

Break down the requirements

Step 1: Set up two pointers

Pointer i starts at the beginning of list a, pointer j at the beginning of list b.

Step 2: Compare and take the smaller element

At each step, append the smaller of a[i] and b[j] to the result and advance that pointer.

Step 3: Append leftover elements

When one list is exhausted, append all remaining elements from the other.

The solution

Two-pointer linear merge
def merge(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