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.
Follow up:
Could you do get and put in O(1) time complexity?
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
- 1 <= capacity <= 3000
- 0 <= key <= 3000
- 0 <= value <= 104
- At most 3 * 104 calls will be made to get and put.
import java.util.Hashtable;
class LRUCache {
// 定义一个内部类，存储LRU节点
class DLinkedNode {
// key
int key;
// value
int value;
// 前一个节点
DLinkedNode pre;
// 后一个节点
DLinkedNode post;
}
/**
* Always add the new node right after head;
*/
private void addNode(DLinkedNode node) {
node.pre = head;
node.post = head.post;
head.post.pre = node;
head.post = node;
}
/**
* Remove an existing node from the linked list.
*/
private void removeNode(DLinkedNode node){
DLinkedNode pre = node.pre;
DLinkedNode post = node.post;
pre.post = post;
post.pre = pre;
}
/**
* Move certain node in between to the head.
*/
private void moveToHead(DLinkedNode node){
this.removeNode(node);
this.addNode(node);
}
// pop the current tail.
private DLinkedNode popTail(){
DLinkedNode res = tail.pre;
this.removeNode(res);
return res;
}
private Hashtable<Integer, DLinkedNode> cache = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;
head = new DLinkedNode();
head.pre = null;
tail = new DLinkedNode();
tail.post = null;
head.post = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if(node == null){
// should raise exception here.
return -1;
}
// move the accessed node to the head;
this.moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null){
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
this.cache.put(key, newNode);
this.addNode(newNode);
++count;
if(count > capacity){
// pop the tail
DLinkedNode tail = this.popTail();
this.cache.remove(tail.key);
--count;
}
}else{
// update the value.
node.value = value;
this.moveToHead(node);
}
}
}
/**
* 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);
*/This is the laziest implementation using Java's LinkedHashMap. In the real interview, however, it is definitely not what interviewer expected.
import java.util.LinkedHashMap;
public class LRUCache {
private LinkedHashMap<Integer, Integer> map;
private final int CAPACITY;
public LRUCache(int capacity) {
CAPACITY = capacity;
map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > CAPACITY;
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void set(int key, int value) {
map.put(key, value);
}
}Several points to mention:
In the constructor, the third boolean parameter specifies the ordering mode. If we set it to true, it will be in access order. (https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#LinkedHashMap-int-float-boolean-) By overriding removeEldestEntry in this way, we do not need to take care of it ourselves. It will automatically remove the least recent one when the size of map exceeds the specified capacity.(https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#removeEldestEntry-java.util.Map.Entry-) Below is a "normal" HashMap + doubly-linked list implementation:
public class LRUCache {
private class Node{
int key, value;
Node prev, next;
Node(int k, int v){
this.key = k;
this.value = v;
}
Node(){
this(0, 0);
}
}
private int capacity, count;
private Map<Integer, Node> map;
private Node head, tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.count = 0;
map = new HashMap<>();
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node n = map.get(key);
if(null==n){
return -1;
}
update(n);
return n.value;
}
public void set(int key, int value) {
Node n = map.get(key);
if(null==n){
n = new Node(key, value);
map.put(key, n);
add(n);
++count;
}
else{
n.value = value;
update(n);
}
if(count>capacity){
Node toDel = tail.prev;
remove(toDel);
map.remove(toDel.key);
--count;
}
}
private void update(Node node){
remove(node);
add(node);
}
private void add(Node node){
Node after = head.next;
head.next = node;
node.prev = head;
node.next = after;
after.prev = node;
}
private void remove(Node node){
Node before = node.prev, after = node.next;
before.next = after;
after.prev = before;
}
}