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 MapkeyToValue; 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 Dictionarykeyfreq = 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; } }