Jobs

Interviews

Discussions

Design HashSet

Easy

Asked by:

27 views

Topics:

ArraysLinked Lists

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.

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); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // return True myHashSet.contains(3); // return False, (not found) myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // return True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // return False, (already removed)

Constraints:

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

Try coding it in LeetCode

Design HashSet

Easy

Asked by:

27 views

Topics:

ArraysLinked Lists

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.

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); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // return True myHashSet.contains(3); // return False, (not found) myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // return True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // return False, (already removed)

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The constraints specify that keys are integers between 0 and 1,000,000. Should my design be optimized specifically for this fixed, non-negative integer range?
Given the maximum key value, is a solution that uses memory proportional to this range (approximately 1MB) acceptable, or should I prioritize a design where memory usage scales with the number of elements actually stored?
When implementing the hashing mechanism, do you have a preference for the collision resolution strategy, for instance, separate chaining with linked lists versus open addressing techniques like linear probing?
Should the design account for dynamic resizing or 'rehashing' to maintain performance if the load factor becomes too high?
Can I assume that the keys will be uniformly distributed, or should the design be robust against scenarios that might lead to a high number of hash collisions, such as clustered key inputs?

Brute Force Solution

Approach

The simplest approach is to maintain a basic collection of all the numbers that have been added. Every time we need to perform an action, like adding, removing, or checking for a number, we will exhaustively search through every single item in our collection to get the answer.

Here's how the algorithm would work step-by-step:

Imagine our set is just one simple list where we store all the unique numbers.
When asked to add a new number, we first have to make sure it's not already in our list to avoid duplicates.
To do this, we must look at every single number we are already storing, one by one, from the very beginning.
If we find the number is already there, we do nothing. If we check all our numbers and don't find it, we then add the new number to our collection.
To check if a specific number exists, we must again perform a complete search through our list.
We compare the number we're looking for against each number in our collection until we either find a match or have checked everything.
Similarly, to remove a number, we first have to find it by searching the entire collection, and if we find a match, we take that number out.

Code Implementation

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

    def add(self, key: int) -> None:
        # To maintain uniqueness, we must first check if the number already exists in our set.
        is_key_present = self.contains(key)
        if not is_key_present:
            self.storage_list.append(key)

    def remove(self, key: int) -> None:
        # A linear scan is necessary to find the item's index before it can be removed.
        for current_index in range(len(self.storage_list)):
            if self.storage_list[current_index] == key:
                self.storage_list.pop(current_index)
                return

    def contains(self, key: int) -> bool:
        # Because the data is unsorted, a full scan is required to check for the key's existence.
        for existing_key in self.storage_list:
            if existing_key == key:
                return True
        return False

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of elements currently in the set. For any given operation, whether it is adding, removing, or checking for an element, the described approach requires an exhaustive search of the entire collection. This search is the primary driver of the cost, as it involves iterating through all n stored elements one by one. In the worst-case scenario, such as adding a new unique element or searching for a non-existent one, we must check every single item. Therefore, the total number of operations is directly proportional to n, which simplifies to a time complexity of O(n).

Space Complexity

O(N) – The space complexity is determined by the 'simple list' used to store the set's elements. Let N be the number of unique elements added to the HashSet. The list must allocate memory for each of these N elements, causing its size to grow linearly with the number of items stored. No other significant data structures are used, so the total auxiliary space is directly proportional to the count of unique elements in the set.

Optimal Solution

Approach

The core idea is to avoid searching through a single, massive list of numbers. Instead, we use a clever organizational system, like a set of filing cabinets, to instantly determine the correct small 'cabinet' or 'bucket' a number belongs to. This makes finding, adding, or removing a number extremely fast, as we only ever have to look in one small, specific place.

Here's how the algorithm would work step-by-step:

First, set up a large, fixed number of empty containers, which we'll call buckets.
When a request comes in to add, remove, or find a specific number, we don't look through all the buckets.
Instead, we use a special, consistent calculation on the number itself. A common method is to see what the remainder is when the number is divided by our total number of buckets.
This calculation's result instantly tells us the one and only bucket that this number could possibly be in.
To add a number, we go to its designated bucket. We only check inside this small bucket to see if the number is already there before adding it.
To see if a number is present, we perform the same calculation, go to the correct bucket, and just look inside that one.
This strategy is highly efficient because we're always working with a tiny list inside one bucket, rather than searching through every single number we've ever stored.

Code Implementation

class MyHashSet:
    def __init__(self):
        self.number_of_buckets = 1000
        # To handle collisions, each bucket is a list capable of storing multiple hashed values.

        self.buckets = [[] for _ in range(self.number_of_buckets)]

    def add(self, key_value: int) -> None:
        # The modulo operator is a simple hash function to map a key to a specific bucket index.

        bucket_index = key_value % self.number_of_buckets
        designated_bucket = self.buckets[bucket_index]
        # We must check for the key's existence before adding to maintain the set's uniqueness property.

        if key_value not in designated_bucket:
            designated_bucket.append(key_value)

    def remove(self, key_value: int) -> None:
        bucket_index = key_value % self.number_of_buckets
        designated_bucket = self.buckets[bucket_index]
        if key_value in designated_bucket:
            designated_bucket.remove(key_value)

    def contains(self, key_value: int) -> bool:
        bucket_index = key_value % self.number_of_buckets
        designated_bucket = self.buckets[bucket_index]
        # Searching a small bucket list is much faster than scanning all stored elements.

        return key_value in designated_bucket

Big(O) Analysis

Time Complexity

O(1) – The cost of any operation is driven by finding the correct bucket and then searching within it. The bucket is located in constant time using a hash calculation, which is a single modulo operation. The core design assumption is that keys are distributed evenly, so the number of items to check within any single bucket is very small and does not grow with the total number of elements, n, in the set. This makes the search within the bucket a constant time operation, resulting in an overall average time complexity of O(1).

Space Complexity

O(K + N) – The space complexity is determined by two main components described in the solution. First, a fixed number of 'buckets' are initialized, let's call this number K, which requires O(K) space for the container array itself. Second, the structure must store all the unique numbers that are added. If N is the total number of unique elements inserted into the HashSet, an additional O(N) space is needed to hold these values within the buckets. The total space is therefore the sum of the space for the bucket array and the space for the stored elements, resulting in O(K + N).

Edge Cases

Case	How to Handle
Multiple keys mapping to the same hash bucket (hash collisions)	Use a secondary data structure like a linked list in each bucket to store all colliding keys.
Calling 'add' with a key that is already present in the HashSet	The implementation must first check for the key's existence within its designated bucket to avoid storing duplicates.
Calling 'remove' with a key that is not in the HashSet	The operation should complete without error or state change, as the key to be removed is not present.
Operations involving the minimum (0) and maximum (10^6) possible key values	The hash function and underlying array must correctly handle indices corresponding to the full range of keys.
A sequence of inputs where all keys hash to the same bucket	The chaining mechanism ensures correctness, but performance for all operations degrades to be linear in the number of items in that bucket.
A key is added, then removed, and then checked for existence	The final 'contains' call must return false, correctly reflecting the successful removal of the key.
Calling 'contains' or 'remove' immediately after initialization on an empty set	The data structure should be properly initialized to an empty state, causing these operations to have no effect and return correctly.
The large range of key values (up to 10^6) versus the number of calls (10^4)	A direct-addressing table (a boolean array of size 10^6+1) is a simple and efficient solution due to the key range, avoiding hash logic entirely.

Multiple keys mapping to the same hash bucket (hash collisions)

How to Handle:

Use a secondary data structure like a linked list in each bucket to store all colliding keys.

Calling 'add' with a key that is already present in the HashSet

How to Handle:

The implementation must first check for the key's existence within its designated bucket to avoid storing duplicates.

Calling 'remove' with a key that is not in the HashSet

How to Handle:

The operation should complete without error or state change, as the key to be removed is not present.

Operations involving the minimum (0) and maximum (10^6) possible key values

How to Handle:

The hash function and underlying array must correctly handle indices corresponding to the full range of keys.

A sequence of inputs where all keys hash to the same bucket

How to Handle:

The chaining mechanism ensures correctness, but performance for all operations degrades to be linear in the number of items in that bucket.

A key is added, then removed, and then checked for existence

How to Handle:

The final 'contains' call must return false, correctly reflecting the successful removal of the key.

Calling 'contains' or 'remove' immediately after initialization on an empty set

How to Handle:

The data structure should be properly initialized to an empty state, causing these operations to have no effect and return correctly.

The large range of key values (up to 10^6) versus the number of calls (10^4)

How to Handle:

A direct-addressing table (a boolean array of size 10^6+1) is a simple and efficient solution due to the key range, avoiding hash logic entirely.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The constraints specify that keys are integers between 0 and 1,000,000. Should my design be optimized specifically for this fixed, non-negative integer range?
Given the maximum key value, is a solution that uses memory proportional to this range (approximately 1MB) acceptable, or should I prioritize a design where memory usage scales with the number of elements actually stored?
When implementing the hashing mechanism, do you have a preference for the collision resolution strategy, for instance, separate chaining with linked lists versus open addressing techniques like linear probing?
Should the design account for dynamic resizing or 'rehashing' to maintain performance if the load factor becomes too high?
Can I assume that the keys will be uniformly distributed, or should the design be robust against scenarios that might lead to a high number of hash collisions, such as clustered key inputs?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine our set is just one simple list where we store all the unique numbers.
When asked to add a new number, we first have to make sure it's not already in our list to avoid duplicates.
To do this, we must look at every single number we are already storing, one by one, from the very beginning.
If we find the number is already there, we do nothing. If we check all our numbers and don't find it, we then add the new number to our collection.
To check if a specific number exists, we must again perform a complete search through our list.
We compare the number we're looking for against each number in our collection until we either find a match or have checked everything.
Similarly, to remove a number, we first have to find it by searching the entire collection, and if we find a match, we take that number out.

Code Implementation

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

    def add(self, key: int) -> None:
        # To maintain uniqueness, we must first check if the number already exists in our set.
        is_key_present = self.contains(key)
        if not is_key_present:
            self.storage_list.append(key)

    def remove(self, key: int) -> None:
        # A linear scan is necessary to find the item's index before it can be removed.
        for current_index in range(len(self.storage_list)):
            if self.storage_list[current_index] == key:
                self.storage_list.pop(current_index)
                return

    def contains(self, key: int) -> bool:
        # Because the data is unsorted, a full scan is required to check for the key's existence.
        for existing_key in self.storage_list:
            if existing_key == key:
                return True
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, set up a large, fixed number of empty containers, which we'll call buckets.
When a request comes in to add, remove, or find a specific number, we don't look through all the buckets.
Instead, we use a special, consistent calculation on the number itself. A common method is to see what the remainder is when the number is divided by our total number of buckets.
This calculation's result instantly tells us the one and only bucket that this number could possibly be in.
To add a number, we go to its designated bucket. We only check inside this small bucket to see if the number is already there before adding it.
To see if a number is present, we perform the same calculation, go to the correct bucket, and just look inside that one.
This strategy is highly efficient because we're always working with a tiny list inside one bucket, rather than searching through every single number we've ever stored.

Code Implementation

class MyHashSet:
    def __init__(self):
        self.number_of_buckets = 1000
        # To handle collisions, each bucket is a list capable of storing multiple hashed values.

        self.buckets = [[] for _ in range(self.number_of_buckets)]

    def add(self, key_value: int) -> None:
        # The modulo operator is a simple hash function to map a key to a specific bucket index.

        bucket_index = key_value % self.number_of_buckets
        designated_bucket = self.buckets[bucket_index]
        # We must check for the key's existence before adding to maintain the set's uniqueness property.

        if key_value not in designated_bucket:
            designated_bucket.append(key_value)

    def remove(self, key_value: int) -> None:
        bucket_index = key_value % self.number_of_buckets
        designated_bucket = self.buckets[bucket_index]
        if key_value in designated_bucket:
            designated_bucket.remove(key_value)

    def contains(self, key_value: int) -> bool:
        bucket_index = key_value % self.number_of_buckets
        designated_bucket = self.buckets[bucket_index]
        # Searching a small bucket list is much faster than scanning all stored elements.

        return key_value in designated_bucket

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Multiple keys mapping to the same hash bucket (hash collisions)	Use a secondary data structure like a linked list in each bucket to store all colliding keys.
Calling 'add' with a key that is already present in the HashSet	The implementation must first check for the key's existence within its designated bucket to avoid storing duplicates.
Calling 'remove' with a key that is not in the HashSet	The operation should complete without error or state change, as the key to be removed is not present.
Operations involving the minimum (0) and maximum (10^6) possible key values	The hash function and underlying array must correctly handle indices corresponding to the full range of keys.
A sequence of inputs where all keys hash to the same bucket	The chaining mechanism ensures correctness, but performance for all operations degrades to be linear in the number of items in that bucket.
A key is added, then removed, and then checked for existence	The final 'contains' call must return false, correctly reflecting the successful removal of the key.
Calling 'contains' or 'remove' immediately after initialization on an empty set	The data structure should be properly initialized to an empty state, causing these operations to have no effect and return correctly.
The large range of key values (up to 10^6) versus the number of calls (10^4)	A direct-addressing table (a boolean array of size 10^6+1) is a simple and efficient solution due to the key range, avoiding hash logic entirely.

Multiple keys mapping to the same hash bucket (hash collisions)

How to Handle:

Use a secondary data structure like a linked list in each bucket to store all colliding keys.

Calling 'add' with a key that is already present in the HashSet

How to Handle:

The implementation must first check for the key's existence within its designated bucket to avoid storing duplicates.

Calling 'remove' with a key that is not in the HashSet

How to Handle:

The operation should complete without error or state change, as the key to be removed is not present.

Operations involving the minimum (0) and maximum (10^6) possible key values

How to Handle:

The hash function and underlying array must correctly handle indices corresponding to the full range of keys.

A sequence of inputs where all keys hash to the same bucket

How to Handle:

The chaining mechanism ensures correctness, but performance for all operations degrades to be linear in the number of items in that bucket.

A key is added, then removed, and then checked for existence

How to Handle:

The final 'contains' call must return false, correctly reflecting the successful removal of the key.

Calling 'contains' or 'remove' immediately after initialization on an empty set

How to Handle:

The data structure should be properly initialized to an empty state, causing these operations to have no effect and return correctly.

The large range of key values (up to 10^6) versus the number of calls (10^4)

How to Handle:

A direct-addressing table (a boolean array of size 10^6+1) is a simple and efficient solution due to the key range, avoiding hash logic entirely.