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 C++. Switch to Python

This problem is only available to subscribers.

Language:

C++23 Python 3.12

ProbeMap

#include <cstddef>
#include <cstdint>
#include <optional>
#include <vector>

// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
// ...
class ProbeMap {
public:
    ProbeMap() : slots_(8) {}

    bool insert(long long key, long long value) {
        // ...
        (void)key;
        (void)value;
        return false;
    }

    std::optional<long long> find(long long key) const {
        // ...
        (void)key;
        return std::nullopt;
    }

    bool erase(long long key) {
        // ...
        (void)key;
        return false;
    }

    long long size() const { return size_; }
    long long bucket_count() const { return static_cast<long long>(slots_.size()); }

    long long probe_length(long long key) const {
        // ...
        (void)key;
        return 0;
    }

private:
    enum class State : unsigned char { empty, live, tombstone };

    struct Slot {
        long long key = 0;
        long long value = 0;
        State state = State::empty;
    };

    std::vector<Slot> slots_;
    long long size_ = 0;
    long long tombstones_ = 0;
};

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Open-Addressing Hash Map

xxxxxxxx

xxxxxxxxxxx

xx xxxxxx