Python O(1) Solution using 1 Dictionary and "Doubly-Linked-List of Doubly-Linked-Lists"


  • 0
    A

    I use a dictionary to map to key to data nodes.
    The data nodes are linked together with nodes with the exact same frequency count, headed by a dummy node. The dummy node contains one value: the count.
    I also have a linked list of dummy nodes, with the head being the smallest frequency count.
    Data nodes have pointer to their dummy node parent, allowing for O(1) access.
    Since incrementing frequency is always count + 1 we either 1) get the next dummy node if it is count + 1, or 2) insert a new dummy node next to it and set it's frequency count to count + 1.
    We then insert the new data node into the following dummy node.
    We will delete the previous dummy node if unlinking the data node from its previous dummy node empties the linked list.

    class LFUCache(object):
        class DummyNode(object):
            def __init__(self, count_value):
                self.count_value = count_value
                self.next_node = self
                self.prev_node = self
                self.next_freq = self
                self.prev_freq = self
        class DataNode(object):
            def __init__(self, key=None, value=None):
                self.key = key
                self.value = value
                self.dummy_node = self
                self.next_node = self 
                self.prev_node = self
    
        def __init__(self, capacity):
            """
            
            :type capacity: int
            """
            self._max_capacity = capacity
            self._data_node_dict = {}
            self._lfu_dummy_node_list = LFUCache.DummyNode(0)
            
    
        def get(self, key):
            """
            :type key: int
            :rtype: int
            """
            if key not in self._data_node_dict:
                return -1
    
            node = self._data_node_dict[key]
            self._increment_node_frequency(node)
            return node.value
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: void
            """
            if self._max_capacity == 0:
                return
            
            if key not in self._data_node_dict:
                node = LFUCache.DataNode(key,value)
                if len(self._data_node_dict) == self._max_capacity:
                    self._delete_least_used_node()
                self._data_node_dict[key] = node
                root_dummy = self._lfu_dummy_node_list
                if root_dummy.next_freq.count_value != 1:
                    new_dummy = LFUCache.DummyNode(1)
                    self._insert_next_freq_dummy_node(root_dummy,new_dummy)
                self._insert_node_into_lru_linked_list(root_dummy.next_freq, node)
            else :
                node = self._data_node_dict[key]
                node.value = value
                self._increment_node_frequency(node)
    
        def _increment_node_frequency(self, node):
            old_dummy = node.dummy_node
            new_count_val = old_dummy.count_value + 1
            if old_dummy.next_freq.count_value != new_count_val:
                new_dummy = LFUCache.DummyNode(new_count_val)
                self._insert_next_freq_dummy_node(old_dummy,new_dummy)
            dummy = old_dummy.next_freq
            self._unlink_node_from_lru_linked_list(node)
            self._insert_node_into_lru_linked_list(dummy, node)
            return node.value
            
        def _insert_next_freq_dummy_node(self, prev_dummy, next_dummy):
            next_dummy.next_freq = prev_dummy.next_freq
            next_dummy.prev_freq = prev_dummy
            prev_dummy.next_freq.prev_freq = next_dummy
            prev_dummy.next_freq = next_dummy
            
        def _insert_node_into_lru_linked_list(self, dummy, node):
            node.next_node = dummy.next_node
            node.prev_node = dummy
            dummy.next_node.prev_node = node
            dummy.next_node = node
            node.dummy_node = dummy
    
        def _unlink_node_from_lru_linked_list(self, node):
            dummy = node.dummy_node
            node.prev_node.next_node = node.next_node
            node.next_node.prev_node = node.prev_node
            if dummy.next_node == dummy : #delete dummy node
                dummy.prev_freq.next_freq = dummy.next_freq
                dummy.next_freq.prev_freq = dummy.prev_freq
                del dummy
    
        def _delete_least_used_node(self):
            least_used_dummy = self._lfu_dummy_node_list.next_freq
            least_used = least_used_dummy.prev_node
            self._unlink_node_from_lru_linked_list(least_used)
            self._data_node_dict.pop(least_used.key)
            del least_used
    
    

Log in to reply
 

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