# 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.

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 = {}

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
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
entry.freq_node = next_freq_node
entry.value = value
else:
if len(self.cache) == self.capacity:
# evict least frequently used cache entry
del self.cache[entry_to_evict.key]

# remove freq node if empty

# insert new cache entry with freq 1
new_entry = Entry(key, value)
``````

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))
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))
}
}```
```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
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
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
};

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.tail) {
this.tail = this.tail.prev;
}
entry.next = null;
entry.prev = null;
};

// if this is the first entry, set it as the head
}
// 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
while (curr) {
if (curr.freq > entry.freq) {
entry.next = curr;
entry.prev = curr.prev;
if (curr.prev) {
curr.prev.next = entry;
}
curr.prev = 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.end()};
freqMap.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();
}

// 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];

// 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 = new List();
}

// 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;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]