LRU Cache
Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class with capacity k:
get(key)— return the value if the key exists, otherwise return -1put(key, value)— update or insert. If the number of keys exceeds capacity, evict the least recently used key.
Examples
Example 1
Input: capacity=2; put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output: 1, -1, -1, 3, 4
Explanation: After put(3,3) key 2 is evicted (LRU). After put(4,4) key 1 is evicted.
Constraints
- •
1 <= capacity <= 3000 - •
0 <= key <= 10^4 - •
At most 2*10^5 calls to get and put.
Hints
Hint 1
A HashMap alone gives O(1) key lookup but no way to track recency; a doubly linked list alone gives O(1) reordering but no O(1) key lookup — combining both is what gets you O(1) on every operation.
Hint 2
The HashMap maps key -> LIST NODE (not key -> value directly) — that node reference is what lets you splice it out of its current position in O(1) without searching the list.
Hint 3
Java's built-in LinkedHashMap (with accessOrder=true) already implements this exact combination internally — worth knowing as the 'if I were allowed a library' answer, contrasted with the from-scratch version an interview usually wants.
Solutions
class LRUCache {
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0); // dummy
private final Node tail = new Node(0, 0); // dummy
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
moveToFront(node); // mark as recently used
return node.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
moveToFront(node);
} else {
if (map.size() == capacity) {
Node lru = tail.prev; // least recently used
remove(lru);
map.remove(lru.key);
}
Node node = new Node(key, value);
map.put(key, node);
addToFront(node);
}
}
private void remove(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void addToFront(Node n) {
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
}
private void moveToFront(Node n) { remove(n); addToFront(n); }
private static class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
}Time: O(1) get and put · Space: O(capacity)