460. LFU Cache - cocoder39/coco39_LC GitHub Wiki

460. LFU Cache

• O(1) put and get -> hashmap
• how to identify LFU node:
  • initial idea was to use a sorted data structure to manage the frequency O(log N)
  • the key idea here is use maintain self.freq_to_nodes = collections.defaultdict(DoublyLinkedList) and `self.min_freq = 0 # to record in which list lfu node is so we can identify the min_freq in O(1) and remove the LRU node in O(1) (by leveraging double linked list)
    • self.min_freq to record min freq in O(1)
    • self.freq_to_nodes = collections.defaultdict(DoublyLinkedList) to maintain LRU order and achieve O(1) node removal
    • similar technique is used in 895. Maximum Frequency Stack to identify max frequency item in O(1)

class Node:
    def __init__(self, key, val):
        self.prev = None
        self.next = None
        self.key = key
        self.val = val
        self.freq = 1

class DoublyLinkedList:
    def __init__(self):
        self.size = 0 # record size so we can increase min_freq when original min_freq has empty list
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def __len__(self): # to get len(doublyLinkedList)
        return self.size

    def insertToHead(self, node):
        self.size += 1
        node.next = self.head.next
        node.next.prev = node
        self.head.next = node
        node.prev = self.head
    
    def remove(self, node=None):
        if node is None:
            node = self.tail.prev
            if node == self.head:
                raise Exception('no node to be removed from empty list')
        
        self.size -= 1
        node.prev.next = node.next
        node.next.prev = node.prev
        return node

class LFUCache:

    def __init__(self, capacity: int):
        self.capa = capacity
        self.key_to_node = {}
        self.freq_to_nodes = collections.defaultdict(DoublyLinkedList)
        self.min_freq = 0 # to record in which list lfu node is so we can remove it

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]

        # update node attributes
        cur_freq = node.freq
        node.freq += 1

        # update LFU cache attributes
        cur_freq_list = self.freq_to_nodes[cur_freq]
        cur_freq_list.remove(node)
        if cur_freq == self.min_freq and len(cur_freq_list) == 0:
            self.min_freq += 1
        self.freq_to_nodes[node.freq].insertToHead(node)

        return node.val
        

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            node = self.key_to_node[key]

            # update node attributes
            node.val = value
            cur_freq = node.freq
            node.freq += 1

            # update LFU cache attributes
            cur_freq_list = self.freq_to_nodes[cur_freq]
            cur_freq_list.remove(node)
            if cur_freq == self.min_freq and len(cur_freq_list) == 0:
                self.min_freq += 1
            self.freq_to_nodes[node.freq].insertToHead(node)
        else:
            if len(self.key_to_node) == self.capa:
                node = self.freq_to_nodes[self.min_freq].remove()
                del self.key_to_node[node.key]
                # min_freq could be changed at this point
                # it takes O(N) to get the new min freq from self.freq_to_nodes or O(log N) if we maintain frequency in a sorted data structure 
                # However, we can skip the detailed update at this point since the below block will set it to 1 anyway
                
            node = Node(key, value)
            self.key_to_node[key] = node
            self.freq_to_nodes[1].insertToHead(node)
            self.min_freq = 1

========================================================

O(1) time get/put

• -> hashtable
• -> O(1) to delete LF element -> doubly linked list

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1
        self.next = self.prev = None
        
class DLinkedList:
    def __init__(self):
        self.dummy = Node(None, None)
        self.dummy.next = self.dummy.prev = self.dummy
        self.size = 0
    
    def __len__(self):
        return self.size
    
    def append(self, node):
        node.next = self.dummy.next
        node.prev = self.dummy
        node.next.prev = node
        self.dummy.next = node
        self.size += 1
    
    def pop(self, node=None):
        if self.size == 0:
            return
        
        if not node:
            node = self.dummy.prev
        
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        
        return node

class LFUCache:

    def __init__(self, capacity):
        self.size = 0
        self.capacity = capacity
        self.nodes = {} # key -> node
        self.freqs = collections.defaultdict(DLinkedList) # freq -> DLinkedList
        self.minFreq = 0
    
    def update(self, node): # increase freq by 1
        freq = node.freq
        self.freqs[freq].pop(node)
        
        if self.minFreq == freq and not self.freqs[freq]: # last node with minFreq
            self.minFreq += 1
            
        node.freq += 1
        self.freqs[node.freq].append(node)
        
    def get(self, key: int) -> int:
        
        if key not in self.nodes:
            return -1
        
        node = self.nodes[key]
        self.update(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        
        if key in self.nodes:
            node = self.nodes[key]
            self.update(node)
            node.value = value
        else:
            if self.size == self.capacity:
                node = self.freqs[self.minFreq].pop()
                del self.nodes[node.key]
                self.size -= 1
            
            node = Node(key, value)
            self.nodes[key] = node
            self.freqs[1].append(node)
            self.minFreq = 1
            self.size += 1