Module 02 · Hash Maps, Sets, and Frequency State

018. Multiset Intersection

Interview · Download this solution · All solutions and shared helpers

Problem

Return common integers with multiplicity: value x appears min(count_a(x), count_b(x)) times. Emit matches in the order they are consumed from b. Do not mutate either list. Empty input on either side yields [].

Examples

Example 1

multiset_intersection([1, 2, 2, 1], [2, 2])
=> [2, 2]

Both available copies are consumed.

Example 2

multiset_intersection([], [1])
=> []

There is no supply.

Example 3

multiset_intersection([2], [2, 2])
=> [2]

One supply occurrence cannot be reused.

Reveal the worked solution and reasoning

Why this mechanism works

Treat a as a finite supply and b as demand. Finding a value is insufficient after all copies have been consumed. Decrementing remaining supply after each committed match ensures that the same occurrence cannot serve several requests.

State and boundaries

supply[x] is the number of unmatched x occurrences from a. output records fulfilled demand from b.

Protocol

Count supply from a.
Scan b in order.
Append only when supply is positive.
Decrement immediately after appending.
Return output.

Visualization

a supply: 1=2, 2=2
b demand: 2, 2, 2
fulfilled: 2, 2; final request rejected

Python implementation

def multiset_intersection(a, b):
    supply = {}
    for value in a:
        supply[value] = supply.get(value, 0) + 1
    output = []
    for value in b:
        if supply.get(value, 0) > 0:
            output.append(value)
            supply[value] -= 1
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

multiset_intersection([1, 2, 2, 1], [2, 2])

L2 multiset_intersection: supply = {}
a=[1, 2, 2, 1]; b=[2, 2]; supply={}

L3 multiset_intersection: for value in a:
a=[1, 2, 2, 1]; b=[2, 2]; supply={}; value=1

L4 multiset_intersection: supply[value] = supply.get(value, 0) + 1
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:1}; value=1

L3 multiset_intersection: for value in a:
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:1}; value=2

L4 multiset_intersection: supply[value] = supply.get(value, 0) + 1
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:1, 2:1}; value=2

L4 multiset_intersection: supply[value] = supply.get(value, 0) + 1
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:1, 2:2}; value=2

L3 multiset_intersection: for value in a:
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:1, 2:2}; value=1

L4 multiset_intersection: supply[value] = supply.get(value, 0) + 1
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:2, 2:2}; value=1

... 2 intermediate state changes omitted ...

L8 multiset_intersection: output.append(value)
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:2, 2:2}; value=2; output=[2]

L9 multiset_intersection: supply[value] -= 1
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:2, 2:1}; value=2; output=[2]

L8 multiset_intersection: output.append(value)
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:2, 2:1}; value=2; output=[2, 2]

L9 multiset_intersection: supply[value] -= 1
a=[1, 2, 2, 1]; b=[2, 2]; supply={1:2, 2:0}; value=2; output=[2, 2]

Result: [2, 2]. Both available copies are consumed.

multiset_intersection([], [1])

L2 multiset_intersection: supply = {}
a=[]; b=[1]; supply={}

L5 multiset_intersection: output = []
a=[]; b=[1]; supply={}; output=[]

L6 multiset_intersection: for value in b:
a=[]; b=[1]; supply={}; output=[]; value=1

Result: []. There is no supply.

Why the solution is correct

A match consumes a previously unused occurrence from each list. Demand is fulfilled until one side's multiplicity is exhausted, giving exactly the smaller count. Scanning b directly provides the required output order.

Time and space

O(n+m) expected time; O(u) supply state plus O(min(n,m)) output.

Common mistakes

A set intersection loses multiplicity. Forgetting to decrement can overproduce repeated matches.

Reasoning card

State: supply[x] is the number of unmatched x occurrences from a. output records fulfilled demand from b.

Invariant: Remaining counts represent unmatched supply.

Decision to rehearse: Consume counts as matches are committed.

Finish: Return output

Transfer exercise

When both inputs are sorted, solve the same matching problem with two pointers and no frequency table.