Multiset Implementation

A multiset is a set that can hold the same value more than once. This question checks two dunder methods, __contains__ and __len__, and whether you handle duplicates and missing values correctly.

What the question asks

Complete a Multiset class with four operations:

• add(val) adds one copy of val.
• remove(val) removes one copy of val if there is one. If val is not in the multiset, nothing happens and nothing is raised.
• val in m returns True if at least one copy of val is present, otherwise False.
• len(m) returns the total number of values, counting every copy.

The stub reads commands such as add 1, remove 1, query 1 and size, runs them on one Multiset, and prints the result of every query and size.

Function to write

class Multiset:
    def add(self, val): ...
    def remove(self, val): ...
    def __contains__(self, val): ...
    def __len__(self): ...

The template gives you these four methods with comments and no constructor. You have to add __init__ yourself to set up the storage.

Solution

class Multiset:
    def __init__(self):
        self.counts = {}
        self.size = 0

    def add(self, val):
        self.counts[val] = self.counts.get(val, 0) + 1
        self.size += 1

    def remove(self, val):
        if val not in self.counts:
            return
        self.counts[val] -= 1
        if self.counts[val] == 0:
            del self.counts[val]
        self.size -= 1

    def __contains__(self, val):
        return val in self.counts

    def __len__(self):
        return self.size

How it works

• counts maps each value to how many copies are stored. size is the total number of copies.
• add uses counts.get(val, 0), so a new value starts at 0 and becomes 1.
• remove returns early when the value is not there. Otherwise it takes one copy away, and deletes the key when the count reaches 0. Deleting the key matters, because __contains__ only checks whether the key exists.
• val in m calls m.__contains__(val), and len(m) calls m.__len__().
• Every operation is constant time, so a long list of commands is no problem.

A plain list also works: append in add, if val in self.items: self.items.remove(val) in remove, and len(self.items). It is easier to read and fine for small inputs. The dict version stays fast however many values you add.

Mistakes that fail the hidden tests

• Calling list.remove without checking first. [1, 2].remove(5) raises ValueError. Removing a value that is not there must be a silent no-op.
• Using a set. A set stores each value once, so after add 2 twice, size prints 1 instead of 2.
• Removing every copy. Filtering the list with [x for x in items if x != val] removes all copies. The question wants one copy removed per call.
• Keeping a count but never deleting the key. With a dict, if you leave {1: 0} behind, 1 in m still says True.
• One underscore in the dunder names. _contains_ and _len_ are ordinary methods that Python never calls. len(m) then fails with “object of type ‘Multiset’ has no len()”.
• Storage on the class instead of in __init__. items = [] under class Multiset: is shared by every Multiset object. The stub only builds one per test, so it may pass, but two multisets in the same program would share their values.

Try it on sample data

Twelve commands in the stub’s format:

12
query 1
add 1
query 1
remove 1
query 1
add 2
add 2
size
query 2
remove 2
query 2
size

Output from my run with a copy of the stub’s loop:

False
True
False
2
True
True
1

After two add 2 commands the size is 2. One remove 2 leaves one copy, so query 2 is still True and the size drops to 1.