LFU Cache

class LFU_Cache {
    unordered_map<int, list<pair<int, int>>> freqMap; // Maps frequency to list of key-value pairs
    unordered_map<int, pair<int, list<pair<int, int>>::iterator>> keyValueStore; // Maps key to (frequency, iterator)
    int maxCapacity;
    int lowestFreq;

    void addEntry(int key, int freq, int value) {
        freqMap[freq].push_back({key, value});
        keyValueStore[key] = {freq, --freqMap[freq].end()};
    }

public:
    LFU_Cache(int capacity) : maxCapacity(capacity), lowestFreq(0) {}

    int get(int key) {
        auto it = keyValueStore.find(key);
        if (it == keyValueStore.end()) {
            return -1;
        }
        int currFreq = it->second.first;
        auto listIt = it->second.second;
        pair<int, int> keyValue = *listIt;
        freqMap[currFreq].erase(listIt);
        if (freqMap[currFreq].empty()) {
            freqMap.erase(currFreq);
            if (lowestFreq == currFreq) ++lowestFreq;
        }
        addEntry(key, currFreq + 1, keyValue.second);
        return keyValue.second;
    }

    void put(int key, int value) {
        if (maxCapacity <= 0) return;

        auto it = keyValueStore.find(key);
        if (it != keyValueStore.end()) {
            it->second.second->second = value;
            get(key);
            return;
        } 
        if (maxCapacity == keyValueStore.size()) {
            int evictKey = freqMap[lowestFreq].front().first;
            keyValueStore.erase(evictKey);
            freqMap[lowestFreq].pop_front();
            if (freqMap[lowestFreq].empty()) {
                freqMap.erase(lowestFreq);
            }
        }
        lowestFreq = 1;
        addEntry(key, 1, value);
    }
};

This LFU Cache implementation in C++ efficiently manages data retrieval and storage while respecting the Least Frequently Used (LFU) caching strategy. This strategy ensures that the least frequently accessed items are the first to be evicted when the cache reaches its maximum capacity. Here’s how this implementation works:

• Data Structures Used:

  • unordered_map<int, list<pair<int, int>>> freqMap: Maps frequencies to a list of key-value pairs.
  • unordered_map<int, pair<int, list<pair<int, int>>::iterator>> keyValueStore: Maps keys to a pair comprising frequency and an iterator pointing to the corresponding position in the frequency list.

• Constructor LFU_Cache(int capacity):

  • Initializes the cache with a specified maximum capacity. It also sets the lowestFreq to 0, indicating the starting frequency count.

• Function int get(int key):

  • Retrieves the value associated with the given key. If the key exists, it increments the frequency of key access, updates the structures, and possibly adjusts the lowestFreq if needed. If the key is not found, it returns -1.

• Function void put(int key, int value):

  • Adds or updates the key-value pair in the cache. If the key already exists, it updates the value and employs the get method to adjust the frequency. If adding a new key-value pair and the cache is at full capacity, it evicts the least frequently used item before adding the new pair. If the cache's total size hasn't reached maximum capacity, it simply adds the new key with an initial frequency of one.

• Eviction Logic:

  • When inserting a new key causes an overflow, the least frequently accessed element (indicated by lowestFreq) is removed. If multiple keys have the same lowest frequency, the one that was accessed earliest within that frequency is evicted.
  • Adjustments to lowestFreq and the removal from freqMap and keyValueStore are performed as necessary to maintain accurate frequency tracking and fast access to elements.

This implementation ensures efficient fetch and update times with operations close to O(1) under typical usage due to the constant-time complexity characteristics of unordered_maps and list operations used. By dynamically adjusting the lowestFreq and carefully handling the storage structures, it optimally manages cache size and element frequency, making it suitable for scenarios where cache efficiency is crucial.

class LeastFrequentlyUsedCache {

    private Map<Integer, Pair<Integer, Integer>> itemsMap;
    private Map<Integer, LinkedHashSet<Integer>> freqMap;
    private int lowestFrequency;
    private int maxCapacity;

    private void addItem(int k, int freq, int val) {
        itemsMap.put(k, new Pair<>(freq, val));
        freqMap.putIfAbsent(freq, new LinkedHashSet<>());
        freqMap.get(freq).add(k);
    }

    public LeastFrequentlyUsedCache(int capacity) {
        itemsMap = new HashMap<>();
        freqMap = new HashMap<>();
        lowestFrequency = 0;
        maxCapacity = capacity;
    }

    public int get(int k) {
        Pair<Integer, Integer> freqAndVal = itemsMap.get(k);
        if (freqAndVal == null) {
            return -1;
        }
        final int freq = freqAndVal.getKey();
        final Set<Integer> keysWithSameFreq = freqMap.get(freq);
        keysWithSameFreq.remove(k);
        if (keysWithSameFreq.isEmpty()) {
            freqMap.remove(freq);

            if (lowestFrequency == freq) {
                lowestFrequency++;
            }
        }
        final int val = freqAndVal.getValue();
        addItem(k, freq + 1, val);
        return val;
    }

