LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement the `LFUCache` class: - `LFUCache(int capacity)` Initializes the object with the `capacity` of the data structure. - `int get(int key)` Gets the value of the `key` if the `key` exists in the cache. Otherwise, returns `-1`. - `void put(int key, int value)` Update the value of the `key` if present, or inserts the `key` if not already present. When the cache reaches its `capacity`, it should invalidate and remove the **least frequently used** key before inserting a new item. For this problem, when there is a **tie** (i.e., two or more keys with the same frequency), the **least recently used** key would be invalidated. To determine the least frequently used key, a **use counter** is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key. When a key is first inserted into the cache, its use counter is set to `1` (due to the `put` operation). The use counter for a key in the cache is incremented either a `get` or `put` operation is called on it. The functions `get` and `put` must each run in `O(1)` average time complexity.

Examples

Input:["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]

Output:[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

// cnt(x) = the use counter for key x // cache=[] will show the last used order for tiebreakers (leftmost element is most recent) LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // return 1 // cache=[1,2], cnt(1)=2, cnt(2)=1 lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the minimum, hit LRU rule. cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1. // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // return -1 (not found) lfu.get(3); // return 3 // cache=[3,4], cnt(3)=3, cnt(4)=1 lfu.get(4); // return 4 // cache=[4,3], cnt(4)=2, cnt(3)=3

Constraints

0 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
At most 2 * 10^5 calls will be made to get and put.

Optimal Solution

Approach

To achieve O(1) time complexity for both `get` and `put` operations, we can combine a hash map with doubly linked lists. 1. **Data Structures**: * **Node**: Stores the `key`, `value`, and its `frequency`. It also has `prev` and `next` pointers to be used in a doubly linked list. * **Doubly Linked List (DLL)**: For a specific frequency, we maintain a DLL of nodes. The head represents the most recently used (MRU) node, and the tail represents the least recently used (LRU) node. * **Key Map (`key_to_node`)**: A hash map mapping a `key` to its corresponding `Node`. This allows O(1) access to any node. * **Frequency Map (`freq_to_dll`)**: A hash map mapping a `frequency` to a `Doubly Linked List`. This keeps track of all nodes having the same frequency, ordered by recency. * **min_freq**: An integer tracking the minimum frequency among all nodes currently in the cache. 2. **Get Operation**: * If the `key` is not in `key_to_node`, return -1. * Otherwise, fetch the node. We need to update its frequency: * Remove the node from the DLL in `freq_to_dll` corresponding to its current frequency. * If this DLL becomes empty and the node's frequency was equal to `min_freq`, increment `min_freq`. * Increment the node's frequency. * Add the node to the head of the DLL in `freq_to_dll` corresponding to its new frequency. * Return the node's value. 3. **Put Operation**: * If `capacity` is 0, do nothing. * If the `key` already exists, update its value and perform the same frequency update logic as in the `get` operation. * If the `key` is new: * If the cache is at full capacity, we need to evict the LFU/LRU node: * Get the DLL corresponding to `min_freq` from `freq_to_dll`. * Remove the LRU node (which is at the tail of this DLL). * Remove the corresponding key from `key_to_node`. * Create a new node with frequency 1. * Add it to `key_to_node`. * Add it to the head of the DLL for frequency 1 in `freq_to_dll`. * Reset `min_freq` to 1.

Complexity Analysis

Time Complexity

O(1)

Space Complexity

O(N)

Solution.java

1import java.util.HashMap;2import java.util.Map;3
4class LFUCache {5    class Node {6        int key, val, freq;7        Node prev, next;8        Node(int key, int val) {9            this.key = key;10            this.val = val;11            this.freq = 1;12        }13    }14    15    class DoublyLinkedList {16        Node head, tail;17        int size;18        19        DoublyLinkedList() {20            head = new Node(0, 0);21            tail = new Node(0, 0);22            head.next = tail;23            tail.prev = head;24            size = 0;25        }26        27        void addNode(Node node) {28            node.next = head.next;29            node.prev = head;30            head.next.prev = node;31            head.next = node;32            size++;33        }34        35        void removeNode(Node node) {36            node.prev.next = node.next;37            node.next.prev = node.prev;38            size--;39        }40        41        Node popTail() {42            if (size == 0) return null;43            Node res = tail.prev;44            removeNode(res);45            return res;46        }47    }48    49    int capacity, size, minFreq;50    Map<Integer, Node> keyToNode;51    Map<Integer, DoublyLinkedList> freqToDll;52
53    public LFUCache(int capacity) {54        this.capacity = capacity;55        this.size = 0;56        this.minFreq = 0;57        this.keyToNode = new HashMap<>();58        this.freqToDll = new HashMap<>();59    }60    61    private void update(Node node) {62        int freq = node.freq;63        DoublyLinkedList dll = freqToDll.get(freq);64        dll.removeNode(node);65        if (minFreq == freq && dll.size == 0) {66            minFreq++;67        }68        node.freq++;69        freqToDll.computeIfAbsent(node.freq, k -> new DoublyLinkedList()).addNode(node);70    }71    72    public int get(int key) {73        if (!keyToNode.containsKey(key)) {74            return -1;75        }76        Node node = keyToNode.get(key);77        update(node);78        return node.val;79    }80    81    public void put(int key, int value) {82        if (capacity == 0) return;83        84        if (keyToNode.containsKey(key)) {85            Node node = keyToNode.get(key);86            node.val = value;87            update(node);88        } else {89            if (size == capacity) {90                DoublyLinkedList minDll = freqToDll.get(minFreq);91                Node lruNode = minDll.popTail();92                keyToNode.remove(lruNode.key);93                size--;94            }95            Node newNode = new Node(key, value);96            keyToNode.put(key, newNode);97            freqToDll.computeIfAbsent(1, k -> new DoublyLinkedList()).addNode(newNode);98            minFreq = 1;99            size++;100        }101    }102}