The Problem can be described as follow: Design and implement a data structure for Least Recently Used (LRU) 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 reached its capacity, it should invalidate the least recently used item before inserting a new item.
And the Example is:
1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* capacity */ );
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.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
Analysis of the question
For HashMap Get/Set the time complexity is O(1), and for LinkedList Insert/Delete the time complexity is O(1). So, we are going to use these two data structure to form our solution. I will create a node as:
1
2
3
4
5
6
7
8
9
10
11
12
13
private class Node {
Node prev;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
And create two Nodes: head and tail. When we put a new value, if the capacity is full. We remove head.next, and add the new one to tail.prev. If there is still remaining space, we just add it to tail.prev directly. The following code is the complete Java code and I am going to illustrate more on the code:
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
class LRUCache {
private class Node {
Node prev;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
private int capacity;
private HashMap<Integer, Node> hm = new HashMap<Integer, Node>();
private Node head = new Node(-1, -1);
private Node tail = new Node(-1, -1);
public LRUCache(int capacity) {
this.capacity = capacity;
this.head.next = this.tail;
this.tail.prev = this.head;
}
public int get(int key) {
if (!hm.containsKey(key)) {
return -1;
}
Node current = hm.get(key);
current.prev.next = current.next;
current.next.prev = current.prev;
moveToTail(current);
return hm.get(key).value;
}
public void put(int key, int value) {
if (get(key) != -1) {
hm.get(key).value = value;
return;
}
if (hm.size() == capacity) {
hm.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}
Node insert = new Node(key, value);
hm.put(key, insert);
moveToTail(insert);
}
private void moveToTail(Node current) {
current.next = tail;
tail.prev.next = current; // update head
current.prev = tail.prev;
tail.prev = current;
}
}
Get function:
In the get function:
1
2
current.prev.next = current.next;
current.next.prev = current.prev;
is used to remove the current value we get from the its original position and call moveToTail(current); to add it to tail.prev which presents the current value.
Put function:
In the put function:
1
2
3
4
5
if (hm.size() == capacity) {
hm.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}
The above code is used for removing the Least recently used value. And then we need to put the new one into tail.prev, still by calling: Node insert = new Node(key, value);
hm.put(key, insert);
moveToTail(insert);
moveToTail function:
This function is the complex one, because the link between them sometimes makes me a bit confused. And I explain these code with a comment after each line:
1
2
3
4
current.next = tail; //Connect the current with tail
tail.prev.next = current; // update head
current.prev = tail.prev; //Connect the current with head