Intersection of Two Arrays

The word intersection hides a choice that interviewers will make you state. Does it mean the distinct common values, the common values with duplicates preserved, or the common values with their multiplicities matched? Each gives a different answer for the same inputs, so say which one you are implementing before you write a line of code.

def intersection(a, b):
    seen = set(a)
    return [value for value in b if value in seen]

print(intersection([1, 2, 3, 4], [3, 4, 5]))
print(intersection([1, 2], [3, 4]))

The outputs are 3, 4 and an empty list. The first call finds the two values that appear in both arrays. The second finds none, so the list is empty.

The mechanism is that a set turns the membership question into a constant-time lookup. You put the first array into a set, then walk the second array and keep the values that are found. Without the set you would be scanning the first array for every element of the second, which is quadratic. The complexity is linear in the combined length, with space proportional to the number of distinct values in the first array.

The trade-off to name is space against time, plus an ordering subtlety. This version returns the common values in the order they appear in the second array, and it does not deduplicate them, so if both arrays contain three copies of the same value you get three copies back. If you want distinct values, add the result to a set. If you want multiplicities matched, you need a count table rather than a set, and you should say so. The honest interview answer names the interpretation first and then gives the matching implementation.

Keep a set of the values you have already emitted. Walk the list, and add a value to the result only the first time you see it. The set makes the check constant time instead of a scan of the result.

def unique_in_order(items):
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

print(unique_in_order([1, 2, 2, 3, 1, 4]))

The output is 1, 2, 3, 4. The two extra copies of 2 and the repeated 1 are dropped, and the surviving values keep the order in which they first appeared.

The mechanism is that the set holds the membership history. Without it you would have to check whether the value is already in the result list, which is a linear scan and turns the whole routine into quadratic. The set turns each check into a hash lookup, so the routine is linear in the length of the input.

The trade-off to name is that a dictionary already preserves insertion order, so a slightly different trick works: assign each value a counter slot and let the dictionary keep the first occurrence. The set-based version is clearer and does the same job. In Python 3.7 and later, dict.fromkeys gives the same result in one line, since the keys keep their original order and the duplicates are discarded. Mentioning that is a good sign, as long as you can still write the loop version when the order guarantee matters or the runtime is older.