460. LFU Cache

HardDesignHash TableLinked ListDoubly-Linked List

Problem Description

In this problem, we need to design a Least Frequently Used (LFU) cache. An LFU cache is a type of cache that removes the least frequently accessed item when it needs space. If there are multiple items with the same lowest frequency, it removes the least recently used among those.

The LFUCache class requires the following operations:

LFUCache(int capacity): Constructor that initializes the cache with a given capacity.
int get(int key): Retrieves the value linked to the key from the cache. If the key is not present, it should return -1.
void put(int key, int value): Inserts or updates the value of the key. If inserting a new item causes the cache to exceed its capacity, the least frequently used key should be removed. In case of a tie (when multiple keys have the same frequency), the least recently used key should be removed.

Additionally, each key in the cache will have a use counter which increments every time the key is accessed through get or put operations. The goal is to implement get and put methods that each run with an average time complexity of O(1).

Intuition

The solution to this problem requires us to perform insertion, access, and removal operations with O(1) complexity. We can satisfy these requirements with a combination of data structures: hashtables and doubly linked lists.

Hashtable: Allows O(1) access to nodes by their keys.
Doubly Linked Lists: Allow O(1) insertion and removal of nodes. We use one doubly linked list per frequency count, so each list contains all nodes that have been accessed a certain number of times.

For the LFUCache, we maintain the following:

A map that maps keys to their corresponding node which contains the value and frequency of access.
A freq_map that maps frequencies to a doubly linked list containing all nodes with that frequency.
A variable min_freq to keep track of the minimum frequency of all keys in the cache for easy access to the least frequently used item.

When a get or put operation is called, we update the corresponding node's frequency, move it to the respective frequency list in the freq_map, and update min_freq if necessary. If a put operation is performed on a full cache, we remove the least frequently used item. When there's a tie, we remove the least recently used item from the list corresponding to the lowest frequency.

By doing this, we ensure constant-time O(1) complexity for get and put operations while maintaining the structure of the LFU cache.

Learn more about Linked List patterns.

Solution Approach

The implementation for the LFU Cache problem involves designing a set of classes to efficiently manage our cache operations. Here we will discuss the algorithms, patterns, and data structures utilized in the solution code provided:

Node Class

A Node represents an item in the cache, with properties for its key, value, frequency (freq), prev (previous node), and next (next node). This will be used to store each entry and will be inserted into a doubly linked list.

DoublyLinkedList Class

A DoublyLinkedList is used to keep track of all items with the same frequency. It supports adding a node to the head (add_first), removing a specific node (remove), and removing the last node (remove_last). An empty list can be checked with is_empty.

LFUCache Class

Data Structures:

self.map: A dictionary (hashtable) to map keys to their corresponding node (Node objects).
self.freq_map: A dictionary to map frequencies to their corresponding doubly linked list, where each list contains all nodes with that frequency.
self.min_freq: An integer tracking the current minimum frequency amongst all keys in the cache.

Constructor:

Initializes the data structures and sets the capacity of the cache.

get Method:

Retrieves the node from the map using the given key.
If the key is missing or the capacity is 0, returns -1.
If the node is found, it calls the incr_freq method to update the frequency of the node and returns its value.

put Method:

If the capacity is 0, the function ends early as no items can be put into the cache.
If the key is present in the map, it updates the value in the corresponding node and increases the frequency by calling incr_freq.
If the key is not present and the cache is at full capacity, it removes the least frequently used item by (1) accessing the linked list for the current minimum frequency, (2) removing the last node from that list, and (3) removing the node's key from the map.
A new node is created and added to the map and to the frequency map under frequency 1. The min_freq is set to 1.

incr_freq Method:

Removes the node from its current frequency list in freq_map.
If the removal of the node results in an empty list and that frequency was the min_freq, increments min_freq.
Increments the node's frequency, inserts it into the linked list in the freq_map that corresponds to the new frequency.

add_node Method:

A helper used to add a node to the linked list in the freq_map corresponding to the node’s frequency.

With these components combined, we ensure each operation on the cache is O(1) on average by efficiently tracking both the least frequently and least recently used items.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say we have an LFU Cache with a capacity of 2, and we perform the following operations:

