{x}
blog image

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.

 

Example 1:

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]

Explanation
// 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(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // 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(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[4,3], cnt(4)=2, cnt(3)=3

 

Constraints:

  • 1 <= capacity <= 104
  • 0 <= key <= 105
  • 0 <= value <= 109
  • At most 2 * 105 calls will be made to get and put.

 

 

Solution Explanation for LFU Cache

This problem requires designing a Least Frequently Used (LFU) cache. The core challenge lies in maintaining both frequency and recency information for each cached item, allowing O(1) average time complexity for get and put operations. This is achieved using a combination of data structures:

  • Hash Map (Dictionary): A key to Node mapping for fast lookups. The Node contains the key, value, frequency, and pointers for doubly-linked lists.
  • Doubly Linked List: Maintains the order of least recently used items for a given frequency. This allows efficient removal of LRU items when the cache is full.
  • Frequency Map: A map of frequencies to their respective doubly linked lists. This efficiently groups nodes by frequency.

Data Structures

Node: Represents a cached item. It holds the key, value, frequency count, and pointers to its previous and next nodes within the doubly linked list for its frequency.

DoublyLinkedList: A standard doubly-linked list implementation. The addFirst method adds a node to the beginning, remove removes a specified node, and removeLast removes the last node (LRU). is_empty checks if the list is empty.

LFUCache: The main class implementing the LFU cache.

  • capacity: The maximum number of items the cache can hold.
  • minFreq: Tracks the minimum frequency count currently in the cache. This helps to identify LRU items for eviction.
  • map: A hash map mapping keys to their corresponding Node objects.
  • freqMap: A hash map mapping frequency counts to doubly linked lists, each containing nodes with that frequency.

Algorithms

get(key):

  1. Check if the cache is empty or the key doesn't exist. If so, return -1.
  2. Retrieve the Node associated with the key.
  3. Increment the node's frequency using incrFreq.
  4. Return the node's value.

put(key, value):

  1. If the cache is empty, return.
  2. If the key already exists, update its value and increment its frequency using incrFreq.
  3. If the cache is full (map.size() == capacity):
    • Obtain the least frequently used (LRU) Node from the doubly linked list associated with minFreq.
    • Remove this Node from the cache (map and freqMap).
  4. Create a new Node with the given key and value.
  5. Add this new Node to the cache (map and freqMap) using addNode.
  6. Set minFreq to 1 because we've added a new node (frequency 1).

incrFreq(node):

  1. Get the current frequency (freq) of the Node.
  2. Remove the Node from its current doubly linked list (freqMap[freq]).
  3. Update the frequency (node.freq++).
  4. Add the Node to the doubly linked list associated with the new frequency in freqMap.
  5. If the old frequency list is now empty, remove it from freqMap.
  6. If the old frequency was the minFreq, increment minFreq because the minimum frequency has shifted.

addNode(node):

  1. Get or create the doubly linked list for the node's frequency (freq) in freqMap.
  2. Add the Node to the beginning of this list.

Time Complexity

  • get(key): O(1) on average. Hash map lookup and doubly linked list operations are O(1) on average.
  • put(key, value): O(1) on average. Similar to get, the operations are primarily O(1). Even though removing the LRU item might involve traversing a list in the worst case, the average case remains O(1) due to the nature of LFU (the lists don't become overwhelmingly long).

Space Complexity

O(capacity + unique_keys). The space is dominated by the cache size and the number of unique keys stored.

The provided code in Python, Java, C++, and Rust demonstrates the implementation of this data structure and algorithms. Each language uses appropriate data structures to optimize the solution for O(1) average time complexity. The core logic remains consistent across all languages.