    public void put(int k, int val) {
        if (maxCapacity <= 0) {
            return;
        }
        Pair<Integer, Integer> freqAndVal = itemsMap.get(k);
        if (freqAndVal != null) {
            itemsMap.put(k, new Pair<>(freqAndVal.getKey(), val));
            get(k);
            return;
        }
        if (maxCapacity == itemsMap.size()) {
            final Set<Integer> keysAtMinFreq = freqMap.get(lowestFrequency);
            final int oldestKey = keysAtMinFreq.iterator().next();
            itemsMap.remove(oldestKey);
            keysAtMinFreq.remove(oldestKey);
            if (keysAtMinFreq.isEmpty()) {
                freqMap.remove(lowestFrequency);
            }
        }
        lowestFrequency = 1;
        addItem(k, 1, val);
    }
}

The provided Java code implements an LFU Cache (Least Frequently Used Cache), which is a data structure used for efficient caching where the least frequently accessed items are evicted first when the cache reaches its capacity limit. Here's a breakdown of the implementation and its features:

• The class LeastFrequentlyUsedCache maintains two main data structures:

  • itemsMap: A HashMap that stores cache keys and their corresponding values and frequencies.
  • freqMap: A HashMap where frequencies are keys linked to a set of items that share the same frequency.

• Constructor:

  • Initializes itemsMap, freqMap, lowestFrequency, and maxCapacity based on the provided capacity.

• addItem(int k, int freq, int val):

  • Helper function to add or update items in both maps (itemsMap and freqMap).

• get(int k):

  • Retrieves the value for the key k if it exists, updates its frequency, adjusts the frequency map appropriately, and returns the value. If the key does not exist, -1 is returned.

• put(int k, int val):

  • Inserts a new key-value pair into the cache:
    • If the key already exists, it updates the value and then calls get(k) to adjust the frequency.
    • If the cache is at full capacity, it removes the least frequently used item before adding the new one.
    • Adjusts lowestFrequency and ensures that the element is added with an updated frequency.

• Eviction logic:

  • When adding a new item causes capacity overflow, the item with the lowest frequency is evicted. If multiple items have the same low frequency, the one added earliest amongst them is evicted.

This implementation efficiently handles the operations typical of an LFU caching mechanism, ensuring that the least frequently accessed items are the first to be removed when making space for new items. The use of LinkedHashSet for managing items with the same frequency allows for constant time complexity operations for most actions, making it suitable for scenarios where fast access to cached data is critical.

class LeastFrequentlyUsedCache:

    def __init__(self, size: int):
        self.size = size
        self.value_dict = {}
        self.freq_dict = {}
        self.freq_key_list = collections.defaultdict(collections.OrderedDict)
        self.least_freq = 0

    def get_value(self, key: int) -> int:
        if key not in self.value_dict:
            return -1
        current_freq = self.freq_dict[key]
        self.freq_dict[key] = current_freq + 1
        self.freq_key_list[current_freq].pop(key)
        if not self.freq_key_list[current_freq]:
            del self.freq_key_list[current_freq]
        self.freq_key_list[current_freq + 1][key] = 1
        if self.least_freq not in self.freq_key_list:
            self.least_freq += 1
        return self.value_dict[key]

    def store(self, key: int, value: int) -> None:
        if self.size <= 0:
            return
        if key in self.value_dict:
            self.get_value(key)
            self.value_dict[key] = value
            return

        if len(self.value_dict) == self.size:
            evict_key, _ = self.freq_key_list[self.least_freq].popitem(last=False)
            del self.value_dict[evict_key]
            del self.freq_dict[evict_key]
        self.value_dict[key] = value
        self.freq_dict[key] = 1
        self.freq_key_list[1][key] = 1
        self.least_freq = 1

The provided Python code implements a Least Frequently Used (LFU) Cache system. This specialized cache evicts the least frequently accessed items first, making it suitable for applications where frequency of access is critical for performance.

Here's a breakdown of class and methods used in the implementation:

• __init__(self, size: int): Initializes the LFU Cache with a given size. It sets up dictionaries for storing values (value_dict), frequencies (freq_dict), and frequency-specific ordered lists of keys (freq_key_list). It also initializes the least frequency tracker (least_freq).

• get_value(self, key: int) -> int: Retrieves the value associated with a specified key from the cache. If the key exists, it updates the access frequency and reorders the frequency list. If the key is absent, returns -1.

• store(self, key: int, value: int) -> None: Stores or updates a key-value pair in the cache. If adding a new key-value pair and the cache is at capacity, it evicts the least frequently used item before adding the new pair. For existing keys, it calls get_value to update the frequency, then updates the value.

Important points to handle while implementing or using this LFU Cache include:

• Ensuring the cache does not exceed its initialized size by managing evictions properly.
• Maintaining accurate frequencies for each access to optimize the eviction process.
• Implementing the frequency list with an ordered dictionary to efficiently manage updates and retrievals, enabling quick eviction of the least frequently accessed items.

The implemented LFU Cache serves as an efficient data structure for caching mechanisms where it's essential to keep the most frequently accessed data readily available while discarding rarely used data in scenarios where memory or cache size is limited.