Design Hashset Problem


Description

LeetCode Problem 705.

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 to add, remove, and contains.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MyHashSet {
public:
    /** Initialize your data structure here. */
    int ht[1000000] = {0};
    
    MyHashSet() {
        
    }
    
    void add(int key) {
        ht[key] = 1;
    }
    
    void remove(int key) {
        ht[key] = 0;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        return ht[key];
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */




Related Posts

Time Based Key-Value Store Problem

LeetCode 981. Design a time-based key-value data structure that can...

Rle Iterator Problem

LeetCode 900. We can use run-length encoding (i.e., RLE) to...

Online Stock Span Problem

LeetCode 901. Design an algorithm that collects daily price quotes...

Online Election Problem

LeetCode 911. You are given two integer arrays persons and...

Number Of Recent Calls Problem

LeetCode 933. You have a RecentCounter class which counts the...

Maximum Frequency Stack Problem

LeetCode 895. Design a stack-like data structure to push elements...