#705 Design HashSet

frequently reported atAmazon

the problem

In plain words

Build a set of integer keys without any built-in hash table. MyHashSet() creates an empty set, add(key) inserts a key (no duplicates), remove(key) deletes it if present, and contains(key) says whether it is there.

in add(1), add(2), contains(1), contains(3), add(2), contains(2), remove(2), contains(2)

out null, null, true, false, null, true, null, false

Adding 2 a second time changes nothing; after remove(2), contains(2) is false.

0 ≤ key ≤ 10⁶
At most 10⁴ calls to add, remove and contains

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternHash table from scratch (chaining)Class design: state + operations

where this runsjava.util.HashMap, and so HashSet, is an array of buckets holding chains of nodes: this design, plus resizing and tree bins.

You cannot afford to search every key on every call. Turn the key into a bucket number (key % buckets) so each call looks only at the few keys that share that bucket.

solutions

From brute force to optimal

Store the keys in a list and scan it.

add: append if contains is false.
remove: keys.remove(Integer.valueOf(key)).
contains: keys.contains(key) scans the list.

timeO(n) per call

contains walks up to n stored keys, and add and remove depend on it.

spaceO(n)

One boxed Integer per stored key.

javajava.util.*

1// On LeetCode, name this class MyHashSet.2class MyHashSetList {3    private final List<Integer> keys = new ArrayList<>();4 5    public void add(int key) {6        if (!keys.contains(key)) keys.add(key);      // contains walks the whole list: O(n)7    }8 9    public void remove(int key) {10        keys.remove(Integer.valueOf(key));           // remove(Object), NOT remove(int index)11    }12 13    public boolean contains(int key) {14        return keys.contains(key);15    }16}

Keys are small enough to be array indices.

add: present[key] = true.
remove: present[key] = false.
contains: return present[key].

timeO(1)

One array access per call.

spaceO(U), U = 10⁶ + 1

The array is sized by the key range, not by how many keys you store: 10⁶ + 1 flags even for 3 keys.

javajava.util.*

1// On LeetCode, name this class MyHashSet.2class MyHashSetArray {3    private final boolean[] present = new boolean[1_000_001];   // one flag per possible key (0..10^6)4 5    public void add(int key) {6        present[key] = true;7    }8 9    public void remove(int key) {10        present[key] = false;11    }12 13    public boolean contains(int key) {14        return present[key];15    }16}

An array of buckets; each bucket is a short linked chain of Nodes.

index = Math.floorMod(Integer.hashCode(key), buckets.length).
contains: walk that bucket's chain comparing keys.
add: if absent, push a new Node at the head of the chain.
remove: unlink the matching node, using a dummy node in front of the chain.

timeO(1) average, O(n) worst

With 10,007 buckets and at most 10⁴ keys the average chain holds about 1 node; if every key collided, one chain would hold all n.

spaceO(n + B)

n nodes plus B = 10,007 bucket references.

javajava.util.*

1class MyHashSet {2    private static class Node {                      // one link in a bucket's chain3        final int key;4        Node next;5 6        Node(int key, Node next) {7            this.key = key;8            this.next = next;9        }10    }11 12    private final Node[] buckets;13 14    public MyHashSet() {15        this(10_007);                                // a prime above the 10^4 calls: short chains16    }17 18    MyHashSet(int bucketCount) {                     // the 3D sim uses only a few buckets19        buckets = new Node[bucketCount];20    }21 22    private int indexOf(int key) {23        return Math.floorMod(Integer.hashCode(key), buckets.length);   // hashCode picks the bucket24    }25 26    public void add(int key) {27        if (contains(key)) return;                   // a set keeps one copy28        int i = indexOf(key);29        buckets[i] = new Node(key, buckets[i]);      // the new node becomes the chain's head30    }31 32    public void remove(int key) {33        int i = indexOf(key);34        Node dummy = new Node(-1, buckets[i]);       // a dummy head: removing the first node is not special35        for (Node prev = dummy; prev.next != null; prev = prev.next) {36            if (prev.next.key == key) {              // the equality check (for int keys, ==)37                prev.next = prev.next.next;38                break;39            }40        }41        buckets[i] = dummy.next;42    }43 44    public boolean contains(int key) {45        for (Node n = buckets[indexOf(key)]; n != null; n = n.next) {  // walk one short chain46            if (n.key == key) return true;47        }48        return false;49    }50}

sim

Dry run

loading simulation…

javajava.util.*

1class MyHashSet {2    private static class Node {                      // one link in a bucket's chain3        final int key;4        Node next;5 6        Node(int key, Node next) {7            this.key = key;8            this.next = next;9        }10    }11 12    private final Node[] buckets;13 14    public MyHashSet() {15        this(10_007);                                // a prime above the 10^4 calls: short chains16    }17 18    MyHashSet(int bucketCount) {                     // the 3D sim uses only a few buckets19        buckets = new Node[bucketCount];20    }21 22    private int indexOf(int key) {23        return Math.floorMod(Integer.hashCode(key), buckets.length);   // hashCode picks the bucket24    }25 26    public void add(int key) {27        if (contains(key)) return;                   // a set keeps one copy28        int i = indexOf(key);29        buckets[i] = new Node(key, buckets[i]);      // the new node becomes the chain's head30    }31 32    public void remove(int key) {33        int i = indexOf(key);34        Node dummy = new Node(-1, buckets[i]);       // a dummy head: removing the first node is not special35        for (Node prev = dummy; prev.next != null; prev = prev.next) {36            if (prev.next.key == key) {              // the equality check (for int keys, ==)37                prev.next = prev.next.next;38                break;39            }40        }41        buckets[i] = dummy.next;42    }43 44    public boolean contains(int key) {45        for (Node n = buckets[indexOf(key)]; n != null; n = n.next) {  // walk one short chain46            if (n.key == key) return true;47        }48        return false;49    }50}

in the room

How to say it in the interview

talk track

Clarify the key range and the number of calls. With keys ≤ 10⁶, mention that a boolean array works but grows with the range, not the data.
Explain the two steps of every hash table: hashCode picks the bucket, an equality check confirms inside it.
Pick a prime bucket count near the expected number of keys, and say what happens on a collision (chaining).
Offer the follow-up yourself: resize (double the buckets) when size / buckets passes a load factor like 0.75.

traps

key % n is negative for a negative hash; Math.floorMod never is.
Removing the first node of a chain without a dummy node needs its own special case.
list.remove(key) with an int on a List<Integer> removes by index, not by value.

what they ask next

Follow-ups

How would you support resizing?

Track the size. When size / buckets passes 0.75, allocate twice as many buckets and re-insert every node (rehash). One resize is O(n), but sizes double, so add stays O(1) amortized. java.util.HashMap does the same with a default load factor of 0.75.

What if the keys were Strings?

Use key.hashCode() instead of Integer.hashCode(key) and compare with equals instead of ==. Everything else stays the same.

before you submit

Edge cases to test

Adding a key that is already present (still one copy).
Removing a key that was never added.
Keys 0 and 1,000,000, the two ends of the range.
Many keys in the same bucket (multiples of the bucket count).

practise next