@@ -0,0 +1,2996 @@
+# Time:  O(1)%0A# Space: O(n)%0A%0A# Design a HashSet without using any built-in hash table libraries.%0A#%0A# To be specific, your design should include these two functions:%0A#%0A# add(value): Insert a value into the HashSet. %0A# contains(value) : Return whether the value exists in the HashSet or not.%0A# remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.%0A#%0A# Example:%0A#%0A# MyHashSet hashSet = new MyHashSet();%0A# hashSet.add(1);         %0A# hashSet.add(2);         %0A# hashSet.contains(1);    // returns true%0A# hashSet.contains(3);    // returns false (not found)%0A# hashSet.add(2);          %0A# hashSet.contains(2);    // returns true%0A# hashSet.remove(2);          %0A# hashSet.contains(2);    // returns false (already removed)%0A#%0A# Note:%0A# - All values will be in the range of %5B1, 1000000%5D.%0A# - The number of operations will be in the range of %5B1, 10000%5D.%0A# - Please do not use the built-in HashSet library.%0A%0A%0Aclass ListNode(object):%0A    def __init__(self, key, val):%0A        self.val = val%0A        self.key = key%0A        self.next = None%0A        self.prev = None%0A%0A%0Aclass LinkedList(object):%0A    def __init__(self):%0A        self.head = None%0A        self.tail = None%0A%0A    def insert(self, node):%0A        node.next, node.prev = None, None  # avoid dirty node%0A        if self.head is None:%0A            self.head = node%0A        else:%0A            self.tail.next = node%0A            node.prev = self.tail%0A        self.tail = node%0A%0A    def delete(self, node):%0A        if node.prev:%0A            node.prev.next = node.next%0A        else:%0A            self.head = node.next%0A        if node.next:%0A            node.next.prev = node.prev%0A        else:%0A            self.tail = node.prev%0A        node.next, node.prev = None, None  # make node clean%0A%0A    def find(self, key):%0A        curr = self.head%0A        while curr:%0A            if curr.key == key:%0A                break%0A            curr = curr.next%0A        return curr%0A%0A%0Aclass MyHashSet(object):%0A%0A    def __init__(self):%0A        %22%22%22%0A        Initialize your data structure here.%0A        %22%22%22%0A        self.__data = %5BLinkedList() for _ in xrange(10000)%5D%0A%0A    def add(self, key):%0A        %22%22%22%0A        :type key: int%0A        :rtype: void%0A        %22%22%22%0A        l = self.__data%5Bkey %25 len(self.__data)%5D%0A        node = l.find(key)%0A        if not node:%0A            l.insert(ListNode(key, 0))%0A%0A    def remove(self, key):%0A        %22%22%22%0A        :type key: int%0A        :rtype: void%0A        %22%22%22%0A        l = self.__data%5Bkey %25 len(self.__data)%5D%0A        node = l.find(key)%0A        if node:%0A            l.delete(node)%0A%0A    def contains(self, key):%0A        %22%22%22%0A        Returns true if this set did not already contain the specified element%0A        :type key: int%0A        :rtype: bool%0A        %22%22%22%0A        l = self.__data%5Bkey %25 len(self.__data)%5D%0A        node = l.find(key)%0A        return node is not None%0A%0A%0A# Your MyHashSet object will be instantiated and called as such:%0A# obj = MyHashSet()%0A# obj.add(key)%0A# obj.remove(key)%0A# param_3 = obj.contains(key)%0A

Create design-hashset.py