The Matching Manifest

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

Problem

Two shipment manifests, list1 and list2, hold integer item codes, and either one can repeat a code or list codes in any order. Return the codes that appear on both manifests, each once, smallest first.

Two warehouses, one shipment - only load what's in both.

Example 1

Input:

list1 = [1,2,2,1], list2 = [2,2]

Output:

[2]

Example 2

Input:

list1 = [4,9,5], list2 = [9,4,9,8,4]

Output:

[4,9]

Worked solution and explanation

What this really is

This is a set intersection that comes with two output contracts attached: each value appears once, and the list comes back sorted. Anyone can find the values that overlap. The trap is the one-liner [x for x in list1 if x in list2]. It looks right and gives back the overlap, but it also carries along every duplicate from list1 and keeps the input order. On the first example it returns '[2, 2]' instead of '[2]'. On the second it returns '[4, 9]' only because of how the input happens to be ordered. Dedupe and order are part of the answer, so leaving either one out fails an exact-match grader.

Build it in three moves

Step 1: Index one manifest

Turn list1 into a set called set1. Each membership check then costs constant time instead of a scan of the whole list, so the solution stays linear and never becomes quadratic.

Step 2: Collect each match once

Go through list2 and keep a value only when it is in set1 and has not already been kept. The seen set is the dedupe. Without it, a code that appears three times on the second manifest shows up three times in the answer.

Step 3: Sort before returning

The order in which matches are collected follows list2, not value order. Calling common.sort() at the end is what makes the result smallest first, and that order is what gets graded.

Indexed lookup, deduped, sorted
def find_intersection(list1, list2):
    set1 = set(list1)
    seen = set()
    common = []
    for val in list2:
        if val in set1 and val not in seen:
            common.append(val)
            seen.add(val)
    common.sort()
    return common

Common follow-up questions