leetcode-460 LFU Cache

# Design a data structure that follows the constraints of a Least Frequently Used (LFU) cache.
#
# Implement the LFUCache class:
# - LFUCache(int capacity) Initializes the object with the capacity.
# - int get(int key) Gets the value of the key if it exists, otherwise returns -1.
# - void put(int key, int value) Updates the value if key exists. Otherwise, adds
#   the key-value pair. When the cache reaches its capacity, it should invalidate
#   and remove the least frequently used key. If there is a tie, remove the LRU key.
#
# get and put must run in O(1) average time.
#
# Example:
# Input: ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
#        [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
# Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
#
# Constraints:
# 1 <= capacity <= 10^4
# 0 <= key <= 10^5
# 0 <= value <= 10^9
# At most 2 * 10^5 calls will be made to get and put.

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0

        # key -> (value, frequency)
        self.key_to_val_freq = {}

        # frequency -> OrderedDict of {key: value}
        # OrderedDict maintains insertion order for LRU within same frequency
        self.freq_to_keys = defaultdict(OrderedDict)

    def _update_freq(self, key: int) -> None:
        """Update frequency of a key"""
        value, freq = self.key_to_val_freq[key]

        # Remove from current frequency list
        del self.freq_to_keys[freq][key]

        # If current frequency list is now empty and it's the min frequency
        if not self.freq_to_keys[freq] and freq == self.min_freq:
            self.min_freq += 1

        # Add to next frequency list
        freq += 1
        self.freq_to_keys[freq][key] = value
        self.key_to_val_freq[key] = (value, freq)

    def get(self, key: int) -> int:
        if key not in self.key_to_val_freq:
            return -1

        self._update_freq(key)
        return self.key_to_val_freq[key][0]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return

        if key in self.key_to_val_freq:
            # Update existing key
            self.key_to_val_freq[key] = (value, self.key_to_val_freq[key][1])
            self._update_freq(key)
        else:
            # Add new key
            if len(self.key_to_val_freq) >= self.capacity:
                # Evict LFU (and LRU if tie)
                # popitem(last=False) removes first item (LRU within min frequency)
                evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
                del self.key_to_val_freq[evict_key]

            # Add new key with frequency 1
            self.key_to_val_freq[key] = (value, 1)
            self.freq_to_keys[1][key] = value
            self.min_freq = 1


# Alternative: Using custom Node and DLL
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None

class DLL:
    """Doubly Linked List for same frequency"""
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

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

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def remove_tail(self):
        if self.size == 0:
            return None
        tail_node = self.tail.prev
        self.remove(tail_node)
        return tail_node

# Time Complexity: O(1) for both get and put
# Space Complexity: O(capacity)
#
# Data Structures:
# 1. key_to_val_freq: Direct access to key info
# 2. freq_to_keys: Group keys by frequency
# 3. min_freq: Track minimum frequency for eviction
#
# Key Operations:
# - get(): Update frequency, return value
# - put(): If full, evict from min_freq (LRU within that frequency)
#         Add new key with freq=1, update min_freq
#
# Why OrderedDict?
# - Maintains insertion order
# - When multiple keys have same frequency, need LRU tie-breaking
# - popitem(last=False) gives LRU key within that frequency
#
# AirBnB: Tests complex cache design
# Follow-up: Compare LRU vs LFU tradeoffs, when to use each