LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
Constraints:
- 1 <= capacity <= 1000
- 0 <= key <= 1000
- 0 <= value <= 1000
- At most 3000 operations will be performed.
Examples:
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); lRUCache.put(2, 2); lRUCache.get(1); // return 1 lRUCache.put(3, 3); // evict key 2 lRUCache.get(2); // return -1 (not found) lRUCache.put(4, 4); // evict key 1 lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4
Solutions
Hash Table and Doubly Linked List
We use a hash table to store the keys and values, and a doubly linked list to keep track of the order of the elements. When we get a key, we move it to the end of the list. When we put a key, we add it to the end of the list and remove the first element if the list is full.
import java.util.HashMap;
import java.util.Map;
import java.util.LinkedHashMap;
public
class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity;
}
}Follow-up:
How would you implement the LRU cache if you were not allowed to use a hash table?
