[Geeks for Geeks] LRU Cache

LRU Cache

Design a data structure that works like a LRU Cache. Here cap denotes the capacity of the cache and Q denotes the number of queries. Query can be of two types:

  1. SET x y : sets the value of the key x with value y
  2. GET x : gets the key of x if present else returns -1.

The LRUCache class has two methods get() and set() which are defined as follows.

  1. get(key) : returns the value of the key if it already exists in the cache otherwise returns -1.
  2. set(key, value) : if the key is already present, update its value. If not present, add the key-value pair to the cache. If the cache reaches its capacity it should invalidate the least recently used item before inserting the new item.
  3. In the constructor of the class the capacity of the cache should be intitialized.
  • Time : O(1)
  • Space : O(cap)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class LRUCache
{
private:
list<int> nodes;
unordered_map<int, int> lookup;
unordered_map<int, list<int>::iterator> link;
int cap;
void balance(int key) { // O(1)
auto it = link[key];
nodes.erase(it);
nodes.push_front(key);
link[key] = nodes.begin();
}
void removeOverCapacity() { // O(1)
if(nodes.size() <= cap) return;
int rm = nodes.back();
nodes.pop_back();
lookup.erase(rm);
link.erase(rm);
}
public:
//Constructor for initializing the cache capacity with the given value.
LRUCache(int cap) : cap(cap) {}

//Function to return value corresponding to the key.
int get(int key) // O(1)
{
if(!lookup.count(key)) return -1;
balance(key);
return lookup[key];
}

//Function for storing key-value pair.
void set(int key, int value) // O(1)
{
if(lookup.count(key)) {
balance(key);
} else {
nodes.push_front(key);
link[key] = nodes.begin();
removeOverCapacity();
}
lookup[key] = value;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/15/PS/GeeksforGeeks/lru-cache/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.