How to Design an LRU Cache System | LLD Interview Guide

The LRU Cache is one of the most commonly asked LLD/data-structure problems at FAANG companies. It combines a HashMap and Doubly Linked List for O(1) operations, and tests your understanding of cache eviction, TTL, and thread safety. Here's the complete design.

Core Requirements

• get(key): O(1) — return value or null
• put(key, value): O(1) — insert; evict LRU entry if at capacity
• TTL per entry — auto-evict expired entries
• Thread-safe operations
• Cache statistics: hits, misses, evictions

Core Data Structures

class CacheNode<K, V> {
  key: K; value: V;
  expiresAt: number | null;  // epoch ms; null = no expiry
  prev: CacheNode<K,V> | null = null;
  next: CacheNode<K,V> | null = null;
}

class LRUCache<K, V> {
  private capacity: number;
  private map = new Map<K, CacheNode<K,V>>();
  private head: CacheNode<K,V>; // Most recently used
  private tail: CacheNode<K,V>; // Least recently used
  private hits = 0; misses = 0; evictions = 0;
}

Get and Put — O(1) Operations

get(key: K): V | null {
  const node = this.map.get(key);
  if (!node) { this.misses++; return null; }
  if (this.isExpired(node)) { this.evict(node); this.misses++; return null; }
  this.moveToFront(node); // Mark as recently used
  this.hits++;
  return node.value;
}

put(key: K, value: V, ttlSeconds?: number): void {
  if (this.map.has(key)) {
    const node = this.map.get(key)!;
    node.value = value;
    node.expiresAt = ttlSeconds ? Date.now() + ttlSeconds * 1000 : null;
    this.moveToFront(node);
    return;
  }
  if (this.map.size >= this.capacity) this.evictLRU();
  const node = new CacheNode(key, value, ttlSeconds);
  this.map.set(key, node);
  this.addToFront(node);
}

private evictLRU(): void {
  const lru = this.tail.prev!;
  this.removeNode(lru);
  this.map.delete(lru.key);
  this.evictions++;
}

Strategy Pattern for Eviction Policy

interface EvictionPolicy<K,V> { evict(cache: Map<K, CacheNode<K,V>>): K; }
class LRUPolicy<K,V>  implements EvictionPolicy<K,V> { ... }
class LFUPolicy<K,V>  implements EvictionPolicy<K,V> { ... }
class FIFOPolicy<K,V> implements EvictionPolicy<K,V> { ... }

Thread Safety

In Java: use ReentrantReadWriteLock — reads can be concurrent, writes are exclusive. In JavaScript (single-threaded): no locking needed, but in distributed systems use Redis with Lua scripts for atomic operations.

Common Questions

• "How is TTL handled?" → Check expiry on every get(); background thread sweeps expired entries
• "How to add LFU?" → Strategy pattern — swap EvictionPolicy without touching cache logic
• "How to make it distributed?" → Use Redis; LRU is Redis's built-in eviction policy