Implement a data structure supporting the following operations:



Inc(Key) - Inserts a new key  with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".




Challenge: Perform all these in O(1) time complexity.

Difficulty: interview

Starter code:

class AllOne:
    def __init__(self):
        """
        Initialize your data structure here.
        """
    def inc(self, key: str) -> None:
        """
        Inserts a new key <key> with value 1. Or increments an existing key by 1.
        """
    def dec(self, key: str) -> None:
        """
        Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
        """
    def getMaxKey(self) -> str:
        """
        Returns one of the keys with maximal value.
        """
    def getMinKey(self) -> str:
        """
        Returns one of the keys with Minimal value.
        """
# Your AllOne object will be instantiated and called as such:
# obj = AllOne()
# obj.inc(key)
# obj.dec(key)
# param_3 = obj.getMaxKey()
# param_4 = obj.getMinKey()</key>

Solutions:
class DLL:
     
     def __init__(self, val, key):
         self.val = val
         self.key = key
         self.next = None
         self.prev = None
 
 class AllOne:
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.hash = {}
         self.head = None
         self.tail = None
 
     def inc(self, key):
         """
         Inserts a new key <Key> with value 1. Or increments an existing key by 1.
         :type key: str
         :rtype: void
         """
         self.print_dll()
         dll = self.hash.get(key, None)
         if not dll:
             dll = DLL(1, key)
             self.insert_dll(dll)
             self.hash[key] = dll
         else:
             self.incr_dll(dll)  
         
 
     def dec(self, key):
         """
         Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
         :type key: str
         :rtype: void
         """
         self.print_dll()
         dll = self.hash.get(key, None)
         if not dll:return
         self.decr_dll(dll)
         if dll.val == 0:
             del self.hash[key]
         
 
     def getMaxKey(self):
         """
         Returns one of the keys with maximal value.
         :rtype: str
         """
         if self.head:
             return self.head.key
         return ""
         
 
     def getMinKey(self):
         """
         Returns one of the keys with Minimal value.
         :rtype: str
         """
         if self.tail:
             return self.tail.key
         return ""
         
     def insert_dll(self, dll):
         if self.tail:
             self.tail.next = dll
             self.tail.next.prev = self.tail
             self.tail = dll
         else:
             self.head = dll
             self.tail = dll
         
     def incr_dll(self, dll):
         dll.val = dll.val + 1
         while dll.prev and dll.val > dll.prev.val:
             
             prev = dll.prev
             prev_prev = dll.prev.prev
             next_node = dll.next
             
             dll.next = prev
             prev.next = next_node
             dll.prev = prev_prev
             prev.prev = dll
             
             if prev_prev:
                 prev_prev.next = dll
             else:
                 self.head = dll
             
             if next_node:
                 next_node.prev = prev
             else:
                 self.tail = prev
                 
             
     def decr_dll(self, dll):
         dll.val = dll.val - 1
         if dll.val == 0 :
             if dll.prev:
                 dll.prev.next = dll.next
             else:
                 self.head = dll.next
                                 
             if dll.next:
                 dll.next.prev = dll.prev
             else:
                 self.tail = dll.prev
         
         elif dll.next and dll.val < dll.next.val:
             next_node = dll.next
             next_next = dll.next.next
             prev = dll.prev
             
             dll.next = next_next
             dll.prev = next_node
             
             next_node.next = dll
             next_node.prev = prev
             
             if next_next:
                 next_next.prev = dll
             else:
                 self.tail = dll
             if prev:
                 prev.next = next_node
             else:
                 self.head = next_node
                 
     def print_dll(self):
         temp = self.head
         # while temp:
         #     print("%s %s" % (temp.key, str(temp.val)))
         #     temp = temp.next
         # print("End")
 
 
             
             
                 
 
 
 
 # Your AllOne object will be instantiated and called as such:
 # obj = AllOne()
 # obj.inc(key)
 # obj.dec(key)
 # param_3 = obj.getMaxKey()
 # param_4 = obj.getMinKey()

from collections import defaultdict
 
 
 class Node(object):
     def __init__(self, val, key, prev=None, next=None):
         self.val = val
         self.keys = set()
         self.keys.add(key)
         self.prev = prev
         if prev is not None:
             prev.next = self
         self.next = next
         if next is not None:
             next.prev = self
 
 
 class AllOne(object):
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.head = None
         self.tail = None
         self.key2node = dict()
 
     def check_delete(self, node):
         if len(node.keys) == 0:
             prev = node.prev
             next = node.next
             if prev is None:  # node is self.head
                 if next is None:
                     self.head = None
                     self.tail = None
                 else:
                     self.head = next
                     self.head.prev = None
             else:
                 if next is None:  # node is self.tail
                     self.tail = prev
                     self.tail.next = None
                 else:
                     prev.next = next
                     next.prev = prev
 
     def inc(self, key):
         """
         Inserts a new key <Key> with value 1. Or increments an existing key by 1.
         :type key: str
         :rtype: void
         """
         if key not in self.key2node:
             if self.head is None:
                 new_node = Node(1, key)
                 self.head = new_node
                 self.tail = new_node
                 self.key2node[key] = new_node
             elif self.head.val == 1:
                 self.head.keys.add(key)
                 self.key2node[key] = self.head
             else:
                 new_node = Node(1, key, next=self.head)
                 self.head = new_node
                 self.head.prev = None
                 self.key2node[key] = new_node
         else:
             node = self.key2node[key]
             del self.key2node[key]
             node.keys.remove(key)
             next_node = node.next
             if next_node is None:  # node is self.tail
                 next_node = Node(node.val + 1, key, prev=node)
                 self.tail = next_node
                 self.tail.next = None
             elif next_node.val == node.val + 1:
                 next_node.keys.add(key)
             else:
                 next_node = Node(node.val + 1, key, prev=node, next=next_node)
 
             self.check_delete(node)
             self.key2node[key] = next_node
 
     def dec(self, key):
         """
         Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
         :type key: str
         :rtype: void
         """
         if key not in self.key2node:
             return
 
         node = self.key2node[key]
         del self.key2node[key]
         node.keys.remove(key)
         prev_node = node.prev
         if prev_node is None:  # node is self.head
             if node.val != 1:
                 new_node = Node(node.val - 1, key, next=node)
                 self.head = new_node
                 self.head.prev = None
                 self.key2node[key] = new_node
         elif prev_node.val == node.val - 1:
             prev_node.keys.add(key)
             self.key2node[key] = prev_node
         else:
             new_node = Node(node.val - 1, key, prev=prev_node, next=node)
             self.key2node[key] = new_node
 
         self.check_delete(node)
 
     def getMaxKey(self):
         """
         Returns one of the keys with maximal value.
         :rtype: str
         """
         return '' if self.tail is None else next(iter(self.tail.keys))
         
 
     def getMinKey(self):
         """
         Returns one of the keys with Minimal value.
         :rtype: str
         """
         return '' if self.head is None else next(iter(self.head.keys))



 class Node:
     def __init__(self, cnt):
         self.count = cnt
         self.prev = None
         self.next = None
 
 
 class AllOne(object):
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         self.count_key_map={}
         self.key_count_map={}
         self.count_node_map={}
         
         self.head=Node(0)
         self.tail=Node(float('inf'))
         
         self.head.next=self.tail
         self.tail.prev=self.head
         
         self.count_node_map[0]=self.head
         self.count_node_map[float('inf')]=self.tail
 
     def inc(self, key):
         """
         Inserts a new key <Key> with value 1. Or increments an existing key by 1.
         :type key: str
         :rtype: void
         """
         if key not in self.key_count_map:
             self.key_count_map[key]=0
         
         
         prev_count=self.key_count_map[key]
         prev_node=self.count_node_map[prev_count]
         
         self.key_count_map[key]+=1
         
         if prev_node.next.count!=self.key_count_map[key]:
             new_node=Node(self.key_count_map[key])
             self.insert(prev_node,new_node)
             self.count_key_map[self.key_count_map[key]]=set()
             self.count_node_map[self.key_count_map[key]]=new_node
         
         self.count_key_map[self.key_count_map[key]].add(key)
         
         if prev_count!=0:
            
            self.count_key_map[prev_count].remove(key)
            if len(self.count_key_map[prev_count])==0:
                self.count_node_map.pop(prev_count)
                self.count_key_map.pop(prev_count)
                self.delete(prev_node)
                
     
         
 
     def dec(self, key):
         """
         Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
         :type key: str
         :rtype: void
         """
         if key not in self.key_count_map:
             return 
         prev_count=self.key_count_map[key]
         prev_node=self.count_node_map[prev_count]
         
         self.key_count_map[key]-=1
         
         
         if self.key_count_map[key]==0:
            self.key_count_map.pop(key)
         else:
             if prev_node.prev.count!=self.key_count_map[key]:
                 new_node=Node(self.key_count_map[key])
                 self.insert(prev_node.prev,new_node)
                 self.count_key_map[self.key_count_map[key]]=set()
                 self.count_node_map[self.key_count_map[key]]=new_node
         
             self.count_key_map[self.key_count_map[key]].add(key) 
             
             
         self.count_key_map[prev_count].remove(key)
         if len(self.count_key_map[prev_count])==0:
                self.delete(prev_node)
                self.count_node_map.pop(prev_count)
                self.count_key_map.pop(prev_count)
             
     def getMaxKey(self):
         """
         Returns one of the keys with maximal value.
         :rtype: str
         """
         if self.head.next == self.tail:
             return ""
         x = self.count_key_map[self.tail.prev.count].pop()
         self.count_key_map[self.tail.prev.count].add(x)
         return x
         
 
     def getMinKey(self):
         """
         Returns one of the keys with Minimal value.
         :rtype: str
         """
         if self.head.next == self.tail:
             return ""
         x = self.count_key_map[self.head.next.count].pop()
         self.count_key_map[self.head.next.count].add(x)
         return x
         
     #insert 'node' after prev_node O(1) 
     def insert(self, prev_node, node):
         node.next = prev_node.next
         node.prev = prev_node
         
         node.next.prev = node
         node.prev.next = node
         
     def delete(self, node):
         node.next.prev = node.prev
         node.prev.next = node.next


 class Node:
     def __init__(self, cnt):
         self.count = cnt
         self.prev = None
         self.next = None
 
 
 class AllOne(object):
 
     def __init__(self):
         """
         Initialize your data structure here.
         """
         #Key:count, Value:set of key who has been incremented by 'count' time
         self.count_key_map = {}
         #Key:key, Value: the number of counts of this key
         self.key_count_map = {}
         #Key: the count, Value: the node
         self.count_node_map = {}
         
         #initialize the linkedlist with dummy node
         self.head = Node(0)
         self.tail = Node(float('inf'))
         self.head.next = self.tail
         self.tail.prev = self.head
         
         self.count_node_map[0] = self.head
         self.count_node_map[float('inf')] = self.tail
 
     def inc(self, key):
         """
         Inserts a new key <Key> with value 1. Or increments an existing key by 1.
         :type key: str
         :rtype: void
         """
         if key not in self.key_count_map:
             self.key_count_map[key]=0
         
         
         prev_count=self.key_count_map[key]
         prev_node=self.count_node_map[prev_count]
         
         self.key_count_map[key]+=1
         
         if prev_node.next.count!=self.key_count_map[key]:
             new_node=Node(self.key_count_map[key])
             self.insert(prev_node,new_node)
             self.count_key_map[self.key_count_map[key]]=set()
             self.count_node_map[self.key_count_map[key]]=new_node
         
         self.count_key_map[self.key_count_map[key]].add(key)
         
         if prev_count!=0:
            
            self.count_key_map[prev_count].remove(key)
            if len(self.count_key_map[prev_count])==0:
                self.count_node_map.pop(prev_count)
                self.count_key_map.pop(prev_count)
                self.delete(prev_node)
                
     
         
 
     def dec(self, key):
         """
         Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
         :type key: str
         :rtype: void
         """
         if key not in self.key_count_map:
             return 
         prev_count=self.key_count_map[key]
         prev_node=self.count_node_map[prev_count]
         
         self.key_count_map[key]-=1
         
         
         if self.key_count_map[key]==0:
            self.key_count_map.pop(key)
         else:
             if prev_node.prev.count!=self.key_count_map[key]:
                 new_node=Node(self.key_count_map[key])
                 self.insert(prev_node.prev,new_node)
                 self.count_key_map[self.key_count_map[key]]=set()
                 self.count_node_map[self.key_count_map[key]]=new_node
         
             self.count_key_map[self.key_count_map[key]].add(key) 
             
             
         self.count_key_map[prev_count].remove(key)
         if len(self.count_key_map[prev_count])==0:
                self.delete(prev_node)
                self.count_node_map.pop(prev_count)
                self.count_key_map.pop(prev_count)
             
     def getMaxKey(self):
         """
         Returns one of the keys with maximal value.
         :rtype: str
         """
         if self.head.next == self.tail:
             return ""
         x = self.count_key_map[self.tail.prev.count].pop()
         self.count_key_map[self.tail.prev.count].add(x)
         return x
         
 
     def getMinKey(self):
         """
         Returns one of the keys with Minimal value.
         :rtype: str
         """
         if self.head.next == self.tail:
             return ""
         x = self.count_key_map[self.head.next.count].pop()
         self.count_key_map[self.head.next.count].add(x)
         return x
         
     #insert 'node' after prev_node O(1) 
     def insert(self, prev_node, node):
         node.next = prev_node.next
         node.prev = prev_node
         
         node.next.prev = node
         node.prev.next = node
         
     def delete(self, node):
         node.next.prev = node.prev
         node.prev.next = node.next