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

from typing import Any


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

    EMPTY, LIVE, TOMBSTONE = 0, 1, 2

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

    def insert(self, key: int, value: int) -> bool:
        """..."""
        # ...
        return False

    def find(self, key: int) -> int | None:
        """..."""
        # ...
        return None

    def erase(self, key: int) -> bool:
        """..."""
        # ...
        return False

    def size(self) -> int:
        return self.live

    def bucket_count(self) -> int:
        return len(self.state)

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


# ...
# ...
def run_probe_map(ops: list[tuple[Any, ...]]) -> list[bool | int | None]:
    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.

Next in STL From ScratchBlock-Based DequeData Structures

Open-Addressing Hash Map

xxxxxxxx

xxxxxxxxxxx