Super clear O(1) solution using Minimum BASIC data structure (TWO hash tables + ONE doubly linked list)


  • 0

    The basic idea is using ONE doubly linked list to maintain all the data in the cache, wherein each node accommodates a key-value pair. This is the key difference from other solutions using two or 2-d doubly linked list. Storing all the node in a 1-d linked list can avoid many complex 2-d linked list operations, which is error-prone. The nodes that have been accessed for the same frequency are grouped together like in a bucket. And the groups are arranged in the ascending order of frequency in the linked list, where less frequently-accessed node are put behind. So when cache is full, the first node in the linked list will be evicted.

    Two hash tables. One is used for O(1) access from key to its node. And the other is for O(1) access from frequency to boundary node of frequency buckets. More precisely, the boundary nodes are the rightmost node of the buckets, because when we need to add a new node to the bucket, we can easily find the position to add it.

     ------------>    direction of more ```frequent and recent``` access ----->                 
             
    dummy head <-> n1 <-> n2 <-> n3 <-> n4 <-> n5 <-> n6 <-> n7 <-> dummy tail                      
    buckets        ----------------     ----------------     ---
                      freq = 1             freq = 3       freq = 9
    frequency table f  f[1]=n3              f[3]=n6        f[9]=n7   
    
    class DLinkNode(object):  # Doubly Linked List Node
        def __init__(self, key, value):
            self.key, self.value = key, value
            self.freq = 0
            self.prev = self.next = None
    
        def link(self, node):  # Link self and node
            node.prev = self
            self.next = node
    
        def connect(self, node):  # Connect node behind self
            node.link(self.next)
            self.link(node)
    
        def disconnect(self):  # Disconnect self from Linked List
            self.prev.next = self.next
            self.next.prev = self.prev
    
    
    class LFUCache(object):
        def __init__(self, capacity):
            self.remain = self.capacity = capacity
    
            self.head = DLinkNode(-1, -1)  # dummy head
            self.tail = DLinkNode(-2, -2)  # dummy tail
            self.head.next = self.tail
    
            self.cache = {}  # mapping from key to DLinkNode
            self.freq = {0: self.head}  # mapping from freq to DLinkNode
    
        def remove(self, key):  # Remove node from linked list
            node = self.cache[key]
            if self.freq[node.freq] is node:  # node is sentinel
                if node.prev.freq == node.freq:
                    self.freq[node.freq] = node.prev  # re-assign sentinel
                else:  # node is the only node in the frequency bucket
                    del self.freq[node.freq]
            node.disconnect()
    
        def add(self, key):  # add node to freq+1 bucket
            node = self.cache[key]
            f = node.freq = node.freq + 1
            if f in self.freq:  # freq+1 bucket exists
                self.freq[f].connect(node)
            elif f - 1 in self.freq:  # freq bucket exists
                self.freq[f - 1].connect(node)
            else:  # both buckets not exsits
                node.prev.connect(node)
            self.freq[f] = node
    
        def move(self, key):
            self.remove(key)
            self.add(key)
    
        def get(self, key):
            if key in self.cache:
                self.move(key)
                return self.cache[key].value
            return -1
    
        def put(self, key, value):
            if not self.capacity: # handle the 0-capacity case
                return
            if key in self.cache:
                self.cache[key].value = value
                self.move(key)
            else:
                if not self.remain:
                    rm_key = self.head.next.key
                    self.remove(rm_key)
                    del self.cache[rm_key]
                else:
                    self.remain -= 1
                self.cache[key] = DLinkNode(key, value)
                self.add(key)
    

  • 0

    Just a side note, for this problem, we need to consider the corner case of cache capacity=0.


Log in to reply
 

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