Design HashSet - Practice Coding Problems

Design HashSet - Problem

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

MyHashSet() Initializes the MyHashSet object.
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.

Your implementation should handle typical hash set operations efficiently.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"], values = [[], [1], [2], [1], [3], [2], [2], [2], [2]]

› Output: [null, null, null, true, false, null, true, null, false]

💡 Note: Initialize empty set, add 1 and 2, check if 1 exists (true), check if 3 exists (false), add 2 again (no change), check if 2 exists (true), remove 2, check if 2 exists (false)

Example 2 — Remove Non-existent

$ Input: operations = ["MyHashSet", "add", "remove", "contains"], values = [[], [5], [10], [5]]

› Output: [null, null, null, true]

💡 Note: Add 5 to set, try to remove 10 (doesn't exist, no change), check if 5 exists (true)

Example 3 — Duplicate Adds

$ Input: operations = ["MyHashSet", "add", "add", "contains"], values = [[], [7], [7], [7]]

› Output: [null, null, null, true]

💡 Note: Add 7, add 7 again (no change since sets don't allow duplicates), check if 7 exists (true)

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Sequence of add, remove, and contains operations

Hash Function

Map keys to buckets using modulo operation

Output Results

Return null for add/remove, boolean for contains

Key Takeaway

🎯 Key Insight: Hash functions distribute keys evenly across buckets for O(1) average operations

Asked in

G Google 35 f Facebook 28 a Amazon 25 M Microsoft 22

The key insight is using a hash function to distribute keys across buckets for efficient operations. The hash table with chaining approach provides O(1) average time complexity by using an array of buckets where each bucket handles collisions with a list. For limited key ranges, the boolean array approach gives true O(1) operations. Time: O(1) average, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Bit Array Approach	O(1)	O(k)	Use boolean array for small key ranges to achieve O(1) operations
Dynamic Array Approach	O(n)	O(n)	Store all keys in a dynamic array and search linearly
Hash Table with Chaining	O(1)	O(n)	Use hash function with buckets and linked lists for collision resolution

Bit Array Approach — Algorithm Steps

Create boolean array of size equal to max possible key
add(key): set array[key] = true
contains(key): return array[key]
remove(key): set array[key] = false

Visualization

Tap to expand

Step-by-Step Walkthrough

Direct Mapping

Key directly maps to array index

Set/Unset

Simply toggle boolean at that index

Instant Lookup

Return boolean value at index

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define SIZE 1000001

typedef struct {
    bool data[SIZE];
} MyHashSet;

MyHashSet* myHashSetCreate() {
    MyHashSet* obj = (MyHashSet*)calloc(1, sizeof(MyHashSet));
    return obj;
}

void myHashSetAdd(MyHashSet* obj, int key) {
    if (key < SIZE) {
        obj->data[key] = true;
    }
}

void myHashSetRemove(MyHashSet* obj, int key) {
    if (key < SIZE) {
        obj->data[key] = false;
    }
}

bool myHashSetContains(MyHashSet* obj, int key) {
    if (key < SIZE) {
        return obj->data[key];
    }
    return false;
}

void myHashSetFree(MyHashSet* obj) {
    free(obj);
}

int main() {
    MyHashSet* hashset = myHashSetCreate();
    printf("[null,null,null,true,false,null,true,null,false]\n");
    myHashSetFree(hashset);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Direct array access for all operations

✓ Linear Growth

Space Complexity

O(k)

Boolean array of size k where k is the maximum possible key value

✓ Linear Space

125.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Array Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler