Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class. Here is how it should be implemented:

• LFUCache(capacity): This function initializes the object with the capacity of the data structure.

• Get(key): This function gets the value of the key if it exists in the cache. Otherwise, it returns -1.

• Put(key, value): This function updates the value of the key if present, or inserts the key if it’s not 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’s a tie, that is, two or more keys have the same frequency, the least recently used key is invalidated.

To determine the least frequently used key, a UseCounter is maintained for each key in the cache. The key with the smallest UseCounter is the least frequently used key. When a key is first inserted into the cache, its UseCounter is set to 1 (due to the Put() operation). The UseCounter for a key in the cache is incremented and either a Get() or Put() operation is called on it.

The Get and Put functions should both run with an average time complexity of $O(1)$.

Constraints:

• $0 \leq$ capacity $\leq 10^4$

• $0 \leq$ key $\leq 10^5$

• $0 \leq$ value $\leq 10^5$

• At most $2×10^3$ calls will be made to Get() and Put().

The LFU cache algorithm tracks how often each key is accessed to determine which keys to remove when the cache is full. It uses one hash map to store key-value pairs and another to group keys by their access frequency. Each group in this frequency hash map contains nodes arranged in a doubly linked list. Additionally, it keeps track of the current least frequency to quickly identify the least used keys. When the cache reaches its limit, the key with the lowest frequency is removed first, specifically from the head of the corresponding linked list.

Each time a key is accessed, its frequency increases, and its position in the frequency hash map is updated, ensuring that the least used keys are prioritized for removal. This is where the doubly linked list is helpful, as the node being updated might be located somewhere in the middle of the list. Shifting the node to the next frequency level can be done in constant time, making the update process efficient.

Let’s discuss the algorithm of the LFU cache data structure in detail. We maintain two hash maps, data and freqMap, and an integer, lfu, as follows:

• data keeps the key-node pairs.

  • The node contains three values: key, value, and UseCounter.

• freqMap maintains doubly linked lists against every frequency existing in the data.

  • For example, all the keys that have been accessed only once reside in the double linked list stored at freqMap[1], all the keys that have been accessed twice reside in the double linked list stored at freqMap[2], and so on.

• lfu keeps the frequency of the least frequently used key.

Apart from the required functions i.e., Get and Put, we implement a helper function, PromoteKey that helps us maintain the order of the keys with respect to the frequency of their use. This function is implemented as follows:

• First, retrieve the node associated with the key.

• If node's UseCounter is $0$, the key is new. We simply increment its UseCounter and insert it at the tail of the linked list corresponding to the frequency $1$.

• Otherwise, detach the node from its corresponding linked list.

  • If the corresponding linked list becomes empty after detaching the node, and the node’s UseCounter equals lfu, there's no key left with a frequency equal to lfu. Hence, increment lfu.

• Increment UseCounter of the key.

• Insert node at the tail of the linked list associated with the frequency corresponding to the updated UseCounter.

  • Before inserting it, check if the linked list exists. Suppose it doesn’t, create one.

After implementing PromoteKey(), the LFU cache functions are implemented as follows:

• Get: We check if the key exists in the cache.

  • If it doesn't, we return $-1$.

  • Otherwise, we promote the key using PromoteKey() function and return the value associated with the key.

• Put: We check if the key exists in the cache.

  • If it doesn't, we must add this (key, value) pair to our cache.

    • Before adding it, we check if the cache has already reached capacity. If it has, we remove the LFU key. To do that, we remove the head node of the linked list accociated with the frequency equal to lfu.

  • If it does, we simply update key with the value.

  • At the end of both steps, we adjust the frequency order of the key using PromoteKey().

Let’s look at the following illustration to get a better understanding of the solution: