Data Structures

Hand-Rolled Hash Map

Difficulty

Asked at IMC Trading, Headlands Technologies

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_flat_hash_map

import random
from collections.abc import Sequence
from typing import Any

MASK64 = (1 << 64) - 1


def mix64(key: int) -> int:
    """..."""
    x = (key & MASK64) + 0x9E3779B97F4A7C15 & MASK64
    x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK64
    x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK64
    return x ^ (x >> 31)


class FlatHashMap:
    """..."""

    def __init__(self) -> None:
        # ...
        pass

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

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

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

    def size(self) -> int:
        # ...
        return 0


# ...
# ...
def run_flat_hash_map(ops: list[tuple[Any, ...]]) -> list[int | bool | None]:
    m = FlatHashMap()
    out = []
    for op in ops:
        name = op[0]
        if name == "insert":
            out.append(m.insert(op[1], op[2]))
        elif name == "erase":
            out.append(m.erase(op[1]))
        elif name == "find":
            out.append(m.find(op[1]))
        elif name == "size":
            out.append(m.size())
    return out


# ...
# ...
def checksum(values: Sequence[Any]) -> int:
    h = 0
    for v in values:
        if v is None:
            x = -1
        elif isinstance(v, bool):
            x = 1 if v else 0
        elif isinstance(v, (tuple, list)):
            x = checksum(v)
        elif isinstance(v, (bytes, bytearray)):
            x = checksum(list(v)) + len(v)
        else:
            x = v
        h = (h * 1000003 + x + 2) % 1000000007
    return h

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Next in STL From ScratchOpen-Addressing Hash MapData Structures

Hand-Rolled Hash Map

xxxxxxxx

xxxxxxxxxxx