LFU Cache

XXX. LFU Cache

Design

Hash Table

Linked List

Problem Statement:

Design and implement a data structure for a Least Frequently Used (LFU) cache. The LFU Cache should support the following operations:

• get(key): Retrieve the value of the key if the key exists in the cache, otherwise return -1.
• put(key, value): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the cache reaches its capacity, it should invalidate the least frequently used item.

In case of a tie in frequency, the least recently used key should be invalidated.

Approach:

1. Use three hash maps:
   • vals: Stores the key-value pairs.
   • counts: Tracks the frequency of each key.
   • lists: Maps frequency counts to a linked hash set of keys to track order.
2. Maintain a min variable to track the minimum frequency.
3. For the get operation:
   • Update the frequency of the key.
   • Move the key to the appropriate frequency bucket in lists.
   • Return the value from vals.
4. For the put operation:
   • If the key exists, update its value and frequency.
   • If the cache is at capacity, remove the least frequently used key (and the least recently used key in case of a tie).
   • Add the new key-value pair to vals and update its frequency.

Complexity:

Time Complexity: O(1) for both get and put, amortized.
Space Complexity: O(n), where n is the capacity of the cache.

Java Implementation:

class LFUCache {
    HashMap vals;
    HashMap counts;
    HashMap> lists;
    
    int cap;
    int min = -1;
    
    public LFUCache(int capacity) {
        cap = capacity;
        vals = new HashMap<>();
        counts = new HashMap<>();
        lists = new HashMap<>();

        lists.put(1, new LinkedHashSet<>());
    }
    
    public int get(int key) {
        if(!vals.containsKey(key))
            return -1;
        int count = counts.get(key);
        counts.put(key, count+1);
        lists.get(count).remove(key);

        if(count == min && lists.get(count).size() == 0)
            min++;

        if(!lists.containsKey(count+1))
            lists.put(count+1, new LinkedHashSet<>());

        lists.get(count+1).add(key);
        return vals.get(key);
    }
    
    public void put(int key, int value) {
        if(cap <= 0)
            return;

        if(vals.containsKey(key)) {
            vals.put(key, value);
            get(key);
            return;
        } 

        if(vals.size() >= cap) {
            int evit = lists.get(min).iterator().next();
            lists.get(min).remove(evit);
            vals.remove(evit);
        }

        vals.put(key, value);
        counts.put(key, 1);

        min = 1;
        lists.get(1).add(key);
    }
}