LFU Cache

Approach: Hash Maps for Frequency and Nodes

Use a hash map to store keys mapped to nodes. Use another hash map mapping frequencies to a Doubly Linked List of nodes with that frequency (ordered by recency). Track the min_freq. On get/put, update the node's frequency, moving it to the next frequency's list.

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

class DLinkedList:
    def __init__(self):
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def __len__(self): return self.size

    def append(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def pop(self, node=None):
        if self.size == 0: return
        if not node: node = self.tail.prev
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node

class LFUCache:
    def __init__(self, capacity: int):
        self.size = 0
        self.cap = capacity
        self.min_freq = 0
        self.cache = {}
        self.freq = collections.defaultdict(DLinkedList)

    def _update(self, node):
        freq = node.freq
        self.freq[freq].pop(node)
        if self.min_freq == freq and not self.freq[freq]:
            self.min_freq += 1
        node.freq += 1
        self.freq[node.freq].append(node)

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

    def put(self, key: int, value: int) -> None:
        if self.cap == 0: return
        if key in self.cache:
            node = self.cache[key]
            self._update(node)
            node.val = value
        else:
            if self.size == self.cap:
                node = self.freq[self.min_freq].pop()
                del self.cache[node.key]
                self.size -= 1
            node = Node(key, value)
            self.cache[key] = node
            self.freq[1].append(node)
            self.min_freq = 1
            self.size += 1