Author at SyntaxFlow
LFU stands for Least Frequently Used. An LFU Cache is a fixed-capacity cache that evicts the item that has been accessed the fewest number of times when it runs out of space.
In simple words:
get() or put() on a key increases that key's usage frequency by 1.🧠 Think of it this way: LFU cares about how many times something was used, while LRU (its cousin problem) only cares about when it was last used. LFU is essentially "LRU, but frequency comes first."
capacity = 2capacity = 3The simplest way to track everything is to keep a dynamic array (or vector) of objects holding the key, value, frequency, and a timestamp for every element. When an eviction is needed, we scan the entire array to find the element with the minimum frequency and oldest timestamp.
Item { int key, value, freq, time; }.std::vector<Item> to store the cache contents.timer integer to simulate timestamps.get(key): Iterate through the vector. If found, update freq++, time = ++timer, and return value. Otherwise, return -1.put(key, value): Iterate through the vector. If found, update value, freq++, and time = ++timer. If not found:freq. If multiple exist, pick the one with the smallest time. Erase it.Item(key, value, 1, ++timer) to the vector.put(1,1): Vector: [{k:1, v:1, f:1, t:1}]put(2,2): Vector: [{1,1,1,1}, {2,2,1,2}]get(1): Found 1. Update. Vector: [{1,1,2,3}, {2,2,1,2}]. Returns 1.put(3,3): Cap full (2). Scan vector. Min freq is 1 (Key 2). Erase Key 2. Insert Key 3. Vector: [{1,1,2,3}, {3,3,1,4}].#include <vector>
#include <climits>
using namespace std; // Import standard namespace
// Structure to represent each cache item
struct Item {
int key; // The key of the cache entry
int val; // The value stored
int freq; // Frequency of access (how many times accessed)
int time; // Timestamp to track recency (used for tie-breaking)
};
class LFUCacheBrute {
int capacity; // Maximum number of items cache can hold
int timer; // Global timer to track recency
vector<Item> cache; // Vector to store cache items
public:
// Constructor initializes capacity and timer
LFUCacheBrute(int cap) : capacity(cap), timer(0) {}
// Get value for a given key
int get(int key) {
// Iterate through cache to find the key
for (auto& item : cache) {
if (item.key == key) {
item.freq++; // Increase frequency since accessed
item.time = ++timer; // Update timestamp to mark recent use
return item.val; // Return the stored value
}
}
return -1; // Key not found
}
// Put a key-value pair into the cache
void put(int key, int value) {
if (capacity == 0) return; // If capacity is 0, do nothing
// Check if key already exists in cache
for (auto& item : cache) {
if (item.key == key) {
item.val = value; // Update value
item.freq++; // Increase frequency
item.time = ++timer; // Update timestamp
return;
}
}
// If cache is full, evict least frequently used item
if (cache.size() == capacity) {
int minFreq = INT_MAX; // Track minimum frequency
int oldestTime = INT_MAX; // Track oldest timestamp for tie-breaking
int evictIdx = -1; // Index of item to evict
// Find item with lowest frequency (and oldest if tie)
for (int i = 0; i < cache.size(); i++) {
if (cache[i].freq < minFreq ||
(cache[i].freq == minFreq && cache[i].time < oldestTime)) {
minFreq = cache[i].freq;
oldestTime = cache[i].time;
evictIdx = i;
}
}
// Remove the chosen item
cache.erase(cache.begin() + evictIdx);
}
// Insert new item with frequency = 1 and updated timestamp
cache.push_back({key, value, 1, ++timer});
}
};
get(): — Linear scan.put(): — Linear scan to find element, plus to find the eviction candidate and to erase from the vector. Overall .Every operation scales linearly with the cache capacity. For a high-performance system serving millions of requests, per operation is unacceptable.
We can improve lookup time using a Hash Map and eviction time using a balanced Binary Search Tree (BST). By using a Red-Black tree (like std::set in C++), we can keep the elements sorted automatically by their frequency, and then by their timestamp.
std::unordered_map<int, Node>: Maps keys to their node data for lookups.std::set<Node>: Maintains nodes sorted by frequency (primary) and timestamp (secondary).get(key): Check hash map. If found, remove from set, update freq and time, re-insert into set, update hash map. Return value.put(key, value):set, update freq/time, re-insert into set.set (set.begin()) because it represents the minimum frequency/oldest time. Remove it from the hash map. Create new node, insert into set and hash map.put(1,1): Map: {1}. Set: [(f:1, t:1, k:1)]put(2,2): Map: {1, 2}. Set: [(f:1, t:1, k:1), (f:1, t:2, k:2)]get(1): Find 1 in map. Remove from set. Freq=2, t=3. Insert to set. Set: [(f:1, t:2, k:2), (f:2, t:3, k:1)]. Returns 1.put(3,3): Cap full. set.begin() is (f:1, t:2, k:2). Evict Key 2. Insert Key 3. Set: [(f:1, t:4, k:3), (f:2, t:3, k:1)].#include <unordered_map>
#include <set>
struct SetNode {
int key, val, freq, time;
bool operator<(const SetNode& other) const {
if (freq == other.freq) return time < other.time;
return freq < other.freq;
}
};
class LFUCacheBetter {
int capacity, timer;
std::unordered_map<int, SetNode> keyNode;
std::set<SetNode> bst;
public:
LFUCacheBetter(int cap) : capacity(cap), timer(0) {}
int get(int key) {
if (keyNode.find(key) == keyNode.end()) return -1;
SetNode node = keyNode[key];
bst.erase(node);
node.freq++;
node.time = ++timer;
bst.insert(node);
keyNode[key] = node;
return node.val;
}
void put(int key, int value) {
if (capacity == 0) return;
if (keyNode.find(key) != keyNode.end()) {
SetNode node = keyNode[key];
bst.erase(node);
node.val = value;
node.freq++;
node.time = ++timer;
bst.insert(node);
keyNode[key] = node;
return;
}
if (keyNode.size() == capacity) {
auto it = bst.begin();
keyNode.erase(it->key);
bst.erase(it);
}
SetNode newNode = {key, value, 1, ++timer};
bst.insert(newNode);
keyNode[key] = newNode;
}
};get(): — Hash map lookup is , but erasing and inserting into std::set takes .put(): — Map operations are , set insertion/deletion is .Significantly faster for large capacities. is highly scalable.
is great, but production caches (like those in OS, databases, or Redis) require constant time operations to handle ultra-high throughput.
The standard LFU Cache relies on grouping keys by their frequencies.
Instead of ordering all elements in a single tree, we bucket them by frequency. If we have a list of items that have been accessed 1 time, a list for 2 times, etc., we can find the minimum frequency group instantly if we just track a minFreq variable.
When a node's frequency increases, it must be removed from its current frequency list and appended to the next. A Doubly Linked List allows node removal (since we have the node pointer directly from Map 1) and insertion.
We append new/updated nodes to the head of the DLL. Thus, the tail of the DLL represents the oldest node in that specific frequency bucket. When a tie-break is needed, we simply pop the tail of the minFreq's DLL.
minFreqA variable minFreq tracks the smallest frequency currently present in the cache. When eviction occurs, we look up Map2[minFreq] and evict its LRU node. minFreq is updated to 1 on new insertions, or incremented if the DLL representing the current minFreq becomes empty.
key, value, freq, prev, and next pointers.head and tail, and a size counter. Supports addFront() and removeNode().keyNode): std::unordered_map<int, Node*> maps a key to its physical memory address.freqListMap): std::unordered_map<int, List*> maps an integer frequency to its corresponding DLL.get() step-by-stepkeyNode. If not, return -1.Node*.updateFrequency(node).put() step-by-stepcapacity == 0, exit.keyNode, update its value, and call updateFrequency(node).freqListMap[1] (using insertAfterHead()).minFreq = 1.keyNode.removeNode()Given a node pointer, rewire its neighbors:
node->prev->next = node->next
node->next->prev = node->prev
Decrement DLL size.
insertAfterHead()(Usually called addFront)
New node goes right after the dummy head.
node->next = head->next
node->prev = head
head->next->prev = node
head->next = node
Increment DLL size.
updateFrequency()freq = node->freq.freqListMap[freq].freq == minFreq AND the DLL for this freq is now empty (size == 0), increment minFreq++.node->freq++.freqListMap[node->freq] at the head.minFreq: List* list = freqListMap[minFreq].list->tail->prev.keyNode.#include <unordered_map>
#include <iostream>
using namespace std; // Import standard namespace
// Node structure representing a key-value pair and its metadata
struct Node {
int key, value, freq; // Key, value, and frequency count
Node* prev; // Pointer to previous node in DLL
Node* next; // Pointer to next node in DLL
// Constructor initializes key, value, and sets frequency = 1
Node(int k, int v) : key(k), value(v), freq(1), prev(nullptr), next(nullptr) {}
};
// Doubly Linked List to maintain LRU order within the same frequency bucket
struct List {
int size; // Number of nodes in this list
Node* head; // Dummy head node
Node* tail; // Dummy tail node
List() {
// Initialize with dummy head and tail
head = new Node(-1, -1);
tail = new Node(-1, -1);
head->next = tail;
tail->prev = head;
size = 0;
}
~List() {
delete head;
delete tail;
}
// Add node to the front (most recently used within frequency bucket)
void addFront(Node* node) {
Node* nextNode = head->next;
node->next = nextNode;
node->prev = head;
head->next = node;
nextNode->prev = node;
size++;
}
// Remove a specific node from the list
void removeNode(Node* node) {
Node* prevNode = node->prev;
Node* nextNode = node->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
size--;
}
};
class LFUCache {
private:
unordered_map<int, Node*> keyNode; // Maps key → Node
unordered_map<int, List*> freqListMap; // Maps frequency → Doubly Linked List
int maxSizeCache; // Maximum capacity of cache
int minFreq; // Tracks minimum frequency in cache
int curSize; // Current number of elements
// Helper to upgrade node to the next frequency bucket
void updateFrequency(Node* node) {
int freq = node->freq;
// Remove from current frequency list
freqListMap[freq]->removeNode(node);
// If this was the minFreq list and now empty, increment minFreq
if (freq == minFreq && freqListMap[freq]->size == 0) {
minFreq++;
}
// Increment frequency and add to new frequency list
node->freq++;
if (freqListMap.find(node->freq) == freqListMap.end()) {
freqListMap[node->freq] = new List();
}
freqListMap[node->freq]->addFront(node);
}
public:
LFUCache(int capacity) {
maxSizeCache = capacity;
minFreq = 0;
curSize = 0;
}
~LFUCache() {
// Free all allocated nodes and lists
for (auto& pair : keyNode) delete pair.second;
for (auto& pair : freqListMap) delete pair.second;
}
// Get value for a given key
int get(int key) {
if (keyNode.find(key) == keyNode.end()) {
return -1; // Key not found
}
Node* node = keyNode[key];
updateFrequency(node); // Increase frequency and move node
return node->value;
}
// Put a key-value pair into the cache
void put(int key, int value) {
if (maxSizeCache == 0) return; // No capacity
// If key already exists, update value and bump frequency
if (keyNode.find(key) != keyNode.end()) {
Node* node = keyNode[key];
node->value = value;
updateFrequency(node);
return;
}
// Eviction logic if capacity is reached
if (curSize == maxSizeCache) {
List* minFreqList = freqListMap[minFreq];
Node* lruNode = minFreqList->tail->prev; // Least recently used in minFreq bucket
keyNode.erase(lruNode->key); // Remove from key map
minFreqList->removeNode(lruNode); // Remove from list
delete lruNode; // Free memory
curSize--;
}
// Insert new node
curSize++;
minFreq = 1; // Reset min frequency to 1 for new elements
Node* newNode = new Node(key, value);
if (freqListMap.find(1) == freqListMap.end()) {
freqListMap[1] = new List();
}
freqListMap[1]->addFront(newNode);
keyNode[key] = newNode;
}
};
Capacity = 2
put(1,1)nullput(2,2)nullget(1)1put(3,3)nullget(2)-1 (Not found)get(3)3put(4,4)nullget(1)-1get(3)3get(4)4Why every operation is :
keyNode hash map.minFreq instantly points to the correct DLL, and its tail->prev instantly gives the LRU element to delete.Visualizing how node promotion works via DLLs.
Initial State (Key A freq 1, Key B freq 1):
minFreq when a node's frequency increments and it was the only node in the minFreq list. (Check if (freq == minFreq && freqListMap[freq]->size == 0) minFreq++;).capacity == 0 right at the start of put(). This will cause segmentation faults.capacity = 0: Cache size is zero. Every put should do nothing, every get should return -1. Guard against this at the very top of put().get(): A key accessed heavily will march up the frequency lists map (e.g., Map[100], Map[101]). This creates new DLLs dynamically.put() on an existing key, it should NOT reset the frequency to 1. It acts like a get() (increases frequency) but also overwrites the stored value.freq might overflow if a key is hit billions of times. In production systems (like Redis's LFU implementation), frequency is usually capped (e.g., at 255 using an 8-bit counter) or decays over time to prevent stagnant keys from permanently hogging the cache.tail is implicitly the LRU.key to its physical Node* (for instant lookups), and another mapping a frequency integer to a DLL of nodes (to handle ties using LRU).get bumps the item to the next frequency bucket. put inserts at frequency 1 (resetting minFreq to 1). If full, put pops the tail of the minFreq DLL before inserting.minFreq edge case, and you will ace the interview.code link: