Algorithm
Problem Name: 460. LFU Cache
Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity)Initializes the object with thecapacityof the data structure.int get(int key)Gets the value of thekeyif thekeyexists in the cache. Otherwise, returns-1.void put(int key, int value)Update the value of thekeyif present, or inserts thekeyif not already present. When the cache reaches itscapacity, 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 usedkeywould be invalidated.
To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.
When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // return 4
// cache=[4,3], cnt(4)=2, cnt(3)=3
Constraints:
0 <= capacity <= 1040 <= key <= 1050 <= value <= 109- At most
2 * 105calls will be made togetandput.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
*/
typedef struct item_s {
int key;
int val;
int ref;
// add mutex if it is used in multithreaded program
struct item_s *shadow;
struct item_s *prev;
struct item_s *next;
} item_t;
typedef struct {
int sz;
item_t **data;
item_t *head;
item_t *buff;
} LFUCache;
LFUCache* lFUCacheCreate(int capacity) {
LFUCache *p;
item_t *buff;
int i;
if (capacity < = 0) return NULL;
p = malloc(sizeof(item_t));
//assert(p);
p->data = calloc(capacity, sizeof(item_t *));
//assert(p->data);
buff = calloc(capacity, sizeof(item_t));
//assert(buff);
p->head = p->buff = &buff[0];
if (capacity > 1) {
buff[0].next = &buff[1];
for (i = 1; i < capacity - 1; i ++) {
buff[i].prev = &buff[i - 1];
buff[i].next = &buff[i + 1];
}
buff[capacity - 1].prev = &buff[capacity - 2];
}
p->sz = capacity;
return p;
}
void move2next(item_t *t, LFUCache *obj) {
item_t *a, *b;
a = t;
b = t->next;
while (b && b->ref < = t->ref) {
a = b;
b = b->next;
}
if (a != t) {
t->next->prev = t->prev;
if (t->prev) t->prev->next = t->next;
else obj->head = t->next;
a->next = t;
t->prev = a;
t->next = b;
if (b) b->prev = t;
}
}
item_t *lookup(LFUCache* obj, int key) {
item_t *t;
t = obj->data[key % obj->sz];
while (t && t->key != key) {
t = t->shadow;
}
return t;
}
int lFUCacheGet(LFUCache* obj, int key) {
item_t *t, *n, *np;
t = obj ? lookup(obj, key) : NULL;
if (!t) {
return -1;
}
t->ref ++;
move2next(t, obj);
return t->val;
}
void lFUCachePut(LFUCache* obj, int key, int value) {
item_t *t, **pp;
if (!obj) return;
t = lookup(obj, key);
if (!t) {
t = obj->head; // least frequently used
// take it out of the cache
pp = &obj->data[t->key % obj->sz];
while (*pp && *pp != t) {
pp = &(*pp)->shadow;
}
if (*pp) {
*pp = (*pp)->shadow;
}
// put it back with new key
t->key = key;
t->ref = 1;
t->shadow = obj->data[key % obj->sz];
obj->data[key % obj->sz] = t;
} else {
t->ref ++;
}
t->val = value;
move2next(t, obj);
}
void lFUCacheFree(LFUCache* obj) {
if (!obj) return;
free(obj->buff);
free(obj->data);
free(obj);
}
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
#2 Code Example with Java Programming
Code -
Java Programming
class LFUCache {
private final Map keyToNodeMap;
private final Map < Integer, Node[]> frequencyToNodeMap;
private final Map keyToFrequencyMap;
private int capacity;
private int currentCapacity;
public LFUCache(int capacity) {
this.capacity = capacity;
this.currentCapacity = 0;
this.keyToNodeMap = new HashMap < >();
this.frequencyToNodeMap = new TreeMap<>();
this.keyToFrequencyMap = new HashMap < >();
}
public int get(int key) {
if (!keyToNodeMap.containsKey(key)) {
return -1;
}
Node node = keyToNodeMap.get(key);
removeNode(node);
int currentFrequency = keyToFrequencyMap.get(key);
int newFrequency = currentFrequency + 1;
keyToFrequencyMap.put(key, newFrequency);
addNodeToFrequencyHead(node, newFrequency);
return node.val;
}
public void put(int key, int value) {
if (this.capacity == 0) {
return;
}
removeNodeIfCapacityReached(key);
Node node = getNode(key, value);
int newFrequency = keyToFrequencyMap.getOrDefault(key, 0) + 1;
keyToFrequencyMap.put(key, newFrequency);
keyToNodeMap.put(key, node);
if (newFrequency > 1) {
removeNode(node);
}
addNodeToFrequencyHead(node, newFrequency);
}
private void removeNodeIfCapacityReached(int key) {
if (!keyToNodeMap.containsKey(key) && this.currentCapacity == capacity) {
for (Integer freq : frequencyToNodeMap.keySet()) {
Node[] nodes = frequencyToNodeMap.get(freq);
if (nodes[1].prev.val == -1) {
continue;
}
Node toRemove = nodes[1].prev;
removeNode(toRemove);
keyToNodeMap.remove(toRemove.key);
keyToFrequencyMap.remove(toRemove.key);
this.currentCapacity--;
break;
}
}
}
private Node getNode(int key, int value) {
Node node;
if (keyToNodeMap.containsKey(key)) {
node = keyToNodeMap.get(key);
removeNode(node);
node.val = value;
} else {
this.currentCapacity++;
node = new Node(value, key);
}
return node;
}
private void addNodeToFrequencyHead(Node node, int newFrequency) {
if (!frequencyToNodeMap.containsKey(newFrequency)) {
Node head = new Node(-1, Integer.MIN_VALUE);
Node tail = new Node(-1, Integer.MAX_VALUE);
head.next = tail;
tail.prev = head;
frequencyToNodeMap.put(newFrequency, new Node[]{head, tail});
}
Node headNode = frequencyToNodeMap.get(newFrequency)[0];
Node nextToHead = headNode.next;
nextToHead.prev = node;
node.next = nextToHead;
headNode.next = node;
node.prev = headNode;
}
private void removeNode(Node node) {
Node prevNode = node.prev;
Node nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
private static class Node {
int val;
int key;
Node next;
Node prev;
public Node(int val, int key) {
this.val = val;
this.key = key;
}
}
}
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const LFUCache = function(capacity) {
this.min = -1;
this.capacity = capacity;
this.keyToVal = {};
this.keyToCount = {};
this.countToLRUKeys = {};
};
LFUCache.prototype.get = function(key) {
if (!this.keyToVal.hasOwnProperty(key)) return -1;
let count = this.keyToCount[key];
let idx = this.countToLRUKeys[count].indexOf(key);
if (idx !== -1) this.countToLRUKeys[count].splice(idx, 1);
if (count === this.min && this.countToLRUKeys[count].length === 0) this.min++;
putCount(key, count + 1, this.keyToCount, this.countToLRUKeys);
return this.keyToVal[key];
};
LFUCache.prototype.put = function(key, value) {
if (this.capacity < = 0) return;
if (this.keyToVal.hasOwnProperty(key)) {
this.keyToVal[key] = value; // update key's value
this.get(key); // update key's count
return;
}
if (Object.keys(this.keyToVal).length >= this.capacity) {
evict(
this.countToLRUKeys[this.min][0],
this.min,
this.keyToVal,
this.countToLRUKeys
); // evict LRU from this min count bucket
}
this.min = 1;
putCount(key, this.min, this.keyToCount, this.countToLRUKeys); // adding new key and count
this.keyToVal[key] = value; // adding new key and value
};
function evict(key, min, keyToVal, countToLRUKeys) {
let idx = countToLRUKeys[min].indexOf(key);
if (idx !== -1) countToLRUKeys[min].splice(idx, 1);
delete keyToVal[key];
}
function putCount(key, count, keyToCount, countToLRUKeys) {
keyToCount[key] = count;
if (countToLRUKeys.hasOwnProperty(count)) {
countToLRUKeys[count].push(key);
} else {
countToLRUKeys[count] = [key];
}
}
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
#4 Code Example with Python Programming
Code -
Python Programming
class Node:
def __init__(self, k, v, f):
self.key = k
self.val = v
self.freq = f
self.next = self.pre = None
class LFUCache:
def __init__(self, capacity):
self.max = capacity
self.cache = 0
self.freqLast = {}
self.Nodes = {}
self.head = self.tail = Node("#", "#", "#")
self.head.next = self.tail
self.tail.pre = self.head
def changeFreq(self, key):
node, f = self.Nodes[key], self.Nodes[key].freq
if self.freqLast[f] == node:
if node.pre.freq == f:
self.freqLast[f] = node.pre
else:
self.freqLast.pop(f)
if f + 1 in self.freqLast:
node.pre.next = node.next
node.next.pre = node.pre
node.pre = self.freqLast[f + 1]
node.next = node.pre.next
elif f in self.freqLast:
node.pre.next = node.next
node.next.pre = node.pre
node.pre = self.freqLast[f]
node.next = node.pre.next
node.pre.next = node.next.pre = node
self.freqLast[f + 1] = node
node.freq += 1
def removeFirst(self):
node, f = self.head.next, self.head.next.freq
node.pre.next = node.next
node.next.pre = node.pre
self.Nodes.pop(node.key)
if self.freqLast[f] == node:
self.freqLast.pop(f)
self.cache -= 1
def get(self, key):
if key in self.Nodes:
self.changeFreq(key)
return self.Nodes[key].val
return -1
def put(self, key, value):
if key in self.Nodes:
self.changeFreq(key)
self.Nodes[key].val = value
elif self.max:
if self.cache == self.max:
self.removeFirst()
self.cache += 1
new = Node(key, value, 1)
if 1 in self.freqLast:
new.pre = self.freqLast[1]
else:
new.pre = self.head
new.next = new.pre.next
new.pre.next = new.next.pre = new
self.freqLast[1] = self.Nodes[key] = new
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0460_LFUCache
{
private readonly SortedDictionary < int, LinkedList<int[]>> frequencyList;
private readonly Dictionary < int, LinkedListNode<int[]>> map;
private readonly int capacity;
public _0460_LFUCache(int capacity)
{
this.capacity = capacity;
frequencyList = new SortedDictionary < int, LinkedList<int[]>>();
map = new Dictionary < int, LinkedListNode<int[]>>();
}
public int Get(int key)
{
if (!map.ContainsKey(key))
return -1;
else
{
Reorder(map[key]);
}
return map[key].Value[1];
}
public void Put(int key, int value)
{
if (capacity == 0) return;
if (map.ContainsKey(key))
map[key].Value[1] = value;
else
{
if (map.Count >= capacity)
{
int min = frequencyList.Keys.First();
map.Remove(frequencyList[min].Last.Value[0]);
frequencyList[min].RemoveLast();
if (frequencyList[min].Count == 0)
frequencyList.Remove(min);
}
map.Add(key, new LinkedListNode < int[]>(new int[] { key, value, -1 }));
}
Reorder(map[key]);
}
private void Reorder(LinkedListNode < int[]> node)
{
var freq = node.Value[2];
if (frequencyList.ContainsKey(freq))
{
frequencyList[freq].Remove(node);
if (frequencyList[freq].Count == 0)
frequencyList.Remove(freq);
}
freq++;
node.Value[2]++;
if (!frequencyList.ContainsKey(freq))
frequencyList.Add(freq, new LinkedList < int[]>());
frequencyList[freq].AddFirst(node);
}
}
}
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]