Java 40: Interview Capstone — Thread-Safe Bounded LRU Cache
easy⏱ 5 mincoursejava
The design sketch
HashMap<K, Node> for O(1) key lookup. Doubly-linked list of Node(k, v, prev, next) for O(1) move-to-front and remove-tail. On get(k): find node, unlink, move to head. On put(k, v): if new and size >= capacity, remove tail from list + map; then add new node at head. Thread safety: one lock around the whole structure, or — better — ConcurrentHashMap + careful CAS (advanced).
LinkedHashMap shortcut
Java's LinkedHashMap(capacity, loadFactor, true /* accessOrder */) is already an LRU — just override removeEldestEntry(eldest) to return size() > capacity. Wrap with Collections.synchronizedMap for thread safety. For interviews, implement it from scratch first — the shortcut is post-interview insight.
new LinkedHashMap<K, V>(cap, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cap;
}
};
What interviewers probe
Typical follow-ups: (1) Why doubly-linked? (single-linked can't unlink in O(1)). (2) How do you make it thread-safe without serializing everything? (striped locks, or Caffeine's BoundedLocalCache). (3) What if the cache is distributed? (consistent hashing, TTL). (4) How do you handle TTL + LRU together? (expiration queue by timestamp). Know the trade-offs.
Implement the cache
BoundedLRU<K, V>(capacity) with: get(k), put(k, v), size(), stats() (hits, misses, evictions). Track hits/misses/evictions. Test: fill a cache of capacity 3 with 5 keys, then access the first key (promotes it), then add another — the 'coldest' key should be evicted, not the recently-accessed one.
In production: use Caffeine
Caffeine is the industry-standard Java cache library: window-TinyLFU eviction (empirically beats pure LRU), near-linear scaling, async loading, expiration policies. In an interview, implement pure LRU; in real code, Caffeine.newBuilder().maximumSize(10_000).build().
Quiz: Concurrent LRU
What's hard about a lock-free concurrent LRU? The linked-list mutations. Updating the order on every get means most reads become writes to the shared structure. Caffeine avoids this by buffering access events in a thread-local ring and draining them in batches — amortized lock-free reads.