Python solution with detailed explanation


  • 0
    G

    Data-Structures
    key_counter: Hashmap with key as input key and value as frequency of the key.

    Node: A node type to support a doubly linked list. It is a container to hold a bag of keys. It supports:

    • add_key(key): Add a key to the bag
    • remove_key(key): Remove a key from the bag
    • get_any_key(): Returns any random key from the bag. Returns None if bag is empty.
    • is_empty(): Returns true if the bag is empty

    DoubleLinkedList

    • The linked list is implemented using the idea of sentinel nodes, i.e. we have two dummy nodes to represent head and tail. Initially head.next points to tail and tail.prev points to head. Using two dummy nodes dramatically simplifies the implementation.
    • insert_after(x): Add a node after node x
    • insert_before(x): Add a node before node x
    • insert_after_head: Add a node at list head
    • remove(x): Remove the node from the list
    • get_head(): Returns the reference to the real head node
    • get_tail() Returns the reference to the real tail node

    node_freq: Hashmap with key as frequency and value as Node.

    Algorithm Idea
    https://goo.gl/photos/YLhF2qCcBwRpAn58A

    • A node in the doubly linked list represents a bucket containing a bag of words with a certain frequency. The doubly linked list is maintained in a sorted order with the head node containing words with the least frequency and the tail node containing words with maximum frequency.
    • Using this list, getMaxKey and getMinKey can be implemented in O(1) by returning any word contained in the tail and head respectively.
    • key_counter is hashmap which allows us to increment or decrement frequency of a key in O(1).
    • node_freq is a hashmap which maps a frequency integer to the bucket node in the linked list.
    • Now, if we can maintain the sorted order of the linked list in O(1) while performing the increment and decrement operations, we would have a working solution!

    Increment Details

    • While incrementing a key, we first update the key_counter ro reflect the new frequency (cf) of the key.
    • Then we test if there is already a bucket with cf using node_freq hashmap. If not, then we need to add a bucket to the linked list.
    • To maintain the sorted invariant, this new bucket must be after the bucket for frequency pf (cf-1).
    • Now unless pf is 0, we are guaranteed that a pf bucket already exists. Therefore, either we add the new bucket after the head node or after the pf bucket.
    • pf bucket can be retrieved in O(1) using node_freq. insertion in doubly linked list can be done in O(1) as well. Once we have inserted, we add the key to the new bucket.
    • Finally we need to remove the key from the previous bucket if pf > 0 (i.e. if a previous bucket exists). Again this can be done in O(1). If the previous bucket becomes empty after removing the key, then we need to also drop the entire bucket from the list.

    Decrement Details

    • While decrementing a key, we first check if the key exisits in key_counter or not. If not, then we simply return. if it does exist, we update the key_counter to reflect the new frequency (cf) of the key. If cf is 0, then we drop this key from the key counter.
    • If cf is not in node_freq and cf is not 0, then we need to add a new bucket in the linked list such that the sorted invariant is maintained. Again we are guaranteed to have pf bucket!
    • We add the key to the new bucket and remove it from the previous bucket - O(1) operations.
    from collections import defaultdict
    class Node(object):
        def __init__(self):
            self.key_set = set([])
            self.prev, self.nxt = None, None 
    
        def add_key(self, key):
            self.key_set.add(key)
    
        def remove_key(self, key):
            self.key_set.remove(key)        
    
        def get_any_key(self):
            if self.key_set:
                result = self.key_set.pop()
                self.add_key(result)
                return result
            else:
                return None
    
        def is_empty(self):
            return len(self.key_set) == 0
    
    
    class DoubleLinkedList(object):
        def __init__(self):
            self.head_node, self.tail_node = Node(), Node()
            self.head_node.nxt, self.tail_node.prev = self.tail_node, self.head_node
    
        def insert_after(self, x):
            node, temp = Node(), x.nxt
            x.nxt, node.prev = node, x
            node.nxt, temp.prev = temp, node
            return node
        
        def insert_before(self, x):
            return self.insert_after(x.prev)
    
        def insert_after_head(self):
            return self.insert_after(self.head_node)
    
        def remove(self, x):
            prev_node = x.prev
            prev_node.nxt, x.nxt.prev = x.nxt, prev_node
    
        def get_head(self):
            return self.head_node.nxt
        
        def get_tail(self):
            return self.tail_node.prev
    
        
    class AllOne(object):
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.dll, self.key_counter = DoubleLinkedList(), defaultdict(int)
            self.node_freq = {}
    
        def _rmv_key_pf_node(self, pf, key):
            if pf in self.node_freq:
                node = self.node_freq[pf]
                node.remove_key(key)
                if node.is_empty():
                    self.dll.remove(node)
                    self.node_freq.pop(pf)
    
        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.key_counter[key] += 1
            cf, pf = self.key_counter[key], self.key_counter[key]-1
            if cf not in self.node_freq:
                self.node_freq[cf] = self.dll.insert_after_head() if pf == 0 else self.dll.insert_after(self.node_freq[pf])
            self.node_freq[cf].add_key(key)
            if pf > 0:
                self._rmv_key_pf_node(pf, key)
    
        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 in self.key_counter:
                self.key_counter[key] -= 1
                cf, pf = self.key_counter[key], self.key_counter[key]+1
                if self.key_counter[key] == 0:
                    self.key_counter.pop(key)
                if cf not in self.node_freq and cf != 0:
                    self.node_freq[cf] = self.dll.insert_before(self.node_freq[pf])
                if cf != 0:
                    self.node_freq[cf].add_key(key)
                self._rmv_key_pf_node(pf, key)
    
        def getMaxKey(self):
            """
            Returns one of the keys with maximal value.
            :rtype: str
            """
            return self.dll.get_tail().get_any_key() if self.dll.get_tail().get_any_key() else ""
    
        def getMinKey(self):
            """
            Returns one of the keys with Minimal value.
            :rtype: str
            """
            return self.dll.get_head().get_any_key() if self.dll.get_tail().get_any_key() else ""
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.