Design an LRU cache.

package com.androidinterview.lrucache;

import java.util.HashMap;
import java.util.Map;

// The whole answer is these two structures held together. The map gives O(1)
// lookup and the list gives O(1) reordering, and neither one alone gives both.
// A map on its own would have to scan every entry to find the oldest, a list
// on its own would have to walk itself to find a key.
public final class LruCache<K, V> {

    private static final class Node<K, V> {
        final K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

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

    private final int capacity;
    private final Map<K, Node<K, V>> index = new HashMap<>();

    // Two sentinels, so every real node always has a real prev and a real
    // next. This is the detail that keeps insert and remove down to four
    // pointer writes with no null checks anywhere.
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);

    public LruCache(int capacity) {
        // A capacity of zero would evict from an empty list, and the node in
        // front of the tail is then the head sentinel itself.
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> node = index.get(key);
        if (node == null) {
            return null;
        }
        moveToFront(node);
        return node.value;
    }

    public void put(K key, V value) {
        Node<K, V> existing = index.get(key);
        if (existing != null) {
            existing.value = value;
            moveToFront(existing);
            return;
        }
        while (index.size() >= capacity) {
            evictLeastRecentlyUsed();
        }
        Node<K, V> node = new Node<>(key, value);
        index.put(key, node);
        addToFront(node);
    }

    // Explicit invalidation, the usual follow-up. With the sentinels it is the
    // same unlink eviction uses, aimed at a chosen node instead of the last.
    public V remove(K key) {
        Node<K, V> node = index.remove(key);
        if (node == null) {
            return null;
        }
        unlink(node);
        return node.value;
    }

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

    // The node in front of the tail sentinel is the least recently used one by
    // construction, so eviction is a pointer unlink and a map removal, never a
    // search.
    private void evictLeastRecentlyUsed() {
        Node<K, V> lru = tail.prev;
        unlink(lru);
        index.remove(lru.key);
    }

    private void moveToFront(Node<K, V> node) {
        unlink(node);
        addToFront(node);
    }

    private void unlink(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToFront(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

package com.androidinterview.lrucache;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.ToIntFunction;

// The same cache budgeted in bytes rather than in entries, which is what
// androidx.collection.LruCache actually does and why it asks the caller for a
// sizeOf. A hundred short strings and a hundred large bitmaps are the same
// count and nowhere near the same memory.
//
// LinkedHashMap in access order is the map and the list already welded
// together, so this version never spells out the node wiring that LruCache
// above writes by hand. Overriding removeEldestEntry is the hook most people
// reach for. This one drains with an iterator instead, because the budget is
// bytes and a single put may have to evict several entries.
public final class SizedLruCache<K, V> {

    // The size is recorded at insert and never recomputed, so a sizeOf that is
    // not stable, a recycled bitmap reporting zero for instance, cannot drift
    // the counter until the cache either never evicts or evicts everything.
    private record Sized<V>(V value, int bytes) {
    }

    private final long maxBytes;
    private final ToIntFunction<V> sizeOf;
    private final LinkedHashMap<K, Sized<V>> entries = new LinkedHashMap<>(16, 0.75f, true);
    private long bytes;

    public SizedLruCache(long maxBytes, ToIntFunction<V> sizeOf) {
        this.maxBytes = maxBytes;
        this.sizeOf = sizeOf;
    }

    public synchronized V get(K key) {
        Sized<V> entry = entries.get(key);
        return entry == null ? null : entry.value();
    }

    public synchronized void put(K key, V value) {
        int size = sizeOf.applyAsInt(value);
        Sized<V> previous = entries.put(key, new Sized<>(value, size));
        if (previous != null) {
            bytes -= previous.bytes();
        }
        bytes += size;
        trimTo(maxBytes);
    }

    public synchronized V remove(K key) {
        Sized<V> removed = entries.remove(key);
        if (removed == null) {
            return null;
        }
        bytes -= removed.bytes();
        return removed.value();
    }

    // onTrimMemory hands this a smaller budget than the configured one, which
    // is the only reason the budget is a parameter and not the field. A cache
    // that evicts only on its own writes never learns that the rest of the app
    // is starving.
    public synchronized void trimTo(long budget) {
        Iterator<Map.Entry<K, Sized<V>>> oldestFirst = entries.entrySet().iterator();
        while (bytes > budget && oldestFirst.hasNext()) {
            bytes -= oldestFirst.next().getValue().bytes();
            oldestFirst.remove();
        }
    }

    public synchronized long sizeInBytes() {
        return bytes;
    }
}

package com.androidinterview.lrucache

// The whole answer is these two structures held together. The map gives O(1)
// lookup and the list gives O(1) reordering, and neither one alone gives both.
class LruCache<K : Any, V : Any>(private val capacity: Int) {

    // Sentinels carry no key and no value, which is the only reason either is
    // nullable. A real node always holds both, and every real node always has
    // a real prev and next, so the pointer work below needs no null checks.
    private class Node<K, V>(val key: K?, var value: V?) {
        lateinit var prev: Node<K, V>
        lateinit var next: Node<K, V>
    }

    private val index = HashMap<K, Node<K, V>>()
    private val head = Node<K, V>(null, null)
    private val tail = Node<K, V>(null, null)

    init {
        // A capacity of zero would evict from an empty list, and the node in
        // front of the tail is then the head sentinel itself.
        require(capacity > 0) { "capacity must be positive" }
        head.next = tail
        tail.prev = head
    }

    val size: Int get() = index.size

    operator fun get(key: K): V? = index[key]?.also(::moveToFront)?.value

    // The operator form of put, so a caller writes cache[key] = value.
    operator fun set(key: K, value: V) {
        index[key]?.let { existing ->
            existing.value = value
            moveToFront(existing)
            return
        }
        while (index.size >= capacity) {
            // The node in front of the tail sentinel is the least recently
            // used one by construction, so eviction is never a search.
            val lru = tail.prev
            unlink(lru)
            index.remove(lru.key!!)
        }
        val node = Node<K, V>(key, value)
        index[key] = node
        addToFront(node)
    }

    // Explicit invalidation, the usual follow-up. With the sentinels it is the
    // same unlink eviction uses, aimed at a chosen node instead of the last.
    fun remove(key: K): V? = index.remove(key)?.also(::unlink)?.value

    private fun moveToFront(node: Node<K, V>) {
        unlink(node)
        addToFront(node)
    }

    private fun unlink(node: Node<K, V>) {
        node.prev.next = node.next
        node.next.prev = node.prev
    }

    private fun addToFront(node: Node<K, V>) {
        node.next = head.next
        node.prev = head
        head.next.prev = node
        head.next = node
    }
}

package com.androidinterview.lrucache

// The same cache budgeted in bytes rather than in entries, which is what
// androidx.collection.LruCache does and why it asks the caller for a sizeOf. A
// hundred short strings and a hundred large bitmaps are the same count and
// nowhere near the same memory.
//
// LinkedHashMap in access order is the map and the list already welded
// together, so nothing here spells out the node wiring that LruCache writes by
// hand. Overriding removeEldestEntry is the hook most people reach for. This
// one drains with an iterator instead, because the budget is bytes and a
// single put may have to evict several entries.
class SizedLruCache<K : Any, V : Any>(
    private val maxBytes: Long,
    private val sizeOf: (V) -> Int,
) {
    // The size is recorded at insert and never recomputed, so a sizeOf that is
    // not stable, a recycled bitmap reporting zero for instance, cannot drift
    // the counter until the cache either never evicts or evicts everything.
    private class Sized<V>(val value: V, val bytes: Int)

    private val entries = LinkedHashMap<K, Sized<V>>(16, 0.75f, true)

    var sizeInBytes = 0L
        private set

    @Synchronized
    operator fun get(key: K): V? = entries[key]?.value

    @Synchronized
    operator fun set(key: K, value: V) {
        val size = sizeOf(value)
        entries.put(key, Sized(value, size))?.let { sizeInBytes -= it.bytes }
        sizeInBytes += size
        trimTo(maxBytes)
    }

    @Synchronized
    fun remove(key: K): V? = entries.remove(key)?.also { sizeInBytes -= it.bytes }?.value

    // onTrimMemory hands this a smaller budget than the configured one, which
    // is the only reason the budget is a parameter and not the field.
    @Synchronized
    fun trimTo(budget: Long) {
        val oldestFirst = entries.entries.iterator()
        while (sizeInBytes > budget && oldestFirst.hasNext()) {
            sizeInBytes -= oldestFirst.next().value.bytes
            oldestFirst.remove()
        }
    }
}