Design HashSet

EASY✓ CHIP-TIMEDLC #705 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Build a set of non-negative integers from scratch — add, remove, and check membership — without reaching for a language's built-in hash set.

A set of non-negative integers needs building from the ground up — add a value, remove a value, and check whether a value is currently present — without leaning on a language's ready-made hash set.

Adding a value already inside does nothing new, and removing a value that isn't present is simply a no-op; the set only ever tracks presence, never how many times something was added.

This site drives the drill as a sequence of operations against one live instance: each call acts on whatever the set currently holds, in the order the calls arrive.

keys are non-negative integers within a bounded, modest range
add on an existing key and remove on a missing key are both harmless no-ops
operations are processed one at a time, in arrival order
no built-in hash set or map type may back the implementation

EX 01

MyHashSet()

add(1)

add(2)

contains(1) → true

contains(3) → false

add(2)

contains(2) → true

remove(2)

contains(2) → false

basic add, contains, remove

EX 02

MyHashSet()

add(5)

remove(5)

contains(5) → false

remove(5)

adding the same key twice is idempotent; removing twice is a no-op

EX 03

MyHashSet()

add(0)

contains(0) → true

add(1000000)

contains(1000000) → true

remove(0)

contains(0) → false

boundary keys: 0 and 1,000,000

The hintstake only what you need

HINT 1 THE NUDGE

A plain list gets add and remove for free, but membership means scanning every element. How do you make 'have I seen this' stop depending on how many things you've stored?

HINT 2 THE STRUCTURE

Keys live in a bounded range. A fixed-size array of buckets, indexed by key modulo the bucket count, turns 'which bucket' into one division.

HINT 3 ONE STEP FROM THE ANSWER

Each bucket only ever holds the handful of keys that collide into it — a short list per bucket, scanned only within that bucket, keeps every operation close to O(1).

Coach's boardthe pattern, step by step

THE BUCKET LINEPATTERN · BUCKETED HASH TABLE — OPSadd 1, add 2, contains 1, contains 3, add 2, contains 2, remove 2, contains 2

add 1

add 2

contains 1

contains 3

add 2

contains 2

remove 2

contains 2

SET CONTENTS

set → {}

STEP 1

Ops run against one live set, hashed into fixed buckets by key mod table size.

STEP 1 / 12 · ← → WORK TOO

The splitstwo paces, two languages

grind/design-hashset.py — RACE PACE

LANG ▸

PACE ▸

class MyHashSet:
    def __init__(self):
        self.buckets = 1000
        self.table = [[] for _ in range(self.buckets)]

    def _bucket(self, key: int) -> list:
        return self.table[key % self.buckets]

    def add(self, key: int) -> None:
        bucket = self._bucket(key)
        if key not in bucket:
            bucket.append(key)

    def remove(self, key: int) -> None:
        bucket = self._bucket(key)
        if key in bucket:
            bucket.remove(key)

    def contains(self, key: int) -> bool:
        return key in self._bucket(key)

TIME O(1) AVERAGE PER OPSPACE O(N + BUCKETS)PYTHON · RACE PACE · 20 LN

class MyHashSet:
    def __init__(self):
        self.items = []

    def add(self, key: int) -> None:
        if key not in self.items:
            self.items.append(key)

    def remove(self, key: int) -> None:
        if key in self.items:
            self.items.remove(key)

    def contains(self, key: int) -> bool:
        return key in self.items

TIME O(N) PER OPSPACE O(N)PYTHON · TRAINING PACE · 14 LN

class MyHashSet {
    private final List<Integer>[] table;
    private final int buckets = 1000;

    public MyHashSet() {
        table = new List[buckets];
        for (int i = 0; i < buckets; i++) {
            table[i] = new ArrayList<>();
        }
    }

    public void add(int key) {
        List<Integer> bucket = table[key % buckets];
        if (!bucket.contains(key)) {
            bucket.add(key);
        }
    }

    public void remove(int key) {
        table[key % buckets].remove(Integer.valueOf(key));
    }

    public boolean contains(int key) {
        return table[key % buckets].contains(key);
    }
}

TIME O(1) AVERAGE PER OPSPACE O(N + BUCKETS)JAVA · RACE PACE · 26 LN

class MyHashSet {
    private final List<Integer> items = new ArrayList<>();

    public MyHashSet() {
    }

    public void add(int key) {
        if (!items.contains(key)) {
            items.add(key);
        }
    }

    public void remove(int key) {
        items.remove(Integer.valueOf(key));
    }

    public boolean contains(int key) {
        return items.contains(key);
    }
}

TIME O(N) PER OPSPACE O(N)JAVA · TRAINING PACE · 20 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED