## # 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(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
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

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]

self._freqs[node.freq].remove(node)
if node.freq + 1 not in self._freqs:
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: