Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1 Codex Max· openaiHugging Face Frontier Reasoning Traces

Build an LFU cache with O(1) time complexity for both get and put. Use a dictionary…

  1. User

    Build an LFU cache with O(1) time complexity for both get and put. Use a dictionary mapping keys to nodes and a doubly linked list of doubly linked lists for frequency buckets to manage counts efficiently.

  2. Assistant

    Implementing LFU cache with frequency buckets and O(1) operations

    The solution uses a dictionary to map keys to nodes storing values and frequencies, and a doubly linked list of frequency buckets each holding a doubly linked list of entries to track frequency order and recency within the same frequency. This enables constant-time updates for both get and put operations by efficiently relocating entries between frequency buckets while evicting the least frequently and least recently used entries when needed.

    class Node:
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.freq = 1
            self.parent = None  # FreqBucket the node belongs to
            self.prev = None
            self.next = None
    
    class DoublyLinkedList:
        def __init__(self):
            self.head = Node(None, None)  # Sentinel head
            self.tail = Node(None, None)  # Sentinel tail
            self.head.next = self.tail
            self.tail.prev = self.head
            self.size = 0
    
        def appendleft(self, node):
            node.prev = self.head
            node.next = self.head.next
            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
            node.prev = None
            node.next = None
            self.size -= 1
    
        def pop_tail(self):
            if self.size > 0:
                lru = self.tail.prev
                self.remove(lru)
                return lru
            return None
    
        def is_empty(self):
            return self.size == 0
    
    class FreqBucket:
        def __init__(self, freq):
            self.freq = freq
            self.prev = None
            self.next = None
            self.dll = DoublyLinkedList()
    
    class LFUCache:
        def __init__(self, capacity: int):
            self.capacity = capacity
            self.size = 0
            self.key_to_node = {}  # key -> Node
            # Frequency buckets list with sentinel head and tail
            self.freq_head = FreqBucket(0)   # sentinel head (freq=0)
            self.freq_tail = FreqBucket(float('inf'))  # sentinel tail (freq=inf)
            self.freq_head.next = self.freq_tail
            self.freq_tail.prev = self.freq_head
    
        def get(self, key: int) -> int:
            if key not in self.key_to_node:
                return -1
            node = self.key_to_node[key]
            self._increase_freq(node)
            return node.val
    
        def put(self, key: int, value: int) -> None:
            if self.capacity == 0:
                return
            if key in self.key_to_node:
                node = self.key_to_node[key]
                node.val = value
                self._increase_freq(node)
                return
            if self.size == self.capacity:
                self._evict_lfu()
            new_node = Node(key, value)
            self.key_to_node[key] = new_node
            self.size += 1
            self._add_to_freq_bucket(new_node, 1)
    
        def _increase_freq(self, node: Node) -> None:
            current_bucket = node.parent
            current_bucket.dll.remove(node)
            next_bucket = current_bucket.next
            new_freq = current_bucket.freq + 1
    
            if next_bucket == self.freq_tail or next_bucket.freq != new_freq:
                next_bucket = self._insert_bucket_after(current_bucket, new_freq)
    
            node.freq = new_freq
            node.parent = next_bucket
            next_bucket.dll.appendleft(node)
    
            if current_bucket.dll.is_empty() and current_bucket.freq != 0:
                self._remove_bucket(current_bucket)
    
        def _add_to_freq_bucket(self, node: Node, freq: int) -> None:
            first_bucket = self.freq_head.next
            if first_bucket == self.freq_tail or first_bucket.freq != freq:
                first_bucket = self._insert_bucket_after(self.freq_head, freq)
            node.freq = freq
            node.parent = first_bucket
            first_bucket.dll.appendleft(node)
    
        def _evict_lfu(self) -> None:
            lfu_bucket = self.freq_head.next
            node_to_remove = lfu_bucket.dll.pop_tail()
            if node_to_remove:
                del self.key_to_node[node_to_remove.key]
                self.size -= 1
            if lfu_bucket.dll.is_empty():
                self._remove_bucket(lfu_bucket)
    
        def _insert_bucket_after(self, bucket: FreqBucket, freq: int) -> FreqBucket:
            new_bucket = FreqBucket(freq)
            new_bucket.prev = bucket
            new_bucket.next = bucket.next
            bucket.next.prev = new_bucket
            bucket.next = new_bucket
            return new_bucket
    
        def _remove_bucket(self, bucket: FreqBucket) -> None:
            bucket.prev.next = bucket.next
            bucket.next.prev = bucket.prev
            # Python GC handles cleanup
    

    This implementation tracks each key's node and frequency bucket, ensuring get and put operations can update frequencies or evict least frequently used entries in constant time. Frequency buckets are kept sorted in ascending order, and within each bucket entries are ordered by recency to evict the least recently used when frequencies tie. One way to keep both operations (O(1)) is to maintain two layers of doubly‑linked lists:

    • A list of “frequency buckets”, sorted by count. Each bucket node holds a count value and a doubly linked list of cache entries at that count.
    • Each cache entry node knows its key, value, current count and a pointer back to its bucket.

    A dictionary gives you direct access from a key to its entry node. Bumping the frequency of an entry consists of unlinking it from its current bucket’s list, moving it into the next bucket (creating that bucket if necessary), and possibly removing the old bucket if it became empty. Eviction happens from the lowest‑frequency bucket at the tail end of that bucket’s entry list to get least‑recently‑used semantics within a frequency.

    Here is a complete implementation in Python:

    class Entry:
        def __init__(self, key=None, val=None):
            self.key = key
            self.val = val
            self.freq = 1
            self.parent = None  # FreqBucket this entry belongs to
            self.prev = None
            self.next = None
    
    class EntryList:
        """Doubly linked list of Entry objects."""
        def __init__(self):
            self.head = Entry()  # sentinel nodes
            self.tail = Entry()
            self.head.next = self.tail
            self.tail.prev = self.head
            self.size = 0
    
        def appendleft(self, node):
            node.prev = self.head
            node.next = self.head.next
            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
            node.prev = node.next = None
            self.size -= 1
    
        def pop_tail(self):
            if self.size == 0:
                return None
            node = self.tail.prev
            self.remove(node)
            return node
    
        def is_empty(self):
            return self.size == 0
    
    class FreqBucket:
        """Node in the frequency bucket list."""
        def __init__(self, freq):
            self.freq = freq
            self.prev = None
            self.next = None
            self.entries = EntryList()
    
    class LFUCache:
        def __init__(self, capacity: int):
            self.cap = capacity
            self.size = 0
            self.key_to_entry = {}
            # sentinel buckets to simplify edge cases
            self.freq_head = FreqBucket(0)
            self.freq_tail = FreqBucket(float('inf'))
            self.freq_head.next = self.freq_tail
            self.freq_tail.prev = self.freq_head
    
        def _insert_bucket_after(self, bucket, freq):
            new_bucket = FreqBucket(freq)
            new_bucket.prev = bucket
            new_bucket.next = bucket.next
            bucket.next.prev = new_bucket
            bucket.next = new_bucket
            return new_bucket
    
        def _remove_bucket(self, bucket):
            bucket.prev.next = bucket.next
            bucket.next.prev = bucket.prev
            bucket.prev = bucket.next = None
    
        def _increase_freq(self, entry):
            bucket = entry.parent
            bucket.entries.remove(entry)
    
            # ensure there is a bucket for the next frequency
            next_bucket = bucket.next
            if next_bucket is self.freq_tail or next_bucket.freq != bucket.freq + 1:
                next_bucket = self._insert_bucket_after(bucket, bucket.freq + 1)
    
            # move entry into the next bucket
            entry.freq = next_bucket.freq
            entry.parent = next_bucket
            next_bucket.entries.appendleft(entry)
    
            # remove old bucket if it became empty
            if bucket.entries.is_empty():
                self._remove_bucket(bucket)
    
        def get(self, key: int) -> int:
            if key not in self.key_to_entry:
                return -1
            entry = self.key_to_entry[key]
            self._increase_freq(entry)
            return entry.val
    
        def put(self, key: int, value: int) -> None:
            if self.cap == 0:
                return
            if key in self.key_to_entry:
                entry = self.key_to_entry[key]
                entry.val = value
                self._increase_freq(entry)
                return
    
            # evict if at capacity
            if self.size == self.cap:
                lfu_bucket = self.freq_head.next
                evicted = lfu_bucket.entries.pop_tail()
                if evicted:
                    del self.key_to_entry[evicted.key]
                    self.size -= 1
                if lfu_bucket.entries.is_empty():
                    self._remove_bucket(lfu_bucket)
    
            # insert new entry with frequency 1
            entry = Entry(key, value)
            # ensure bucket for freq=1 exists at the front
            first_bucket = self.freq_head.next
            if first_bucket is self.freq_tail or first_bucket.freq != 1:
                first_bucket = self._insert_bucket_after(self.freq_head, 1)
            entry.parent = first_bucket
            first_bucket.entries.appendleft(entry)
            self.key_to_entry[key] = entry
            self.size += 1
    

    Both get and put run in constant time, and the two-level doubly linked structure maintains the LFU/LRU eviction policy efficiently.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.