LRU Cache Low Level Design is one of the most frequently asked problems in software engineering interviews at Google, Microsoft, Amazon, and startups. It tests both your data structure knowledge (HashMap + Doubly Linked List for O(1) operations) and your OOP design skills. This complete LRU cache LLD guide covers the full solution with Java code, class diagram, TTL support, and thread safety.
Why Interviewers Ask LRU Cache LLD
LRU Cache bridges algorithms and system design. Interviewers use it to test:
- Do you know why a HashMap alone is not enough — it has no ordering?
- Can you combine two data structures to achieve O(1) get and put?
- Do you think about thread safety for concurrent access?
- Can you extend it with TTL support or an LFU variant?
- Do you encapsulate internals properly with a private Node class?
Functional Requirements
- get(key): return value if present and move key to most-recently-used position, else return -1
- put(key, value): insert or update. If at capacity, evict the least recently used entry first
- Capacity is fixed at construction time
- Both get and put must run in O(1) time
Non-Functional Requirements
- Thread-safe: concurrent get/put must not corrupt cache state
- Optional: TTL — entries expire after a configurable duration
- Optional: eviction listener — callback when an entry is evicted
Why HashMap + Doubly Linked List?
A HashMap gives O(1) lookup but no ordering. A Queue gives ordering but O(n) lookup. Combining them: the map stores node references for O(1) lookup, and the doubly linked list gives O(1) move-to-front and O(1) remove-from-tail via direct pointer manipulation. This is the key insight interviewers want to hear.
Text-Based Class Diagram
LRUCache +-- capacity: int +-- map: HashMap<Integer, Node> +-- head: Node (dummy, most-recent end) +-- tail: Node (dummy, least-recent end) +-- get(key): int +-- put(key, value): void +-- moveToFront(node): void +-- addToFront(node): void +-- removeNode(node): void +-- evictLRU(): void Node (private inner class) +-- key: int +-- val: int +-- prev: Node +-- next: Node
LRU Cache Implementation — Java
public class LRUCache {
private final int capacity;
private final Map<Integer, Node> map;
private final Node head; // dummy, most-recent side
private final Node tail; // dummy, least-recent side
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
moveToFront(node);
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) evictLRU();
Node node = new Node(key, value);
map.put(key, node);
addToFront(node);
}
}
private void moveToFront(Node node) { removeNode(node); addToFront(node); }
private void addToFront(Node node) {
node.next = head.next; node.prev = head;
head.next.prev = node; head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void evictLRU() {
Node lru = tail.prev;
removeNode(lru);
map.remove(lru.key);
}
private static class Node {
int key, val; Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
}Thread-Safe LRU Cache
public class ThreadSafeLRUCache {
private final LRUCache cache;
private final ReentrantLock lock = new ReentrantLock();
public ThreadSafeLRUCache(int capacity) { this.cache = new LRUCache(capacity); }
public int get(int key) {
lock.lock();
try { return cache.get(key); } finally { lock.unlock(); }
}
public void put(int key, int value) {
lock.lock();
try { cache.put(key, value); } finally { lock.unlock(); }
}
}Key Design Decisions
- Dummy head and tail nodes: Sentinel nodes eliminate null checks in addToFront and removeNode, making the code cleaner and less error-prone.
- Store key in Node: When evicting the LRU node you need to remove it from the map. Storing the key in Node lets you do map.remove(lru.key) without a reverse lookup.
- Write lock for get: get modifies list order (moves node to front), so it cannot use a read lock. Using a read lock for get is a common interview mistake.
Common Follow-Up Questions
- "How would you implement an LFU cache?" — Use two maps: key-to-node and frequency-to-doubly-linked-list, plus a minFreq counter. All operations O(1).
- "Can you use LinkedHashMap?" — Yes. Extend LinkedHashMap with accessOrder=true and override removeEldestEntry. Interviewers want the manual implementation to test data structure understanding.
- "How do you add TTL?" — Add an expiry timestamp to Node. In get, check expiry before returning. If expired, remove and return -1. Run a background sweeper thread for cleanup.
FAQ — LRU Cache Low Level Design
Why is HashMap + Doubly Linked List used for LRU cache?
HashMap gives O(1) key lookup. Doubly Linked List gives O(1) insertion at front and removal from any position using direct node references stored in the map. Together they achieve O(1) get and put. A singly linked list would need O(n) to find the previous node for removal.
What is the time complexity of LRU cache operations?
Both get and put are O(1) average. HashMap lookup is O(1) average. Linked list operations (addToFront, removeNode, evictLRU) are O(1) because we have direct node references — no traversal needed.
How is LRU cache used in real systems?
Database query caches, DNS caches, CPU instruction caches, CDN edge caches, and browser caches all use LRU or variants. Redis implements LRU and LFU eviction policies. Java's LinkedHashMap is a built-in LRU used in application-level caching.