Design an LRU Cache

public class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev;
    Node<K, V> next;

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

public class DoublyLinkedList<K, V> {
    private final Node<K, V> head; // dummy
    private final Node<K, V> tail; // dummy
    private int size;

    public DoublyLinkedList() {
        head = new Node<>(null, null);
        tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    /** Add node right after head (most recently used position) */
    public void addToHead(Node<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        size++;
    }

    /** Remove a specific node from anywhere in the list — O(1) */
    public void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
        size--;
    }

    /** Move existing node to head (mark as most recently used) */
    public void moveToHead(Node<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    /** Remove and return the tail node (least recently used) */
    public Node<K, V> removeTail() {
        if (isEmpty()) return null;
        Node<K, V> lru = tail.prev;
        removeNode(lru);
        return lru;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
}

public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> map;
    private final DoublyLinkedList<K, V> dll;

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("Capacity must be positive");
        this.capacity = capacity;
        this.map = new HashMap<>(capacity, 0.75f);
        this.dll = new DoublyLinkedList<>();
    }

    /** O(1) — Returns value or null if not found */
    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        // Mark as most recently used
        dll.moveToHead(node);
        return node.value;
    }

    /** O(1) — Inserts or updates, evicts LRU if at capacity */
    public void put(K key, V value) {
        Node<K, V> existing = map.get(key);

        if (existing != null) {
            // Update existing: change value, move to head
            existing.value = value;
            dll.moveToHead(existing);
        } else {
            // Evict if at capacity
            if (map.size() == capacity) {
                evict();
            }
            // Insert new node
            Node<K, V> newNode = new Node<>(key, value);
            dll.addToHead(newNode);
            map.put(key, newNode);
        }
    }

    private void evict() {
        Node<K, V> lru = dll.removeTail();
        if (lru != null) {
            map.remove(lru.key); // This is why Node stores key
        }
    }

    public int size() {
        return map.size();
    }
}

import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * Thread-safe wrapper using ReentrantReadWriteLock.
 * - Multiple readers can call get() concurrently (read lock)
 * - Writers acquire exclusive lock for put() and eviction
 *
 * Note: get() needs WRITE lock because it modifies DLL order.
 * For true read concurrency, use the segmented approach below.
 */
public class ThreadSafeLRUCache<K, V> {
    private final LRUCache<K, V> cache;
    private final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();

    public ThreadSafeLRUCache(int capacity) {
        this.cache = new LRUCache<>(capacity);
    }

    public V get(K key) {
        // get() mutates DLL order → needs write lock
        rwLock.writeLock().lock();
        try {
            return cache.get(key);
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    public void put(K key, V value) {
        rwLock.writeLock().lock();
        try {
            cache.put(key, value);
        } finally {
            rwLock.writeLock().unlock();
        }
    }

    /**
     * Peek without updating access order — true read-only.
     * Multiple threads can call this concurrently.
     */
    public V peek(K key) {
        rwLock.readLock().lock();
        try {
            Node<K, V> node = cache.map.get(key);
            return node != null ? node.value : null;
        } finally {
            rwLock.readLock().unlock();
        }
    }
}

/**
 * High-throughput alternative: Segmented LRU Cache (Caffeine-style)
 * Partition keyspace into N segments, each with its own lock.
 */
public class SegmentedLRUCache<K, V> {
    private final int segmentCount;
    private final LRUCache<K, V>[] segments;
    private final ReentrantReadWriteLock[] locks;

    @SuppressWarnings("unchecked")
    public SegmentedLRUCache(int totalCapacity, int segmentCount) {
        this.segmentCount = segmentCount;
        int perSegment = totalCapacity / segmentCount;
        segments = new LRUCache[segmentCount];
        locks = new ReentrantReadWriteLock[segmentCount];
        for (int i = 0; i < segmentCount; i++) {
            segments[i] = new LRUCache<>(perSegment);
            locks[i] = new ReentrantReadWriteLock();
        }
    }

    private int segmentFor(K key) {
        return (key.hashCode() & 0x7FFFFFFF) % segmentCount;
    }

    public V get(K key) {
        int seg = segmentFor(key);
        locks[seg].writeLock().lock();
        try {
            return segments[seg].get(key);
        } finally {
            locks[seg].writeLock().unlock();
        }
    }

    public void put(K key, V value) {
        int seg = segmentFor(key);
        locks[seg].writeLock().lock();
        try {
            segments[seg].put(key, value);
        } finally {
            locks[seg].writeLock().unlock();
        }
    }
}

/**
 * LFU (Least Frequently Used) Cache
 * - Evicts the entry with lowest access frequency
 * - On tie: evicts the least recently used among lowest-frequency entries
 *
 * Structure: HashMap + frequency-to-DLL map
 */
public class LFUCache<K, V> {
    private final int capacity;
    private int minFreq;
    private final Map<K, Node<K, V>> keyMap;
    private final Map<K, Integer> freqMap;               // key → frequency
    private final Map<Integer, DoublyLinkedList<K, V>> freqBuckets; // freq → DLL

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.freqBuckets = new HashMap<>();
    }

    public V get(K key) {
        if (!keyMap.containsKey(key)) return null;
        Node<K, V> node = keyMap.get(key);
        incrementFrequency(key, node);
        return node.value;
    }

    public void put(K key, V value) {
        if (capacity <= 0) return;

        if (keyMap.containsKey(key)) {
            Node<K, V> node = keyMap.get(key);
            node.value = value;
            incrementFrequency(key, node);
            return;
        }

        if (keyMap.size() == capacity) {
            // Evict from min-frequency bucket (tail = LRU within that freq)
            DoublyLinkedList<K, V> minList = freqBuckets.get(minFreq);
            Node<K, V> evicted = minList.removeTail();
            keyMap.remove(evicted.key);
            freqMap.remove(evicted.key);
        }

        // Insert new entry at frequency 1
        Node<K, V> newNode = new Node<>(key, value);
        keyMap.put(key, newNode);
        freqMap.put(key, 1);
        freqBuckets.computeIfAbsent(1, k -> new DoublyLinkedList<>()).addToHead(newNode);
        minFreq = 1;
    }

    private void incrementFrequency(K key, Node<K, V> node) {
        int oldFreq = freqMap.get(key);
        int newFreq = oldFreq + 1;
        freqMap.put(key, newFreq);

        // Remove from old frequency bucket
        freqBuckets.get(oldFreq).removeNode(node);
        if (freqBuckets.get(oldFreq).isEmpty()) {
            freqBuckets.remove(oldFreq);
            if (minFreq == oldFreq) minFreq++;
        }

        // Add to new frequency bucket
        freqBuckets.computeIfAbsent(newFreq, k -> new DoublyLinkedList<>()).addToHead(node);
    }
}