705. Design HashSet

Easy


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 <= 106
  • At most 104 calls will be made to add, remove, and contains.




 class Bucket:
    def __init__(self):
        #self.list = []
        self.head = Node(0) # pseudo Head

    def add(self, key):
        if not self.contains(key):
            #self.list.append(key)
            self.head.next = Node(key, self.head.next)


    def remove(self, key):
        # for i in self.list:
        #     if i == key:
        #         self.list.remove(i)
        #         break
        prev = self.head
        current = self.head.next
        while current is not None:
            if current.val == key:
                prev.next = current.next
                return
            prev = current
            current = current.next

    def contains(self, key):
        # for i in self.list:
        #     if i == key:
        #         return True
        # return False
        current = self.head.next
        while current is not None:
            if current.val == key:
                return True
            current = current.next
        return False

class Node:
    def __init__(self, val, next_node = None):
        self.val = val
        self.next = next_node

class MyHashSet:

    def __init__(self):
        self.key = 769
        self.buckets = [Bucket() for i in range(self.key)]


    def add(self, key: int) -> None:
        hash_key = key%self.key
        self.buckets[hash_key].add(key)


    def remove(self, key: int) -> None:
        hash_key = key%self.key
        self.buckets[hash_key].remove(key)


    def contains(self, key: int) -> bool:
        hash_key = key%self.key
        return self.buckets[hash_key].contains(key)



# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)

Random Note


From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict