Python Chaining
I could write a 4-line solution, but I want to make sure I can write a well-thought out solution if I ever get asked this question in an interview. The question
I could write a 4-line solution, but I want to make sure I can write a well-thought out solution if I ever get asked this question in an interview. The question is trivial if we only have 10,000 possible values in our set, but if you\'re at Google and they process billions of web pages, you might run out of memory in your Hashset if you just use an array.\n\nImplementation: Create buckets with an array, each bucket has a linked list so you can delete and add in O(1) time. O(N) time for search. \n\nImprovement: I should add load factor rehashing in order to rehash if LF is above 3/4. Possible tradeoffs with red black tree instead of linked list. Add/delete/search is O(log N) for a red-black tree. If you are searching very rarely, it might be better to go with the linked list, otherwise maybe real world applications would do better with the tree? Not sure, but it might be worth mentioning in an interview. \n\nIt might be more helpful for LeetCode to limit the amount of buckets in the array so people don\'t pass the test case without thinking through the point of the problem. There is no point in doing problems just to get a green checkmark -- you should do problems to understand them so you can do well in the interview. \n\nAwesome answer in Java: https://leetcode.com/problems/design-hashset/discuss/249424/A-complete-Java-Solution-using-load-factor-BST-Rehashing!-Faster-than-90\n\n```\nclass ListNode(object):\n    def __init__(self,key,next):\n        self.key = key\n        self.next = next\n\nclass MyHashSet(object):\n\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.size = 10000\n        self.buckets = [None]*self.size\n\n    def add(self, key):\n        """\n        :type key: int\n        :rtype: None\n        """\n        bucketCode = key % self.size\n        cur = self.buckets[bucketCode]\n        if not cur: \n            self.buckets[bucketCode] = ListNode(key, None)\n            return\n        if cur.key == key:\n            return \n        while cur:\n            if cur.key == key: \n                return\n            if not cur.next: \n                cur.next = ListNode(key,None)\n                return \n            if cur.next: \n                cur = cur.next\n        return \n\n    def remove(self, key):\n        """\n        :type key: int\n        :rtype: None\n        """\n        bucketCode = key % self.size\n        cur = self.buckets[bucketCode]\n        if not cur:\n            return \n        if cur.key == key:\n            self.buckets[bucketCode] = cur.next\n        while cur.next:\n            if cur.next.key == key:\n                cur.next = cur.next.next\n                return \n            cur = cur.next\n        return\n        \n\n    def contains(self, key):\n        """\n        Returns true if this set contains the specified element\n        :type key: int\n        :rtype: bool\n        """\n        bucketCode = key % self.size\n        cur = self.buckets[bucketCode]\n        while cur:\n            if cur.key == key:\n                return True\n            cur = cur.next\n        return False\n```\n\n
[]