Skip to main content

705. Design HashSet

easy

Implement a HashSet from scratch without built-in hash-table libraries. The thinner cousin of Design HashMap — only needs to store keys, not key-value pairs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design a HashSet without using any built-in hash table libraries. Implement MyHashSet class: void add(key) Inserts the value key into the HashSet. bool contains(key) Returns whether the value key exists in the HashSet or not. void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Constraints

  • 0 <= key <= 10^6
  • At most 10^4 calls will be made to add, remove, and contains.

Examples

Example 1

Input
['MyHashSet','add','add','contains','contains','add','contains','remove','contains']
[[],[1],[2],[1],[3],[2],[2],[2],[2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation: MyHashSet myHashSet = new MyHashSet(); myHashSet.add(1); myHashSet.add(2); myHashSet.contains(1) returns true; myHashSet.contains(3) returns false; myHashSet.add(2) (no-op since 2 already in); myHashSet.contains(2) returns true; myHashSet.remove(2); myHashSet.contains(2) returns false.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Same chaining structure as Design HashMap — but each bucket holds only keys, not key-value pairs.

Hint 2

Hash function: index = key % B for a fixed bucket count B.

Hint 3

add scans the bucket and skips duplicates; remove walks and splices; contains is a linear walk of the bucket.

Solution approach

Reveal approach

Chained open hashing. Choose a bucket count B (1000 works for the given constraint). Maintain buckets: list of length B, each entry a list of keys. Hash: index = key % B. add(k): walk buckets[hash(k)]; if k not present, append. contains(k): walk and return whether k was found. remove(k): walk and splice-out if found. All ops are amortized O(N / B), effectively O(1) when B is chosen reasonably. Memory: O(B + N). The implementation is one screen of code; the only thing to watch is consistency of the linear-walk pattern across add/contains/remove so they agree on equality semantics.

Complexity

Time
amortized O(1) per op
Space
O(B + N)

Related patterns

  • hash-table
  • hash-set
  • design
  • linked-list

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Design HashSet and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →