LC460 LFU Cache

from collections import defaultdict
class Node:
    def __init__(self,key,value):
        self.key = key
        self.val = value
        self.cnt = 1
        self.prev = None
        self.next = None

class DLList:
    def __init__(self):
        self.sentinel = Node(None,None)
        self.sentinel.next = self.sentinel.prev = self.sentinel
        self.size_dllist = 0 # record current dllist length
        
    def add_head(self,node):
        Next = self.sentinel.next
        node.next = Next
        node.prev = self.sentinel
        Next.prev = node
        self.sentinel.next = node 
        self.size_dllist += 1
        
    def remove(self, node):
        if self.size_dllist == 0:
            return
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size_dllist -= 1
        return node
    
    def remove_tail(self):
        if self.size_dllist == 0:
            return 
        node = self.sentinel.prev
        #print('remove taill',node.val)
        node.prev.next =node.next
        node.next.prev = node.prev
        self.size_dllist -= 1
        return node 
        
        
        
class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.size = 0
        self.d = defaultdict() # key:Node
        self.frequent_d = defaultdict(DLList)   # frequency :  DLList
        self.min_freq = 1 # to 
    
    def _update(self,key,value):
        # 1.when get(key) is called:  get node, remove the node, update node val, freq +1, add back to freq_d 
        # 2.1 when put(key) is called and the key exist:
        #                   find node from d, update value, call get(key)
       
        node = self.d[key]
        node.val = value
        old_freq = node.cnt
        self.frequent_d[old_freq].remove(node)
        if self.min_freq == old_freq and not self.frequent_d[old_freq]: # if there is no linkedlist exist at old_freq, increment min_freq
            self.min_freq += 1
        new_freq = old_freq +1 
        node.cnt = new_freq
        self.frequent_d[node.cnt].add_head(node)

    def get(self, key: int) -> int:  # cap does not change 
        if key not in self.d:
            return -1
        #print(self.d.keys())
        node = self.d[key]
        prev_dllist = self.frequent_d[node.cnt]
        prev_dllist.remove(node)
        prev_freq = node.cnt
        cur_freq = prev_freq + 1
        node.cnt = cur_freq
        cur_ddlist = self.frequent_d[node.cnt]
        cur_ddlist.add_head(node)
        return node.val
    
 # 2.2 when put(key) is called and key not exist:
        #                   check if cache size has reached capacity, if yes, delete least frequent one(ensure len(DLList)> 0), otherwise ,create a new node, add_head(node) to DLList  with freq = 1
        
    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return 
        if key in self.d:
            self._update(key,value)
        # key not apprear before
        else:
            node = Node(key,value)
            self.d[key] = node
            self.frequent_d[node.cnt].add_head(node)
            self.size += 1
            if self.size > self.cap:
                if self.frequent_d[self.min_freq].size_dllist > 1:
                    node = self.frequent_d[self.min_freq].remove_tail()
                    self.size -= 1
                else:
                    while True:
                        self.min_freq += 1
                        if self.frequent_d[self.min_freq].size_dllist > 0:
                            node = self.frequent_d[self.min_freq].remove_tail()
                            self.size -= 1
                            break
                del self.d[node.key]
                self.min_freq = 1
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

class LFUCache:
    def __init__(self, capacity: int):
        self.size = capacity
        self.freq_pair = defaultdict(list)
        self.key_freq = {} # key:freq, can also check if current LFU exceed capacity limit  
        self.least_f = 1
    # tc O(N) sc O(N)
    def get(self, key: int) -> int:
        res = -1
        if key in self.key_freq:
            freq = self.key_freq[key]
            for i,kv in enumerate(self.freq_pair[freq]):
                if kv[0] == key:
                    res = kv[1]
                    del self.freq_pair[freq][i]#self.freq_pair[freq].pop(i)
                    if freq == self.least_f and len(self.freq_pair[freq])==0:
                        self.least_f  += 1
                    break
            new_freq = freq + 1
            self.freq_pair[new_freq].append((key,res))
            self.key_freq[key] = new_freq 
        return res 
    # tc O(N) sc O(N)
    def put(self, key: int, value: int) -> None:
        # need to discuss edge case when capasity = 0 
        if self.size == 0:
            return 
        if key in self.key_freq:
            freq = self.key_freq[key]
            for i,kv in enumerate(self.freq_pair[freq]):
                if kv[0] == key:
                    self.freq_pair[freq].pop(i)
                    # print(f'after pop put {self.freq_pair[freq]}')
                    self.key_freq.pop(key) # don't forget to update hashmap 
                    if freq == self.least_f and len(self.freq_pair[freq])==0:
                        self.least_f  += 1
                    break    
        else:
            freq = 0
        new_freq = freq + 1
        if len(self.key_freq) == self.size:
            k,v = self.freq_pair[self.least_f].popleft()#slite improvement than using list .pop(0)
            self.key_freq.pop(k)
        self.freq_pair[new_freq].append((key,value))
        self.key_freq[key] = new_freq

        self.least_f = min(self.least_f,new_freq)
            


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)