705. Design HashSet
Model: qwen2.5-coder:14b
Topics: Hash Table,Design
FAANG asked: 1
Acceptance rate: 64.5%
Problem Breakdown
The problem requires designing a HashSet data structure without using any built-in hash table libraries. The MyHashSet class should support three operations: add, remove, and contains. The add method inserts a key into the set, remove deletes a key from the set if it exists, and contains checks if a key is present in the set.
Inputs:
- Methods:
add(key),remove(key),contains(key) - Constraints:
0 <= key <= 10^6 - Maximum operations: At most
10^4calls
Outputs:
add: No return valueremove: No return valuecontains: Boolean indicating presence of the key
Implicit Constraints/Edge Cases:
- Duplicates: Adding a key that already exists should not change the set.
- Non-existent keys: Removing or checking for non-existent keys should handle gracefully without errors.
Intuition
A brute-force approach would involve using a list to store all elements and perform linear searches for add, remove, and contains operations. This approach is inefficient with time complexity of O(n) for each operation due to the need to scan through the entire list.
The key insight is to use an array-based hash set to achieve average constant time complexity for these operations. By using an array where each index represents a potential key value, we can quickly determine if a key exists and perform insertions or deletions efficiently.
Approach
- Data Structure Choice: Use an array of size
10^6 + 1(to cover the range of keys from 0 to 10^6) where each index corresponds to a potential key value. - Initialization: Initialize all elements in the array to
False, indicating that no keys are present initially. - Add Operation:
- Set the boolean value at the index corresponding to the key to
True.
- Set the boolean value at the index corresponding to the key to
- Remove Operation:
- Set the boolean value at the index corresponding to the key to
False.
- Set the boolean value at the index corresponding to the key to
- Contains Operation:
- Return the boolean value at the index corresponding to the key.
This approach leverages direct indexing, which provides average constant time complexity for all operations.
Complexity Analysis
- Time Complexity: O(1) for each of
add,remove, andcontainsoperations.- Direct array access is constant time.
- Space Complexity: O(n), where n is the range of possible keys (10^6 + 1 in this case).
- Fixed-size array to store boolean values.
Solution
class MyHashSet:
def __init__(self):
# Initialize an array of size 10^6 + 1 with all values set to False
self.size = 10**6 + 1
self.set = [False] * self.size
def add(self, key: int) -> None:
# Set the value at index 'key' to True
self.set[key] = True
def remove(self, key: int) -> None:
# Set the value at index 'key' to False
self.set[key] = False
def contains(self, key: int) -> bool:
# Return the value at index 'key'
return self.set[key]
Edge Cases Handled
- Adding a duplicate key: The
addmethod will not change the set since setting an alreadyTrueindex toTruehas no effect. - Removing a non-existent key: The
removemethod will not cause errors or alter the set since setting aFalseindex toFalseis harmless. - Checking for non-existent keys: The
containsmethod will correctly returnFalsefor keys that have never been added.