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.

Example:

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]

# LFU Cache Implementation

This response provides a detailed implementation of a Least Frequently Used (LFU) cache, including code examples, complexity analysis, and handling of edge cases.

## Problem Description

Design and implement a data structure for a Least Frequently Used (LFU) cache. The cache has a fixed capacity. When a key is accessed (either via `get` or `put`), its frequency counter is incremented. If the cache is full, the least frequently used key is evicted. If there is a tie in frequency, the least recently used key is evicted.

## Data Structures

To implement the LFU cache with O(1) average time complexity for `get` and `put` operations, we use the following data structures:

1.  **`cache` (HashMap):** Stores the key-value pairs for quick access.
2.  **`frequencyMap` (HashMap):** Stores the frequency of each key.
3.  **`frequencyListMap` (HashMap):** Maps each frequency to a doubly linked list of keys with that frequency. This allows efficient eviction of the least recently used key among those with the minimum frequency.
4.  **`minFrequency` (Integer):** Tracks the minimum frequency in the cache.

## Naive Solution

A naive solution would involve using a HashMap to store the key-value pairs and iterating through the HashMap to find the least frequently used key when eviction is necessary. This approach has a time complexity of O(n) for the `put` operation, where n is the capacity of the cache.

## Optimal Solution

The optimal solution involves using a combination of HashMaps and Doubly Linked Lists to achieve O(1) average time complexity for both `get` and `put` operations.

### Code Implementation (Java)

```java
import java.util.HashMap;
import java.util.LinkedHashSet;

class LFUCache {
    private final int capacity;
    private final HashMap<Integer, Integer> cache; // key to value
    private final HashMap<Integer, Integer> frequencyMap; // key to frequency
    private final HashMap<Integer, LinkedHashSet<Integer>> frequencyListMap; // frequency to list of keys
    private int minFrequency;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
        this.frequencyMap = new HashMap<>(capacity);
        this.frequencyListMap = new HashMap<>();
        this.minFrequency = 0;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }

        updateFrequency(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if (capacity <= 0) {
            return;
        }

        if (cache.containsKey(key)) {
            cache.put(key, value);
            updateFrequency(key);
            return;
        }

        if (cache.size() == capacity) {
            evict();
        }

        cache.put(key, value);
        frequencyMap.put(key, 1);

        if (!frequencyListMap.containsKey(1)) {
            frequencyListMap.put(1, new LinkedHashSet<>());
        }
        frequencyListMap.get(1).add(key);
        minFrequency = 1;
    }

    private void updateFrequency(int key) {
        int oldFrequency = frequencyMap.get(key);
        frequencyMap.put(key, oldFrequency + 1);

        frequencyListMap.get(oldFrequency).remove(key);
        if (frequencyListMap.get(oldFrequency).isEmpty()) {
            frequencyListMap.remove(oldFrequency);
            if (minFrequency == oldFrequency) {
                minFrequency++;
            }
        }

        int newFrequency = oldFrequency + 1;
        if (!frequencyListMap.containsKey(newFrequency)) {
            frequencyListMap.put(newFrequency, new LinkedHashSet<>());
        }
        frequencyListMap.get(newFrequency).add(key);
    }

    private void evict() {
        if (cache.isEmpty()) {
            return;
        }

        int keyToRemove = frequencyListMap.get(minFrequency).iterator().next();
        frequencyListMap.get(minFrequency).remove(keyToRemove);
        if (frequencyListMap.get(minFrequency).isEmpty()) {
            frequencyListMap.remove(minFrequency);
        }

        cache.remove(keyToRemove);
        frequencyMap.remove(keyToRemove);
    }

    public static void main(String[] args) {
        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
        System.out.println(lfu.get(1));      // return 1, cache=[1,2], cnt(2)=1, cnt(1)=2
        lfu.put(3, 3);   // 2 is the LFU key, invalidate 2. cache=[3,1], cnt(3)=1, cnt(1)=2
        System.out.println(lfu.get(2));      // return -1 (not found)
        System.out.println(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
        System.out.println(lfu.get(1));      // return -1 (not found)
        System.out.println(lfu.get(3));      // return 3, cache=[3,4], cnt(4)=1, cnt(3)=3
        System.out.println(lfu.get(4));      // return 4, cache=[4,3], cnt(4)=2, cnt(3)=3
    }
}

Code Explanation

1. Constructor: Initializes the cache with the given capacity.
2. get(key):
   • If the key exists, it retrieves the value from the cache and updates the frequency of the key.
   • Returns -1 if the key does not exist.
3. put(key, value):
   • If the cache is full, it evicts the least frequently used key.
   • Inserts the new key-value pair into the cache with a frequency of 1.
4. updateFrequency(key):
   • Increments the frequency of the key.
   • Updates the frequency list by moving the key to the new frequency.
5. evict():
   • Removes the least frequently used key from the cache.
   • The least frequently used key is the first key in the linked list associated with the minimum frequency.

Big(O) Run-time Analysis

• get(key): O(1) average case.
  • HashMap lookups and updates take O(1) time on average.
• put(key, value): O(1) average case.
  • HashMap lookups and updates take O(1) time on average.
  • Eviction takes O(1) time on average because we maintain a doubly linked list of keys for each frequency.

Big(O) Space Usage Analysis

• The space complexity is O(capacity), where capacity is the maximum number of key-value pairs the cache can hold.
• The HashMap cache stores at most 'capacity' key-value pairs.
• The HashMap frequencyMap stores at most 'capacity' key-frequency pairs.
• The HashMap frequencyListMap stores at most 'capacity' key in the worst case where all the keys have different frequency.

Edge Cases

1. Cache is Empty:
   • Handle the case where the cache is empty when trying to evict.
2. Cache is Full:
   • Ensure that the cache evicts the least frequently used key when it is full before inserting a new key.
3. Key Already Exists:
   • If the key already exists in the cache, update the value and frequency.
4. Zero Capacity:
   • If the capacity is zero, the cache should not store any data. All get operations should return -1, and put operations should do nothing.

Conclusion

The LFU cache implementation described above provides O(1) average time complexity for both get and put operations. The use of HashMaps and Doubly Linked Lists allows for efficient eviction of the least frequently used key. The code includes handling of edge cases to ensure that the cache behaves correctly in all situations.