put(1, 10): The cache is empty, so this will create a new node with key 1 and value 10. The frequency is set to 1. Our frequency map has 1 -> Node(1) and min_freq is now 1.
put(2, 20): A new node with key 2 and value 20 is created. Similar to the first step, this node's frequency is also 1 and is added to the same frequency list. The frequency map now is 1 -> Node(1) <-> Node(2).
get(1): This operation will get the node with key 1, which has a value of 10. The frequency of this node will be incremented to 2. Since it's the only node with this frequency, it will be added to a new frequency list. The frequency map updates to 1 -> Node(2) and 2 -> Node(1). min_freq remains 1.
put(3, 30): We need to add a new node with key 3 and value 30. Since the cache has reached its capacity, we must remove an item. We look at min_freq which is 1 and remove the least recently used item from that frequency's list, which is Node(2). We then add Node(3) with a frequency of 1 to the list. The frequency map is now 1 -> Node(3) and 2 -> Node(1).
get(3): The node with key 3 is accessed, increasing its frequency to 2. Now both nodes with keys 1 and 3 have the same frequency. The lists are updated: 1 -> becomes empty and 2 -> Node(1) <-> Node(3). min_freq is updated to 2 because there are no nodes with a frequency of 1 after this operation.
get(1): The node with key 1 is accessed again, so its frequency increases to 3. We update the lists such that 2 -> Node(3) and a new list 3 -> Node(1) is created. min_freq remains 2.

The sequence of operations above demonstrates how the LFU Cache responds to different commands. The cache maintains the frequency of each node with the help of the freq_map, and updates the min_freq accordingly to ensure that the least frequently and least recently used node is always easily identifiable and removable in constant time.

Solution Implementation

1from collections import defaultdict
2
3class Node:
4    def __init__(self, key: int, value: int) -> None:
5        self.key = key
6        self.value = value
7        self.freq = 1
8        self.prev = None
9        self.next = None
10
11
12class DoublyLinkedList:
13    def __init__(self) -> None:
14        self.head = Node(-1, -1)  # Sentinel head node
15        self.tail = Node(-1, -1)  # Sentinel tail node
16        self.head.next = self.tail
17        self.tail.prev = self.head
18
19    def add_first(self, node: Node) -> None:
20        """Add a node right after the head."""
21        node.prev = self.head
22        node.next = self.head.next
23        self.head.next.prev = node
24        self.head.next = node
25
26    def remove(self, node: Node) -> Node:
27        """Remove an existing node from the list."""
28        node.prev.next = node.next
29        node.next.prev = node.prev
30        # Clear the removed node's pointers
31        node.next, node.prev = None, None
32        return node
33
34    def remove_last(self) -> Node:
35        """Remove the last node and return it."""
36        return self.remove(self.tail.prev)
37
38    def is_empty(self) -> bool:
39        """Check if the list is empty."""
40        return self.head.next == self.tail
41
42
43class LFUCache:
44    def __init__(self, capacity: int):
45        self.capacity = capacity
46        self.min_freq = 0
47        self.key_node_map = defaultdict(Node)
48        self.freq_node_list_map = defaultdict(DoublyLinkedList)
49
50    def get(self, key: int) -> int:
51        """Get the value of the key if the key exists in the cache."""
52        if self.capacity == 0 or key not in self.key_node_map:
53            return -1
54
55        node = self.key_node_map[key]
56        self._increase_freq(node)
57        return node.value
58
59    def put(self, key: int, value: int) -> None:
60        """Set or insert the value if the key is not already present."""
61        if self.capacity == 0:
62            return
63
64        if key in self.key_node_map:
65            node = self.key_node_map[key]
66            node.value = value
67            self._increase_freq(node)
68            return
69
70        if len(self.key_node_map) == self.capacity:
71            least_freq_list = self.freq_node_list_map[self.min_freq]
72            node_to_remove = least_freq_list.remove_last()
73            del self.key_node_map[node_to_remove.key]
74
75        new_node = Node(key, value)
76        self._add_node(new_node)
77        self.key_node_map[key] = new_node
78        self.min_freq = 1  # Reset min_freq to 1 as a new node is added
79
80    def _increase_freq(self, node: Node) -> None:
81        """Increase the frequency count of a node."""
82        freq = node.freq
83        node_list = self.freq_node_list_map[freq]
84        node_list.remove(node)
85        if node_list.is_empty():
86            del self.freq_node_list_map[freq]
87            if freq == self.min_freq:
88                self.min_freq += 1
89
90        node.freq += 1
91        self._add_node(node)
92
93    def _add_node(self, node: Node) -> None:
94        """Add a node to the list that corresponds to its frequency count."""
95        freq = node.freq
96        node_list = self.freq_node_list_map[freq]
97        node_list.add_first(node)
98      
99# Example of how to use LFUCache:
100# cache = LFUCache(capacity)
101# value = cache.get(key)
102# cache.put(key, value)
103

1import java.util.HashMap;
2import java.util.Map;
3
4class LFUCache {
5
6    private final Map<Integer, Node> cache; // The map to store the key-node pairs
7    private final Map<Integer, DoublyLinkedList> frequencyMap; // The map to store the frequency-node list pairs
8    private final int capacity; // The capacity of the LFU cache
9    private int minimumFrequency; // The current minimum frequency of the nodes in the cache
10
11    public LFUCache(int capacity) {
12        this.capacity = capacity;
13        cache = new HashMap<>();
14        frequencyMap = new HashMap<>();
15    }
16
17    public int get(int key) {
18        if (capacity == 0) {
19            return -1;
20        }
21        if (!cache.containsKey(key)) {
22            return -1;
23        }
24
25        // get the node and increment its frequency
26        Node node = cache.get(key);
27        increaseFrequency(node);
28        return node.value;
29    }
30
31    public void put(int key, int value) {
32        if (capacity == 0) {
33            return;
34        }
35        if (cache.containsKey(key)) {
36            // update the value and frequency of the existing node
37            Node node = cache.get(key);
38            node.value = value;
39            increaseFrequency(node);
40            return;
41        }
42        if (cache.size() == capacity) {
43            // evict the least frequently used node, choosing the least recently used one if there's a tie
44            DoublyLinkedList leastFreqList = frequencyMap.get(minimumFrequency);
45            Node toRemove = leastFreqList.removeLast();
46            cache.remove(toRemove.key);
47        }
48        // create a new node and add it to the cache and frequency map
49        Node newNode = new Node(key, value);
50        addNodeToFrequencyList(newNode);
51        cache.put(key, newNode);
52        minimumFrequency = 1; // reset the minimum frequency
53    }
54
55    private void increaseFrequency(Node node) {
56        int currentFrequency = node.frequency;
57        DoublyLinkedList currentList = frequencyMap.get(currentFrequency);
58        currentList.remove(node);
59        if (currentList.isEmpty()) {
60            frequencyMap.remove(currentFrequency);
61            if (currentFrequency == minimumFrequency) {
62                minimumFrequency++; // increment the minimum frequency if necessary
63            }
64        }
65        node.frequency++;
66        addNodeToFrequencyList(node);
67    }
68
69    private void addNodeToFrequencyList(Node node) {
70        // add the node to the new frequency's list or create a new list if it does not exist
71        int newFrequency = node.frequency;
72        DoublyLinkedList newList = frequencyMap.getOrDefault(newFrequency, new DoublyLinkedList());
73        newList.addFirst(node);
74        frequencyMap.put(newFrequency, newList);
75    }
76
77    private static class Node {
78        int key;
79        int value;
80        int frequency; // the frequency of accesses to this node
81        Node prev;
82        Node next;
83
84        Node(int key, int value) {
85            this.key = key;
86            this.value = value;
87            frequency = 1; // initially, all nodes have frequency 1
88        }
89    }
90
91    private static class DoublyLinkedList {
92        // dummy head and tail make it easier to add/remove nodes
93        private final Node head;
94        private final Node tail;
95
96        public DoublyLinkedList() {
97            head = new Node(-1, -1);
98            tail = new Node(-1, -1);
99            head.next = tail;
100            tail.prev = head;
101        }
102
103        public void addFirst(Node node) {
104            // add a new node right after the dummy head
105            node.prev = head;
106            node.next = head.next;
107            head.next.prev = node;
108            head.next = node;
109        }
110
111        public Node remove(Node node) {
112            // remove a node from its current position
113            node.prev.next = node.next;
114            node.next.prev = node.prev;
115            node.next = null;
116            node.prev = null;
117            return node;
118        }
119
120        public Node removeLast() {
121            // remove the last node before the dummy tail (the least recently used one)
122            if (isEmpty()) {
123                return null; // list is empty, nothing to remove
124            }
125            return remove(tail.prev);
126        }
127
128        public boolean isEmpty() {
129            // check if the list is empty by seeing if the dummy head is directly connected to the dummy tail
130            return head.next == tail;
131        }
132    }
133}
134

1#include <unordered_map>
2using namespace std;
3
4// Node class representing a node in the doubly linked list
5class Node {
6public:
7    int key;        // Key of the node
8    int value;      // Value of the node
9    int freq;       // Frequency of accesses
10    Node* prev;     // Pointer to the previous node in the list
11    Node* next;     // Pointer to the next node in the list