lfu_cache.py

from collections import defaultdict

class LFUCache:
    def __init__(self, capacity_kb):
        self.capacity = capacity_kb
        self.cache = {}
        self.freq = defaultdict(int)
        self.current_size = 0

    def request_page(self, page, size_kb):
        if page in self.cache:
            self.freq[page] += 1
            return True  # Cache hit

        # Cache miss → add page
        while self.current_size + size_kb > self.capacity:
            least_used = min(self.freq, key=self.freq.get)
            self.current_size -= self.cache[least_used]
            del self.cache[least_used]
            del self.freq[least_used]

        self.cache[page] = size_kb
        self.freq[page] = 1
        self.current_size += size_kb
        return False