The LRU (Least Recently Used) Cache is one of the most frequently asked Java LLD interview questions. It evaluates:
- OOP Design
- Data Structures
- SOLID Principles
- Time Complexity
- Thread Safety
- Extensibility
A good interview solution should achieve O(1) time complexity for both get() and put() operations.
Problem Statement
Design an LRU Cache that supports:
get(key)put(key, value)- Fixed capacity
- Evict Least Recently Used item when full
- O(1) operations
- Thread-safe (Bonus)
Example:
Capacity = 3
put(1, A)
put(2, B)
put(3, C)
Cache:
3 → 2 → 1
get(1)
Cache:
1 → 3 → 2
put(4, D)
Evict 2
Cache:
4 → 1 → 3
Functional Requirements
- Get value by key
- Insert/Update key-value pair
- Fixed cache capacity
- Automatic eviction of least recently used entry
Non-Functional Requirements
- O(1) read/write
- Memory efficient
- Extensible
- Thread-safe
- Generic implementation
Why HashMap + Doubly Linked List?
HashMap
-------------------
1 -> Node
2 -> Node
3 -> Node
▲
│
Head <-> 3 <-> 2 <-> 1 <-> Tail
MRU LRU
Responsibilities
HashMap
- O(1) lookup
Doubly Linked List
- O(1) insertion
- O(1) deletion
- O(1) move to front
Time Complexity
| Operation | Complexity |
|---|---|
| get | O(1) |
| put | O(1) |
| remove | O(1) |
| moveToFront | O(1) |
Class Diagram
+----------------------+
| LRUCache<K,V> |
+----------------------+
| capacity |
| Map<K,Node<K,V>> |
| head |
| tail |
+----------------------+
| get() |
| put() |
| removeNode() |
| addToFront() |
+----------+-----------+
|
|
+------v------+
| Node<K,V> |
+-------------+
| key |
| value |
| prev |
| next |
+-------------+
Node Class
class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
LRU Cache Implementation
import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V> {
private final int capacity;
private final Map<K, Node<K, V>> cache;
private final Node<K, V> head;
private final Node<K, V> tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
}
public synchronized V get(K key) {
Node<K, V> node = cache.get(key);
if (node == null) {
return null;
}
moveToFront(node);
return node.value;
}
public synchronized void put(K key, V value) {
Node<K, V> node = cache.get(key);
if (node != null) {
node.value = value;
moveToFront(node);
return;
}
if (cache.size() == capacity) {
Node<K, V> lru = tail.prev;
removeNode(lru);
cache.remove(lru.key);
}
Node<K, V> newNode = new Node<>(key, value);
cache.put(key, newNode);
addToFront(newNode);
}
private void moveToFront(Node<K, V> node) {
removeNode(node);
addToFront(node);
}
private void addToFront(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
static class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
Driver
public class Main {
public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
System.out.println(cache.get(1));
cache.put(4, "D");
System.out.println(cache.get(2));
System.out.println(cache.get(3));
System.out.println(cache.get(4));
}
}
Execution
put(1,A)
1
put(2,B)
2 → 1
put(3,C)
3 → 2 → 1
get(1)
1 → 3 → 2
put(4,D)
Evict 2
4 → 1 → 3
Design Patterns Used
| Pattern | Purpose |
|---|---|
| Template (optional) | Base cache abstraction |
| Strategy (optional) | Eviction policy (LRU, LFU, FIFO) |
| Factory (optional) | Cache creation |
| Singleton (optional) | Shared cache instance |
| Decorator (optional) | Metrics, logging |
SOLID Principles
| Principle | Application |
|---|---|
| Single Responsibility |
Node stores data, LRUCache manages cache behavior. |
| Open/Closed | Eviction logic can be abstracted to support new policies. |
| Liskov Substitution | Alternative cache implementations can implement the same interface. |
| Interface Segregation | Define a small Cache<K,V> interface (get, put, remove, clear). |
| Dependency Inversion | Depend on a Cache abstraction rather than a concrete implementation. |
Production Enhancements
A production-grade cache often includes:
-
Cache<K,V>interface - Pluggable eviction policies (LRU, LFU, FIFO)
- Time-based expiration (TTL/TTI)
- Maximum memory limit
- Statistics (hits, misses, evictions)
- Asynchronous loading (
LoadingCache) - Background cleanup
- Persistence support
- Distributed cache support (Redis, Hazelcast)
- Read-write locking (
ReentrantReadWriteLock) for improved concurrency
Common Interview Follow-up Questions
- Why use a Doubly Linked List instead of a singly linked list?
- Removal and movement of arbitrary nodes require O(1) access to both previous and next nodes.
- Why use dummy head and tail nodes?
- They eliminate edge cases when adding or removing nodes at the ends of the list.
- Why can't a
HashMapalone implement an LRU cache?
- A
HashMapprovides fast lookup but does not maintain recency order.
- How would you make this implementation more concurrent?
- Replace synchronized methods with
ReentrantReadWriteLockor use segmented locking to reduce contention.
- How would you support different eviction strategies?
- Extract an
EvictionPolicyinterface and implementLRU,LFU, orFIFOstrategies using the Strategy pattern.
- How would you add expiration (TTL)?
- Store an expiration timestamp with each node and lazily or periodically remove expired entries.
- How does this compare to Java's
LinkedHashMap?
-
LinkedHashMapcan implement LRU using access-order mode and overridingremoveEldestEntry(), but implementing it manually demonstrates understanding of the underlying data structures.
This implementation is the standard LLD solution expected in Java interviews because it combines HashMap + Doubly Linked List to achieve O(1) get() and put() while remaining clean, extensible, and easy to explain.
Top comments (0)