Lfu Cache

                                            
class LFUCache {
private:
    int capacity;
    int minFreq;
    unordered_map<int, pair<int, int>> cache;
    unordered_map<int, list<int>::iterator> keyIter;
    unordered_map<int, list<int>> freqKeys;

public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        minFreq = 0;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        int value = cache[key].first;
        int freq = cache[key].second;
        updateFreq(key, value, freq);
        return value;
    }

    void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (cache.find(key) != cache.end()) {
            cache[key].first = value;
            updateFreq(key, value, cache[key].second);
        } else {
            if (cache.size() >= capacity) {
                int minKey = freqKeys[minFreq].back();
                freqKeys[minFreq].pop_back();
                if (freqKeys[minFreq].empty()) {
                    freqKeys.erase(minFreq);
                }
                cache.erase(minKey);
                keyIter.erase(minKey);
            }
            cache[key] = {value, 1};
            minFreq = 1;
            freqKeys[1].push_front(key);
            keyIter[key] = freqKeys[1].begin();
        }
    }

private:
    void updateFreq(int key, int value, int freq) {
        freqKeys[freq].erase(keyIter[key]);
        if (freqKeys[freq].empty()) {
            if (freq == minFreq) {
                minFreq++;
            }
            freqKeys.erase(freq);
        }
        cache[key].second++;
        freqKeys[freq + 1].push_front(key);
        keyIter[key] = freqKeys[freq + 1].begin();
    }
};
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

                                            
class LFUCache {
    
    Map<Integer, Integer> keyToVal;
    Map<Integer, Integer> keyToCount;
    Map<Integer, Integer> countToFreq;
    Map<Integer, LinkedHashSet<Integer>> freqToKeys;
    int capacity;
    int minFreq;

    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToCount = new HashMap<>();
        countToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        freqToKeys.put(1, new LinkedHashSet<>());
        this.capacity = capacity;
        this.minFreq = 1;
    }

    public int get(int key) {
        if (!keyToVal.containsKey(key)) {
            return -1;
        }
        int freq = keyToCount.get(key);
        int newFreq = freq + 1;
        keyToCount.put(key, newFreq);
        countToFreq.put(freq, countToFreq.get(freq) - 1);
        countToFreq.put(newFreq, countToFreq.getOrDefault(newFreq, 0) + 1);

        if (freq == minFreq && countToFreq.get(freq) == 0) {
            minFreq = newFreq;
        }

        freqToKeys.get(freq).remove(key);
        freqToKeys.putIfAbsent(newFreq, new LinkedHashSet<>());
        freqToKeys.get(newFreq).add(key);

        return keyToVal.get(key);
    }

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

        if (!keyToVal.containsKey(key)) {
            if (keyToVal.size() >= capacity) {
                int removedKey = freqToKeys.get(minFreq).iterator().next();
                keyToVal.remove(removedKey);
                keyToCount.remove(removedKey);
                freqToKeys.get(minFreq).remove(removedKey);
                countToFreq.put(minFreq, countToFreq.get(minFreq) - 1);
            }
            keyToVal.put(key, value);
            keyToCount.put(key, 1);
            countToFreq.put(1, countToFreq.getOrDefault(1, 0) + 1);
            freqToKeys.get(1).add(key);
            minFreq = 1;
        } else {
            keyToVal.put(key, value);
            int freq = keyToCount.get(key);
            int newFreq = freq + 1;
            keyToCount.put(key, newFreq);
            countToFreq.put(freq, countToFreq.get(freq) - 1);
            countToFreq.put(newFreq, countToFreq.getOrDefault(newFreq, 0) + 1);

            if (freq == minFreq && countToFreq.get(freq) == 0) {
                minFreq = newFreq;
            }

            freqToKeys.get(freq).remove(key);
            freqToKeys.putIfAbsent(newFreq, new LinkedHashSet<>());
            freqToKeys.get(newFreq).add(key);
        }
    }
}

                                            
/**
 * @param {number} capacity
 */
var LFUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.freqMap = new Map();

    this.get = function(key) {
        if (this.cache.has(key)) {
            const [value, freq] = this.cache.get(key);
            this.cache.set(key, [value, freq + 1]);
            this.freqMap.get(freq).delete(key);

            if (this.freqMap.get(freq).size === 0) {
                this.freqMap.delete(freq);
            }

            if (!this.freqMap.has(freq + 1)) {
                this.freqMap.set(freq + 1, new Set());
            }
            this.freqMap.get(freq + 1).add(key);

            return value;
        } else {
            return -1;
        }
    };

    this.put = function(key, value) {
        if (this.capacity === 0) return;

        if (this.cache.has(key)) {
            const [, freq] = this.cache.get(key);
            this.cache.set(key, [value, freq + 1]);

            this.freqMap.get(freq).delete(key);

            if (this.freqMap.get(freq).size === 0) {
                this.freqMap.delete(freq);
            }

            if (!this.freqMap.has(freq + 1)) {
                this.freqMap.set(freq + 1, new Set());
            }
            this.freqMap.get(freq + 1).add(key);
        } else {
            if (this.cache.size === this.capacity) {
                const minFreq = Math.min(...this.freqMap.keys());
                const lfu = this.freqMap.get(minFreq).values().next().value;

                this.cache.delete(lfu);
                this.freqMap.get(minFreq).delete(lfu);
                if (this.freqMap.get(minFreq).size === 0) {
                    this.freqMap.delete(minFreq);
                }
            }

            this.cache.set(key, [value, 1]);
            if (!this.freqMap.has(1)) {
                this.freqMap.set(1, new Set());
            }
            this.freqMap.get(1).add(key);
        }
    };
};

                                            
class LFUCache {
    capacity: number;
    cache: Map<number, number>;
    frequency: Map<number, number>;
    timestamp: Map<number, number>;
    
    constructor(capacity: number) {
        this.capacity = capacity;
        this.cache = new Map();
        this.frequency = new Map();
        this.timestamp = new Map();
    }

    get(key: number): number {
        if (!this.cache.has(key)) {
            return -1;
        }

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

    put(key: number, value: number): void {
        if (this.capacity === 0) {
            return;
        }

        if (this.cache.size >= this.capacity && !this.cache.has(key)) {
            this.evict();
        }

        this.cache.set(key, value);
        this.updateFrequency(key);
    }

    private updateFrequency(key: number): void {
        const currFreq = this.frequency.get(key) || 0;
        this.frequency.set(key, currFreq + 1);
        this.timestamp.set(key, Date.now());
    }

    private evict(): void {
        let minFreq = Infinity;
        let oldestTime = Infinity;
        let keyToRemove: number | null = null;

        for (const [key, freq] of this.frequency) {
            if (freq < minFreq || (freq === minFreq && this.timestamp.get(key)! < oldestTime)) {
                minFreq = freq;
                keyToRemove = key;
                oldestTime = this.timestamp.get(key)!;
            }
        }

        if (keyToRemove !== null) {
            this.cache.delete(keyToRemove);
            this.frequency.delete(keyToRemove);
            this.timestamp.delete(keyToRemove);
        }
    }
}

                                            
class LFUCache(capacity: Int) {
    private val cache = hashMapOf<Int, Int>()
    private val frequencyMap = hashMapOf<Int, Int>()
    private val usedMap = hashMapOf<Int, Int>()
    private var minFrequency = 0
    private val maxCapacity = capacity

    fun get(key: Int): Int {
        if (!cache.containsKey(key)) {
            return -1
        }
        updateFrequency(key)
        return cache[key] ?: -1
    }

    fun put(key: Int, value: Int) {
        if (maxCapacity <= 0) return

        if (cache.containsKey(key)) {
            cache[key] = value
            updateFrequency(key)
        } else {
            if (cache.size >= maxCapacity) {
                evictLeastUsed()
            }
            cache[key] = value
            frequencyMap[key] = 1
            minFrequency = 1
        }
        updateFrequency(key)
    }

    private fun updateFrequency(key: Int) {
        val frequency = frequencyMap.getOrDefault(key, 0)
        frequencyMap[key] = frequency + 1
        val used = usedMap.getOrDefault(key, 0)
        usedMap[key] = used + 1

        if (frequency > 0) {
            val keys = frequencyMap.filterValues { it == frequency }.keys
            keys.forEach { updateLru(it) }
            if (frequency == minFrequency && keys.isEmpty()) {
                minFrequency++
            }
        }
    }

    private fun updateLru(key: Int) {
        val used = usedMap[key] ?: 0
        usedMap[key] = used + 1
    }

    private fun evictLeastUsed() {
        val keys = frequencyMap.filterValues { it == minFrequency }.keys
        var leastUsedKey = -1
        var minUsed = Int.MAX_VALUE
        for (key in keys) {
            val used = usedMap.getOrDefault(key, 0)
            if (used < minUsed) {
                minUsed = used
                leastUsedKey = key
            }
        }
        if (leastUsedKey != -1) {
            cache.remove(leastUsedKey)
            frequencyMap.remove(leastUsedKey)
            usedMap.remove(leastUsedKey)
        }
    }
}

                                            
class LFUCache
=begin
    :type capacity: Integer
    def initialize(capacity)
        
    end

    :type key: Integer
    :rtype Integer
    def get(key)
        
    end

    :type key: Integer
    :type value: Integer
    :rtype nil
    def put(key, value)
        
    end
=end
    def initialize(capacity)
        @capacity = capacity
        @cache = {}
        @freq = {}
        @min_freq = 0
    end

    def get(key)
        return -1 if !@cache.key?(key)

        value, freq = @cache[key]
        update_freq(key, value, freq)
        value
    end

    def put(key, value)
        return if @capacity == 0

        if @cache.key?(key)
            _, cur_freq = @cache[key]
            update_freq(key, value, cur_freq)
        else
            if @cache.size >= @capacity
                remove_lfu
            end
            add_new_key(key, value)
        end
    end

    private

    def update_freq(key, value, freq)
        @freq[freq].delete(key)
        @freq[freq].shift if @freq[freq].empty?

        @freq[freq + 1] ||= []
        @freq[freq + 1] << key
        @cache[key] = [value, freq + 1]

        if !@freq.key?(@min_freq) || @freq[@min_freq].empty?
            @min_freq += 1
        end
    end

    def remove_lfu
        lfu_key = @freq[@min_freq].shift
        @cache.delete(lfu_key)
    end

    def add_new_key(key, value)
        @cache[key] = [value, 1]
        @freq[1] ||= []
        @freq[1] << key
        @min_freq = 1
    end
end

                                            
import scala.collection.mutable

class LFUCache(_capacity: Int) {
    case class Node(key: Int, var value: Int, var freq: Int)
    
    var capacity: Int = _capacity
    var minFreq: Int = 0
    var cache: mutable.Map[Int, Node] = mutable.Map.empty
    var freqMap: mutable.Map[Int, mutable.LinkedHashSet[Node]] = mutable.Map.empty

    def increaseFreq(node: Node): Unit = {
        val freq = node.freq
        freqMap(freq) -= node
        if (freqMap(freq).isEmpty) {
            freqMap -= freq
            if (minFreq == freq) minFreq += 1
        }
        
        node.freq += 1
        freqMap.getOrElseUpdate(node.freq, mutable.LinkedHashSet.empty) += node
    }

    def get(key: Int): Int = {
        cache.get(key) match {
            case Some(node) =>
                increaseFreq(node)
                node.value
            case None => -1
        }
    }

    def put(key: Int, value: Int): Unit = {
        if (capacity == 0) return
        
        cache.get(key) match {
            case Some(node) =>
                node.value = value
                increaseFreq(node)
            case None =>
                if (cache.size == capacity) {
                    val toEvict = freqMap(minFreq).head
                    cache -= toEvict.key
                    freqMap(minFreq) -= toEvict
                    if (freqMap(minFreq).isEmpty) {
                        freqMap -= minFreq
                    }
                }
                
                val node = Node(key, value, 1)
                cache(key) = node
                freqMap.getOrElseUpdate(1, mutable.LinkedHashSet.empty) += node
                minFreq = 1
        }
    }
}

Explanation

To solve this coding challenge, we need to implement a Least Frequently Used (LFU) cache. An LFU cache evicts the least frequently used items when the cache reaches its capacity. If there is a tie (multiple keys with the same frequency), the least recently used key will be evicted first. The main challenge here is to maintain quick (average O(1) time complexity) access and update operations, which requires efficient data structures to keep track of both the access frequency and the recency of each element.

Key Concepts:

Capacity Constraint : The cache should only store up to a specified number of items.
Frequency Tracking : Each key in the cache has an associated frequency which increments every time the key is accessed or updated.
Least Recently Used : If multiple keys have the same frequency, the key that was least recently accessed should be evicted first.
O(1) Operations : Both
get

and
put

operations need to have an average time complexity of O(1).

Data Structures:

Cache Dictionary : This maps keys to their values and their current frequency.
Frequency Map : A dictionary where the keys are frequencies, and the values are sets containing all keys that have the same frequency. This helps quickly find the least frequently used keys and manage ties effectively.
Recency Tracking : The order within each frequency set will help break ties based on recency.

Procedures:

Initialization (
__init__

) : Set up the capacity, cache dictionary, and frequency map.
Get Operation (
get

) : Check if the key exists. If it does, update its frequency and recency, then return its value.
Put Operation (
put

) : Update the value and frequency of an existing key, or insert a new key. If the cache exceeds capacity, find and remove the least frequently and least recently used key.

Detailed Steps in Pseudocode

Initialize LFU Cache :

Initialize with a capacity.
Create an empty cache dictionary and a frequency map.

                                            
Function LFUCache(capacity):
Initialize cache as an empty dictionary
Initialize freq_map as an empty dictionary
Initialize min_freq as 0
Set the given capacity
EndFunction

Get Value :

Check if the key exists in the cache.
Fetch the value and frequency.
Increment the frequency.
Update the frequency map.
Return the value if found, otherwise return -1.

                                            
Function get(key):
If key is not in cache:
Return -1
Else:
(value, frequency) = cache[key]
Increment frequency
Remove key from freq_map[frequency]
If freq_map[frequency] is empty:
Remove freq_map[frequency]
If min_freq equals frequency:
Increment min_freq
Add key to freq_map[frequency + 1]
Update cache[key] to (value, frequency + 1)
Return value
EndFunction

Put Value :

If the capacity is 0, do nothing.
If the key exists, update the value and frequency.
If the key doesn’t exist, handle the insertion:

If the cache is at capacity, evict the least frequently and least recently used key.
Insert the new key with a frequency of 1.

                                            
Function put(key, value):
    If cache capacity is 0:
        Return
    If key is in cache:
        (old_value, frequency) = cache[key]
        Update cache[key] to (value, frequency + 1)
        Remove key from freq_map[frequency]
        If freq_map[frequency] is empty:
            Remove freq_map[frequency]
            If min_freq equals frequency:
                Increment min_freq
        Add key to freq_map[frequency + 1]
    Else:
        If cache is at capacity:
            Least_frequency = min_freq
            Remove least_recent_key from freq_map[Least_frequency]
            If freq_map[Least_frequency] is empty:
                Remove freq_map[Least_frequency]
            Remove least_recent_key from cache
        Add key to cache with value and frequency 1
        Add key to freq_map[1]
        Set min_freq to 1
EndFunction

In this way, the LFU cache manages both space and time efficiency by using appropriate data structures and algorithms. The above steps detail every aspect of the LFU Cache's operations, ensuring all edge cases and constraints are handled properly.