# 460. LFU Cache
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value)
- Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
Follow up: Could you do both operations in O(1) time complexity?
Example:
LFUCache cache = new LFUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
# Solution
Approach 1: use 2 maps and a(or several) doubly linked list.
# Code (Python)
Approach 1:
class Node:
def __init__(self, key, val, freq=1, prev=None, next=None):
self.key = key
self.val = val
self.freq = freq
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self._sentinel = Node(0, 0)
self._len = 0
self._sentinel.prev, self._sentinel.next = self._sentinel, self._sentinel
def __len__(self): # implement magic method len() for DoublyLinkedList
return self._len
def remove(self, node):
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
self._len -= 1
return node
def remove_last(self):
return self.remove(self._sentinel.prev)
def insert_first(self, key, val, freq):
node = Node(key, val, freq, self._sentinel, self._sentinel.next)
node.next.prev = node
self._sentinel.next = node
self._len += 1
return node
class LFUCache:
def __init__(self, capacity: int):
# a node: has a value, a frequency, prev and next pointers
# nodes map: <key, node>
# frequencies map: <frequency, a doubly linked list storing nodes that have that frequency>
# could instead maintain a chained doubly linked list, with a dict storing <freq, place to insert a node with that freq>
self._min_freq = 0
self._nodes = {}
self._freqs = {}
self._capacity = capacity
self._size = 0
def get(self, key: int) -> int:
if key not in self._nodes:
return -1
node = self._nodes[key]
# adjust the frequencies lists
self._freqs[node.freq].remove(node)
if node.freq + 1 not in self._freqs:
self._freqs[node.freq+1] = DoublyLinkedList()
new_node = self._freqs[node.freq+1].insert_first(node.key, node.val, node.freq + 1)
self._nodes[key] = new_node
# adjust minimum frequency of the entire cache
if self._min_freq == node.freq and len(self._freqs[node.freq]) == 0:
self._min_freq = node.freq + 1
return node.val
def put(self, key: int, value: int) -> None:
if self._capacity == 0:
return
if key in self._nodes:
self.get(key)
self._nodes[key].val = value
return
if self._size < self._capacity:
self._size += 1
else:
# eviction
evicted_node = self._freqs[self._min_freq].remove_last()
self._nodes.pop(evicted_node.key)
if 1 not in self._freqs:
self._freqs[1] = DoublyLinkedList()
node = self._freqs[1].insert_first(key, value, 1)
self._nodes[key] = node
self._min_freq = 1
# Code (C++)
Approach 1:
Approach 2: