Design an LRU cache. | androidinterview.com

A cache keeps values so callers can reuse them without fetching or calculating them again. An LRU cache has limited capacity and removes the least recently used entry when it needs room. Reading or updating an entry counts as using it.

The problem

Implement get(key) to return a stored value or a miss, and put(key, value) to insert or update one. Use a positive capacity measured in entries for the basic version. Both operations should take constant time on average as the cache grows.

With capacity two, the expected behaviour is as follows. The order shown runs from most recently used to least recently used.

Operation	Result	Keys in recency order
`put(A, 10)`	Store A	A
`put(B, 20)`	Store B	B, A
`get(A)`	Return 10 and mark A used	A, B
`put(C, 30)`	Remove B to make room	C, A
`get(B)`	Miss	C, A

Updating A replaces its value without using another slot. This exercise starts with an in memory data structure. Disk persistence, expiry and limits measured in bytes are separate extensions.

Starting the design

A hash map for O(1) lookup plus a doubly linked list for O(1) reordering, so get and put are both constant time on average. The rest of the answer is why neither half works alone, and how to keep the pointer work from turning into a maze of edge cases.

Why that combination

A hash map alone gives O(1) lookup but no sense of order, so to evict you would scan every entry for the least recently used one. A linked list alone gives O(1) reordering, moving an accessed node to the front, but O(n) lookup, because you would walk it to find a key. Combined, the map stores key to node and the list keeps the nodes in recency order. You get both for one extra pointer pair per entry.

Neither half is interesting on its own, which is the point of drawing them together. The map reaches a node without walking anything and the list moves that node to the front without searching. The extra pointer per entry is the entire price.

The structure

Two files. LruCache is the map and the doubly linked list written out by hand, which is the version an interviewer wants on the whiteboard. SizedLruCache is the same cache budgeted in bytes instead of entries, built on LinkedHashMap in access order, which is the version you would ship.

Java

com.androidinterview.lrucache.LruCache.java

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.HashMap;
import java.util.Map;

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<>();

    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);

    public LruCache(int capacity) {
        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);
    }

    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();
    }

    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;
    }
}

com.androidinterview.lrucache.SizedLruCache.java

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;

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

public final class SizedLruCache<K, V> {

    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();
    }

    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;
    }
}

Kotlin

com.androidinterview.lrucache.LruCache.kt

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

class LruCache<K : Any, V : Any>(private val capacity: Int) {

    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 {
        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

    operator fun set(key: K, value: V) {
        index[key]?.let { existing ->
            existing.value = value
            moveToFront(existing)
            return
        }
        while (index.size >= capacity) {
            val lru = tail.prev
            unlink(lru)
            index.remove(lru.key!!)
        }
        val node = Node<K, V>(key, value)
        index[key] = node
        addToFront(node)
    }

    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
    }
}

com.androidinterview.lrucache.SizedLruCache.kt

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()
        }
    }
}

package com.androidinterview.lrucache

class SizedLruCache<K : Any, V : Any>(
    private val maxBytes: Long,
    private val sizeOf: (V) -> Int,
) {
    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

    @Synchronized
    fun trimTo(budget: Long) {
        val oldestFirst = entries.entries.iterator()
        while (sizeInBytes > budget && oldestFirst.hasNext()) {
            sizeInBytes -= oldestFirst.next().value.bytes
            oldestFirst.remove()
        }
    }
}

Two sentinel nodes, a dummy head and tail, remove every null check from the insert and remove logic. Every real node always has a real prev and next to link against, and that detail is what keeps the implementation from becoming a maze of edge cases. The other edge worth closing on a whiteboard is a capacity of zero. The constructor rejects it, because evicting from an empty list would unlink a sentinel.

Where this shows up for real on Android

Glide and Coil both keep an in memory bitmap cache of exactly this shape, keyed by URL plus size and budgeted by bytes, each with its own implementation. androidx.collection.LruCache is the platform's version of the same idea. All three weigh entries with a sizeOf rather than counting them, because a handful of large bitmaps can blow a memory budget that a count based limit would never notice.

Follow ups worth having ready

LRU vs LFU. LRU evicts what was touched longest ago, LFU evicts what was touched least often. LFU wins for a hot key read a thousand times that then goes quiet for a moment, since LRU would evict it as soon as newer keys arrive. It costs a frequency count per entry and an aging rule so old counts decay.
LinkedHashMap.removeEldestEntry. The usual shortcut is a LinkedHashMap in access order with removeEldestEntry overridden to return true past the limit. SizedLruCache drains with an iterator instead, because its budget is bytes and one put may need to evict several entries.
Explicit invalidation. remove(key) is the same unlink eviction uses, aimed at a chosen node, plus a map removal.

How I'd build this on Android

Each arrow shows a call from one component to another.

I'd use an LRU cache inside a repository or image loader. It does not need a ViewModel of its own. On Android, the first decisions are how much memory it can use and which callers share it. The platform LruCache can hold bitmaps, while the code browser shows how the underlying linked map works.

class BitmapMemoryCache(maxBytes: Int) : LruCache<String, Bitmap>(maxBytes) {
    override fun sizeOf(key: String, value: Bitmap): Int = value.allocationByteCount
}

// Construct once in the application DI graph using a deliberate memory budget.
val thumbnails = BitmapMemoryCache(maxBytes = 8 * 1024 * 1024)

The budget above is an example, not a safe value for every device. Entries count by the memory they keep alive. If a value changes size after insertion, the count becomes wrong. I'd use immutable values or replace them through the cache API. Removing a bitmap from the cache only removes the cache's reference. It must not recycle a bitmap still shown by a view.

Each LruCache operation is thread safe, but reading, fetching and inserting are three separate operations. Two callers can still fetch the same missing image. I'd share that fetch outside the cache and avoid holding a lock during network or decode work. Memory and app visibility callbacks can trigger trimming, but the cache needs a size limit even if no callback arrives. It disappears on process death, so it cannot be the only copy of a draft or queued write.

Compose rows cancel their image subscriptions when they leave, while the ViewModel exposes URLs. The cache and loader are injected and shared, never created inside LazyColumn.items.

I'd check these cases.

Eviction order.
Replacing a small value with a larger one.
An item bigger than the budget.
Simultaneous requests for one key.

LRU decides what to remove based on recent use. Expiry and keeping selected entries need extra rules. See Android LruCache.

Tradeoffs I'd call out

Count based capacity vs size based capacity. Limiting by entry count is simpler, but it is the wrong metric whenever entries vary a lot in size. A cache of 100 tiny strings and a cache of 100 large bitmaps behave completely differently under the same numeric limit. Size based capacity tracks cumulative bytes and evicts until under budget, which is what the shipped caches do, at the cost of needing a sizeOf from the caller. The size is recorded at insert and never recomputed, so a sizeOf that is not stable cannot drift the counter.
Thread safety cost. A single lock around get and put is simple and correct, but every read blocks every write and vice versa. Under real contention it is still usually the right first choice. Finer grained locking is a real complexity increase that is only worth it once profiling shows this lock is the bottleneck.
Strict LRU vs an approximation. True LRU requires a pointer update on every read, which makes every read a write. The usual approximation is a second chance bit per entry instead of a move to front on every read. The eviction sweep clears the bit on its first pass and evicts on its second. It is cheaper per read, and it sometimes evicts an entry that was not quite the least recently used.

What breaks at scale

At high read throughput, the pointer updates on every get become the bottleneck before the hash map lookup does, because every access mutates shared state to reorder the list. That is the concrete reason a naive synchronized version of this cache becomes a contention point under heavy concurrent access. It is also the follow up an interviewer is likely to push on once the base implementation is working.