Data Structures

Open-Addressing Hash Map

Difficulty

Asked at IMC Trading

Theory: Data Structures You Implement, Not Import

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

Available in C++ and Python. You are solving it in Python. Switch to C++

This problem is only available to subscribers.

Language:

C++23 Python 3.12

run_probe_map

class ProbeMap:
    """..."""

    EMPTY, LIVE, TOMBSTONE = 0, 1, 2

    def __init__(self):
        self.keys = [0] * 8
        self.values = [0] * 8
        self.state = [self.EMPTY] * 8
        self.live = 0
        self.tombstones = 0

    def insert(self, key, value):
        """..."""
        # ...
        return False

    def find(self, key):
        """..."""
        # ...
        return None

    def erase(self, key):
        """..."""
        # ...
        return False

    def size(self):
        return self.live

    def bucket_count(self):
        return len(self.state)

    def probe_length(self, key):
        """..."""
        # ...
        return 0


# ...
# ...
def run_probe_map(ops):
    m = ProbeMap()
    out = []
    for op in ops:
        name = op[0]
        if name == "insert":
            out.append(m.insert(op[1], op[2]))
        elif name == "find":
            out.append(m.find(op[1]))
        elif name == "erase":
            out.append(m.erase(op[1]))
        elif name == "size":
            out.append(m.size())
        elif name == "bucket_count":
            out.append(m.bucket_count())
        elif name == "probe_length":
            out.append(m.probe_length(op[1]))
    return out

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Open-Addressing Hash Map

xxxxxxxx

xxxxxxxxxxx

xx xxxxxx