Solution For Lfu Cache

Problem:

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

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is 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 evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Solution:

To solve this problem, we can use a combination of a hash table and a doubly linked list. We will call the hash table the “cache,” and the doubly linked list the “freq list”.

Each node in the doubly linked list corresponds to a frequency of access. Each node has a frequency value, and a linked list of cache entries, where each entry has the same frequency value as the node it belongs to.

When a cache entry is accessed, its frequency value will be incremented and its position in the freq list will be adjusted accordingly. If the entry had the lowest frequency value in its current node’s linked list, and its new frequency value is not present in the freq list, a new node with the new frequency value will be created and inserted after the current node. If the entry’s new frequency value is present in the freq list, the entry will be moved to the linked list of its new node.

When a new entry is inserted into the cache, it will be inserted into the linked list of the node with frequency value 1. If the cache is already at capacity, the least frequently used cache entry will be evicted from the cache (which will be the entry at the head of the linked list of the node with the lowest frequency value).

The cache will contain a hash map of key-value pairs, with the key mapping to a doubly linked list node that contains the value and its frequency.

The time complexity of all operations will be O(1), assuming we can perform constant time hash map and doubly linked list operations.

Here is the implementation in Python:

class Node:
def init(self, freq):
self.freq = freq
self.prev = None
self.next = None
self.entries = set()

class LFUCache:

def __init__(self, capacity: int):
    self.capacity = capacity
    self.cache = {}
    self.freq_list_head = Node(0)

def get(self, key: int) -> int:
    if key not in self.cache:
        return -1

    # update entry frequency
    entry, freq_node = self.cache[key]
    freq_node.entries.remove(entry)

    if not freq_node.entries and freq_node != self.freq_list_head:
        # remove freq node if empty and not head
        freq_node.prev.next = freq_node.next
        freq_node.next.prev = freq_node.prev

    if freq_node.next.freq != freq_node.freq + 1:
        # create new freq node if not exist
        new_freq_node = Node(freq_node.freq + 1)
        new_freq_node.prev = freq_node
        new_freq_node.next = freq_node.next
        freq_node.next.prev = new_freq_node
        freq_node.next = new_freq_node

    # move entry to next freq node
    next_freq_node = freq_node.next
    next_freq_node.entries.add(entry)
    entry.freq_node = next_freq_node
    self.cache[key] = (entry, next_freq_node)

    return entry.value

def put(self, key: int, value: int) -> None:
    if not self.capacity:
        return

    if key in self.cache:
        # update existing entry value and frequency
        entry, freq_node = self.cache[key]
        freq_node.entries.remove(entry)

        if not freq_node.entries and freq_node != self.freq_list_head:
            # remove freq node if empty and not head
            freq_node.prev.next = freq_node.next
            freq_node.next.prev = freq_node.prev

        if freq_node.next.freq != freq_node.freq + 1:
            # create new freq node if not exist
            new_freq_node = Node(freq_node.freq + 1)
            new_freq_node.prev = freq_node
            new_freq_node.next = freq_node.next
            freq_node.next.prev = new_freq_node
            freq_node.next = new_freq_node

        # move entry to next freq node
        next_freq_node = freq_node.next
        next_freq_node.entries.add(entry)
        entry.freq_node = next_freq_node
        entry.value = value
    else:
        if len(self.cache) == self.capacity:
            # evict least frequently used cache entry
            entry_to_evict = self.freq_list_head.next.entries.pop()
            del self.cache[entry_to_evict.key]

            if not self.freq_list_head.next.entries:
                # remove freq node if empty
                self.freq_list_head.next.next.prev = self.freq_list_head
                self.freq_list_head.next = self.freq_list_head.next.next

        # insert new cache entry with freq 1
        new_entry = Entry(key, value)
        new_entry.freq_node = self.freq_list_head.next
        self.cache[key] = (new_entry, self.freq_list_head.next)
        self.freq_list_head.next.entries.add(new_entry)

class Entry:
def init(self, key, value):
self.key = key
self.value = value
self.freq_node = None

Example usage

lfu_cache = LFUCache(2)
lfu_cache.put(1, 1)
lfu_cache.put(2, 2)
print(lfu_cache.get(1)) # 1
lfu_cache.put(3, 3)
print(lfu_cache.get(2)) # -1
print(lfu_cache.get(3)) # 3
lfu_cache.put(4, 4)
print(lfu_cache.get(1)) # -1
print(lfu_cache.get(3)) # 3
print(lfu_cache.get(4)) # 4

Step by Step Implementation For Lfu Cache

import java.util.*; 
class LFUCache { 
    
    // Declaring fields 
    private int capacity; 
    private int min; 
    private Map keyToValue; 
    private Map keyToCount; 
    private Map> countToLRUKeys; 
      
    public LFUCache(int capacity) { 
        this.capacity = capacity; 
        this.min = -1; 
        this.keyToValue = new HashMap<>(); 
        this.keyToCount = new HashMap<>(); 
        this.countToLRUKeys = new HashMap<>(); 
    } 
      
    public int get(int key) { 
        if(!keyToValue.containsKey(key)) 
            return -1; 
        int count = keyToCount.get(key); 
        keyToCount.put(key, count + 1); 
        countToLRUKeys.get(count).remove(key); 
        if(count == min && countToLRUKeys.get(count).size() == 0) 
            min++; 
        if(!countToLRUKeys.containsKey(count + 1)) 
            countToLRUKeys.put(count + 1, new LinkedHashSet<>()); 
        countToLRUKeys.get(count + 1).add(key); 
        return keyToValue.get(key); 
    } 
      
    public void put(int key, int value) { 
        if(capacity <= 0) 
            return; 
        if(keyToValue.containsKey(key)) { 
            keyToValue.put(key, value); 
            get(key); 
            return; 
        } 
        if(keyToValue.size() >= capacity) { 
            int evict = countToLRUKeys.get(min).iterator().next(); 
            countToLRUKeys.get(min).remove(evict); 
            keyToValue.remove(evict); 
        } 
        min = 1; 
        keyToValue.put(key, value); 
        keyToCount.put(key, min); 
        if(!countToLRUKeys.containsKey(min)) 
            countToLRUKeys.put(min, new LinkedHashSet<>()); 
        countToLRUKeys.get(min).add(key); 
    } 
}

class LFUCache:
    
    def __init__(self, capacity):
        # initialize cache capacity and map
        self.capacity = capacity
        self.map = collections.defaultdict(collections.OrderedDict)
        self.freq = collections.defaultdict(int)
        self.min_freq = 0
        
    def get(self, key):
        # return value for key if key exists in cache
        # otherwise return -1
        if key not in self.map:
            return -1
        
        # update frequency of key
        self.freq[key] += 1
        
        # move key to end of its frequency group in map
        self.map[self.freq[key]][key] = self.map[self.freq[key]].pop(key)
        
        # if min_freq group is empty, update min_freq
        if not self.map[self.min_freq]:
            self.min_freq += 1
        
        return self.map[self.freq[key]][key]
    
    def put(self, key, value):
        # if key already exists, update value and return
        if key in self.map:
            self.map[self.freq[key]][key] = value
            self.get(key)
            return
        
        # if cache is full, remove least frequently used key
        if self.capacity == len(self.map[self.min_freq]):
            self.map[self.min_freq].popitem(last=False)
        
        # insert key into map with frequency 1
        self.freq[key] = 1
        self.min_freq = 1
        self.map[self.freq[key]][key] = value

var LFUCache = function(capacity) {
    this.capacity = capacity;
    this.size = 0;
    this.map = {};
};

LFUCache.prototype.get = function(key) {
    if (!this.map[key]) {
        return -1;
    }
    const entry = this.map[key];
    // increment the frequency
    entry.freq += 1;
    // remove the entry from the list
    this.remove(entry);
    // add the entry to the end of the list
    this.add(entry);
    return entry.value;
};

LFUCache.prototype.put = function(key, value) {
    if (this.capacity <= 0) {
        return;
    }
    let entry = this.map[key];
    if (!entry) {
        // if the key does not exist, create a new entry
        if (this.size === this.capacity) {
            // if the cache is full, remove the least frequently used entry
            const leastFreqEntry = this.head.next;
            this.remove(leastFreqEntry);
            delete this.map[leastFreqEntry.key];
        } else {
            this.size++;
        }
        entry = new Entry(0, key, value);
        this.map[key] = entry;
    } else {
        // if the key already exists, update the value
        entry.value = value;
        // increment the frequency
        entry.freq += 1;
        // remove the entry from the list
        this.remove(entry);
    }
    // add the entry to the end of the list
    this.add(entry);
};

LFUCache.prototype.remove = function(entry) {
    const prev = entry.prev;
    const next = entry.next;
    if (prev) {
        prev.next = next;
    }
    if (next) {
        next.prev = prev;
    }
    if (entry === this.head) {
        this.head = this.head.next;
    }
    if (entry === this.tail) {
        this.tail = this.tail.prev;
    }
    entry.next = null;
    entry.prev = null;
};

LFUCache.prototype.add = function(entry) {
    // if this is the first entry, set it as the head
    if (!this.head) {
        this.head = entry;
    }
    // if this entry has the same frequency as the tail, add it after the tail
    if (this.tail && this.tail.freq === entry.freq) {
        this.tail.next = entry;
        entry.prev = this.tail;
        this.tail = entry;
        return;
    }
    // if this entry has a higher frequency than the tail, add it before the tail
    if (this.tail && this.tail.freq < entry.freq) {
        entry.next = this.tail;
        this.tail.prev = entry;
        this.tail = entry;
        return;
    }
    // if this entry has a lower frequency than the tail, add it after the head
    let curr = this.head;
    while (curr) {
        if (curr.freq > entry.freq) {
            entry.next = curr;
            entry.prev = curr.prev;
            if (curr.prev) {
                curr.prev.next = entry;
            }
            curr.prev = entry;
            if (this.head === curr) {
                this.head = entry;
            }
            return;
        }
        curr = curr.next;
    }
};

var Entry = function(freq, key, value) {
    this.freq = freq;
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
};

This is a C++ implementation of an LFU cache. The cache is implemented using a hashmap and a doubly linked list. The hashmap is used to store the key-value pairs in the cache and the doubly linked list is used to store the frequencies of the keys. The head of the doubly linked list is the least frequently used key and the tail of the doubly linked list is the most frequently used key.

The time complexity of this implementation is O(1) for both the get and set operations.

#include 
#include 

using namespace std;

class LFUCache {
public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        size = 0;
        minFreq = 0;
    }
    
    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        
        // Update the key's frequency
        updateFreq(key);
        
        return cache[key].value;
    }
    
    void set(int key, int value) {
        if (capacity <= 0) {
            return;
        }
        
        if (cache.find(key) != cache.end()) {
            // Update the value for the existing key
            cache[key].value = value;
            
            // Update the key's frequency
            updateFreq(key);
            
            return;
        }
        
        // Evict the least frequently used key if the cache is full
        if (size == capacity) {
            int evictKey = freqMap[minFreq].front();
            freqMap[minFreq].pop_front();
            cache.erase(evictKey);
            size--;
        }
        
        // Insert the new key into the cache
        cache[key] = {value, 1, freqMap[1].end()};
        freqMap[1].push_back(key);
        minFreq = 1;
        size++;
    }
    
private:
    // Data structure for storing a key-value pair in the cache
    struct Pair {
        int value;
        int freq;
        list::iterator it;
    };
    
    // Hashmap for storing the key-value pairs in the cache
    unordered_map cache;
    
    // Doubly linked list for storing the frequencies of the keys
    unordered_map> freqMap;
    
    int capacity;
    int size;
    int minFreq;
    
    // Helper function for updating the frequency of a given key
    void updateFreq(int key) {
        int freq = cache[key].freq;
        freqMap[freq].erase(cache[key].it);
        cache[key].freq++;
        freqMap[cache[key].freq].push_back(key);
        cache[key].it = --freqMap[cache[key].freq].end();
        
        // Update the minimum frequency
        if (freq == minFreq && freqMap[freq].empty()) {
            minFreq++;
        }
    }
};

using System; 
using System.Collections.Generic; 

public class LFUCache { 

// maintain a minfreq to quickly find the least frequent used key 
int minfreq = 0; 

// key to frequency mapping 
Dictionary keyfreq = new Dictionary(); 

// key to value mapping 
Dictionary keyval = new Dictionary(); 

// frequency to list of keys mapping 
Dictionary> freqkey = new Dictionary>(); 

int capacity; 

public LFUCache(int capacity) { 

this.capacity = capacity; 
} 

public int Get(int key) { 

if (!keyval.ContainsKey(key)) { 

return -1; 
} 

// increment the frequency of the key 
keyfreq[key]++; 

// remove the key from the current frequency bucket 
freqkey[keyfreq[key] - 1].Remove(key); 

// if the current frequency bucket is empty, remove it 
if (freqkey[keyfreq[key] - 1].Count == 0) { 

freqkey.Remove(keyfreq[key] - 1); 
} 

// if the key is not present in the new frequency bucket, add it 
if (!freqkey.ContainsKey(keyfreq[key])) { 

freqkey[keyfreq[key]] = new List(); 
} 

freqkey[keyfreq[key]].Add(key); 

// if all the keys have the same frequency, increment the minfreq 
if (minfreq == keyfreq[key] - 1 && freqkey[minfreq].Count == 0) { 

minfreq++; 
} 

return keyval[key]; 
} 

public void Put(int key, int value) { 

// if the capacity is zero, do nothing 
if (capacity <= 0) { 

return; 
} 

// if the key already exists, update its value and return 
if (keyval.ContainsKey(key)) { 

keyval[key] = value; 
Get(key); 
return; 
} 

// if the key does not exist 

// if the cache is full, remove the least frequently used key 
if (keyval.Count == capacity) { 

// find the least frequently used key 
int evict = freqkey[minfreq][0]; 

// remove it from the key to frequency mapping 
keyfreq.Remove(evict); 

// remove it from the key to value mapping 
keyval.Remove(evict); 

// remove it from the frequency to keys mapping 
freqkey[minfreq].Remove(evict); 
} 

// if the key is not present in the new frequency bucket, add it 
if (!freqkey.ContainsKey(1)) { 

freqkey[1] = new List(); 
} 

freqkey[1].Add(key); 

// add the key to the key to frequency mapping 
keyfreq[key] = 1; 

// add the key to the key to value mapping 
keyval[key] = value; 

// set the minimum frequency to 1 
minfreq = 1; 
} 
}