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: