LRUCache.java

package lrucache;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * Thread-safe LRU cache with optional TTL expiry.
 *
 * Design decisions worth discussing in an interview:
 *
 * 1. ReadWriteLock instead of synchronized:
 *    Multiple threads can call get() in parallel (read lock).
 *    Only put/evict needs an exclusive write lock.
 *    Under read-heavy workloads this gives significantly better throughput.
 *
 * 2. Sentinel head/tail nodes:
 *    Avoids null checks on every linked-list operation.
 *    addToFront() and removeNode() never touch null pointers.
 *
 * 3. Key stored in Node:
 *    When evicting the LRU node we need to remove it from the HashMap too.
 *    Storing the key in the node avoids a costly reverse lookup.
 *
 * 4. TTL checked lazily on get() + eagerly by background sweeper:
 *    Lazy check = zero overhead when TTL is not used.
 *    Background sweeper = prevents unbounded memory growth from dead entries
 *    that are never accessed again.
 */
public class LRUCache<K, V> {

    // -----------------------------------------------------------------------
    // Fields
    // -----------------------------------------------------------------------

    private final int capacity;
    private final long ttlMs;           // 0 = no TTL

    private final Map<K, Node<K, V>> map;
    private final Node<K, V> head;      // sentinel — most recently used end
    private final Node<K, V> tail;      // sentinel — least recently used end

    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final CacheStats stats = new CacheStats();

    private ScheduledExecutorService sweeper;

    // -----------------------------------------------------------------------
    // Constructor (use Builder for cleaner construction)
    // -----------------------------------------------------------------------

    LRUCache(int capacity, long ttlMs, long sweepIntervalMs) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.capacity = capacity;
        this.ttlMs = ttlMs;
        this.map = new HashMap<>(capacity);

        // Sentinel nodes — never hold real data
        head = new Node<>(null, null, 0);
        tail = new Node<>(null, null, 0);
        head.next = tail;
        tail.prev = head;

        if (ttlMs > 0 && sweepIntervalMs > 0) {
            startSweeper(sweepIntervalMs);
        }
    }

    // -----------------------------------------------------------------------
    // Public API
    // -----------------------------------------------------------------------

    /**
     * Returns the value for key, or null on miss / expiry.
     * Acquires a WRITE lock because a cache hit moves the node to the front.
     *
     * Interview note: you could use a read lock here and upgrade to write
     * only on hit, but Java's ReentrantReadWriteLock does not support
     * lock upgrading — you'd have to release the read lock first, creating
     * a TOCTOU window. Keeping a single write lock is simpler and correct.
     */
    public V get(K key) {
        lock.writeLock().lock();
        try {
            Node<K, V> node = map.get(key);
            if (node == null) {
                stats.recordMiss();
                return null;
            }
            if (node.isExpired()) {
                removeNode(node);
                map.remove(key);
                stats.recordMiss();
                stats.recordEviction();
                return null;
            }
            // Cache hit — promote to MRU position
            moveToFront(node);
            stats.recordHit();
            return node.value;
        } finally {
            lock.writeLock().unlock();
        }
    }

    /**
     * Inserts or updates a key. Evicts the LRU entry if at capacity.
     * Always acquires a write lock.
     */
    public void put(K key, V value) {
        lock.writeLock().lock();
        try {
            Node<K, V> existing = map.get(key);
            if (existing != null) {
                // Update in place and promote
                existing.value = value;
                existing.expiryMs = (ttlMs > 0) ? System.currentTimeMillis() + ttlMs : -1L;
                moveToFront(existing);
                return;
            }
            if (map.size() >= capacity) {
                evictLRU();
            }
            Node<K, V> node = new Node<>(key, value, ttlMs);
            map.put(key, node);
            addToFront(node);
        } finally {
            lock.writeLock().unlock();
        }
    }

    /** Explicitly removes a key. Returns true if the key existed. */
    public boolean remove(K key) {
        lock.writeLock().lock();
        try {
            Node<K, V> node = map.remove(key);
            if (node == null) return false;
            removeNode(node);
            return true;
        } finally {
            lock.writeLock().unlock();
        }
    }

    /** Current number of entries (including potentially expired ones). */
    public int size() {
        lock.readLock().lock();
        try { return map.size(); }
        finally { lock.readLock().unlock(); }
    }

    public CacheStats stats() { return stats; }

    /** Shuts down the background TTL sweeper if one was started. */
    public void shutdown() {
        if (sweeper != null) sweeper.shutdown();
    }

    // -----------------------------------------------------------------------
    // Linked-list helpers (must be called under write lock)
    // -----------------------------------------------------------------------

    /** Inserts node right after head (MRU position). */
    private void addToFront(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /** Unlinks node from wherever it currently sits. */
    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /** Removes then re-inserts at front — O(1) promotion. */
    private void moveToFront(Node<K, V> node) {
        removeNode(node);
        addToFront(node);
    }

    /** Evicts the node just before the tail (LRU position). */
    private void evictLRU() {
        Node<K, V> lru = tail.prev;
        if (lru == head) return;            // cache is empty
        removeNode(lru);
        map.remove(lru.key);
        stats.recordEviction();
    }

    // -----------------------------------------------------------------------
    // Background TTL sweeper
    // -----------------------------------------------------------------------

    /**
     * Schedules a periodic task that removes expired entries.
     * Without this, entries that are never accessed again would stay in
     * memory until a put() triggers capacity eviction — potentially forever.
     *
     * Uses a daemon thread so it doesn't block JVM shutdown.
     */
    private void startSweeper(long intervalMs) {
        sweeper = Executors.newSingleThreadScheduledExecutor(r -> {
            Thread t = new Thread(r, "lru-cache-sweeper");
            t.setDaemon(true);
            return t;
        });
        sweeper.scheduleAtFixedRate(this::sweepExpired, intervalMs, intervalMs, TimeUnit.MILLISECONDS);
    }

    private void sweepExpired() {
        lock.writeLock().lock();
        try {
            List<K> toRemove = new ArrayList<>();
            // Walk the linked list from LRU end — more likely to find expired entries
            Node<K, V> cur = tail.prev;
            while (cur != head) {
                if (cur.isExpired()) toRemove.add(cur.key);
                cur = cur.prev;
            }
            for (K key : toRemove) {
                Node<K, V> node = map.remove(key);
                if (node != null) {
                    removeNode(node);
                    stats.recordEviction();
                }
            }
        } finally {
            lock.writeLock().unlock();
        }
    }

    // -----------------------------------------------------------------------
    // Builder
    // -----------------------------------------------------------------------

    public static <K, V> Builder<K, V> builder() { return new Builder<>(); }

    public static class Builder<K, V> {
        private int capacity = 100;
        private long ttlMs = 0;
        private long sweepIntervalMs = 30_000;  // 30 s default

        public Builder<K, V> capacity(int capacity) {
            this.capacity = capacity;
            return this;
        }

        /** Sets TTL in milliseconds. Pass 0 to disable. */
        public Builder<K, V> ttlMs(long ttlMs) {
            this.ttlMs = ttlMs;
            return this;
        }

        /** Convenience method using java.time.Duration style. */
        public Builder<K, V> ttlSeconds(long seconds) {
            this.ttlMs = seconds * 1000L;
            return this;
        }

        public Builder<K, V> sweepIntervalMs(long ms) {
            this.sweepIntervalMs = ms;
            return this;
        }

        public LRUCache<K, V> build() {
            return new LRUCache<>(capacity, ttlMs, sweepIntervalMs);
        }
    }
}