Design a HashSet
Easy
5
41.3% Acceptance
Design and implement a HashSet without using any built-in hash table libraries in JavaScript. The main focus of this lab is to evaluate your understanding of hash table concepts and problem-solving skills.
A HashSet is a collection of unique elements. It supports add, remove, and contains operations. Your task is to implement the MyHashSet
class with the following methods:
void add(key)
Inserts the valuekey
into the HashSet.bool contains(key)
Returns whether the valuekey
exists in the HashSet or not.void remove(key)
Removes the valuekey
in the HashSet. Ifkey
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^6
- At most
10^4
calls will be made toadd
,remove
, andcontains
.
Examples
Example 2
myHashSet = new MyHashSet(); myHashSet.add(1); myHashSet.add(2); myHashSet.contains(1); // Expected output: true
Example 3
myHashSet = new MyHashSet(); myHashSet.add(1); myHashSet.add(2); myHashSet.contains(3); // Expected output: false
Example 4
myHashSet = new MyHashSet(); myHashSet.add(1); myHashSet.add(2); myHashSet.add(2); myHashSet.contains(2); // Expected output: true
Challenges
- Implement the
MyHashSet
class using Arrays. - Implement the
MyHashSet
class using Linked Lists. - Implement the
MyHashSet
class using a dynamic size to avoid collisions.
In each challenge, export the required functions and variables to be used in the evaluation script.