Build an LFU cache with O(1) time complexity for both get and put. Use a dictionary…
- 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.
- 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 cleanupThis 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 += 1Both
getandputrun in constant time, and the two-level doubly linked structure maintains the LFU/LRU eviction policy efficiently.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.