Problem Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return -1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Solution
Approach 1 (TLE)
The naive way to solve the problem is to just maintain a list of size “capacity”. For get operation, we can simply iterate through the list and return that element. Then, remove that element from the list and move it to the end. Here, we are considering that the elements to the right are more recently.
To put an element, first we try to check if it’s already present using the get method. If get return -1, we know it’s not already present. If the size of the list is less than capacity, we can simply add the current element at the end. But if it’s >= capacity, we would need to remove the least recently used element and add our current element at the end. On the other side, if the get method returns anything but -1, we already have that “key” at least. However, the put method may have a different value. This means, we would need to update the value of the element for that particular key. When we called the get method to check if that key exists, the element would have been brought to the end of list already marking it as recently used. So, we can simply update the value of the last element in our list.
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class LRUCache {
int capacity;
LinkedList<Node> dList;
public LRUCache(int capacity) {
this.capacity = capacity;
dList = new LinkedList<>();
}
public int get(int key) {
int idx = -1;
Node node = null;
for(int i=0; i<dList.size(); i++){
if(dList.get(i).key == key){
idx = i;
node = dList.get(i);
break;
}
}
if(idx == -1) return -1;
dList.remove(node);
dList.addLast(new Node(key, node.value));
return node.value;
}
public void put(int key, int value) {
int v = get(key);
if(v == -1){
if(dList.size() < capacity){
dList.addLast(new Node(key, value));
}else{
dList.removeFirst();
dList.addLast(new Node(key, value));
}
}else if(v != value){
dList.getLast().value = value;
}
}
}
class Node{
int key;
int value;
Node(int k, int v){
key = k;
value = v;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
Approach 2 (Using HashMap | Accepted)
If we think about the problem in our first approach, it was majorly about getting some element quickly. HashMap allows us to do this in constant time. We can possibly maintain a HashMap of <Key, Node> to check if any element exists. Since that will give us a reference of the Node, we can use that to remove it and move it to the end of the list. For a single-linked list, we would still have to iterate over the elements to remove this particular element (Because to remove a Node from a singly linked list, we actually need a pointer/reference to the previous node). To make this part a bit simpler, we can make use of Doubly Linked List.
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class LRUCache {
int capacity;
LinkedList<Node> dList;
Map<Integer, Node> map;
public LRUCache(int capacity) {
this.capacity = capacity;
dList = new LinkedList<Node>();
map = new HashMap<>();
}
public int get(int key) {
//if HashMap contains the key, get its value
if(map.containsKey(key)){
//get the corresponding Node
Node n = map.get(key);
//remove that Node from the list and add it to the end
dList.remove(n); //This operation is O(n) -> this can be optimized by using Doubly Linked List
dList.addLast(n);
//return the value of that Node/element
return n.value;
}else //HashMap does not have the key, so return -1
return -1;
}
public void put(int key, int value) {
//get the current value for the given key
int currentVal = get(key);
//if the key is not present, put that to the cache
if(currentVal == -1){
//create a new node
Node node = new Node(key, value);
//if more elements can be added to the cache
if(dList.size() < capacity){
//add the current element to the end of the list
dList.addLast(node);
//also add it to the HashMap
map.put(key, node);
//full capacity
}else{
//get the least recently used node
Node toRemove = dList.getFirst();
//remove the least recently used node
dList.removeFirst();
//remove it from the HashMap also
map.remove(toRemove.key);
//add the new node to the list and hashmap
dList.addLast(node);
map.put(key, node);
}
//the key is already present
//however, it's possible that a newValue was sent in the input (in which case we would need to update the existing node)
//the good part is that when we had called the get(key) method, it would have brought this node to the end of the list marking it as most recently used
}else{
dList.getLast().value = value; //OR map.get(key).value = value;
}
}
}
class Node{
int key;
int value;
Node(int k, int v){
key = k;
value = v;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/