LRU cache with a memory budget

O(1) get and put, evicting the least recently used item when bytes exceed a limit.

Part 1 of 5

Basics

The concepts this component is built on. With these in mind, every line of the solution has a reason.

1.1Key concepts

One idea per card, in the order the solution uses them.

01Cache

A fast store for results you will need again. Memory is the fastest place but it is small, so something must decide what to throw away.

02LRU eviction

Least recently used: when space runs out, drop the item nobody has touched for longest. A thumbnail viewed a moment ago is likely to be viewed again.

03Hash map + doubly linked list

The map finds an entry by key in O(1). The list keeps entries in recency order, and because each node knows both neighbours it can be moved or removed in O(1).

04A budget in bytes

Limit total bytes, not item count: one 2 MB photo should weigh as much as a thousand 2 KB icons.

Part 2 of 5

Question

What exactly you are asked to build, what must be true when you are done, and what to ask before you start.

2.1Prompt

The question as the interviewer asks it, and the requirements to check your solution against.

Interviewer

Our feed shows thousands of thumbnails. Build the in-memory cache: get and put in O(1), and when the total size passes a budget, evict whatever was used least recently.

Requirements

  • get(key) and put(key, value, cost) in O(1)
  • Total cost never exceeds the limit after a put
  • Reading an item makes it most recently used
  • Updating a key adjusts the total cost

2.2Clarify first

Questions worth asking, and the answers this interviewer gives.

You askInterviewer answers
Is the limit item count or bytes?Bytes. Images vary from 2 KB to 2 MB, so a count limit is meaningless.
Thread safety?Assume one owner. Callers confine it to one coroutine or wrap it in a Mutex.
What about memory pressure?Expose clear() so the app can purge it from onTrimMemory.
Part 3 of 5

Detailed answer

The design decisions, the complete Kotlin solution, and a walk through it one block at a time.

3.1Design decisions

Settle these before writing code; each one shows up in the solution.

Hash map + doubly linked list

The map finds a node in O(1); the list keeps recency order so moving or evicting is O(1).

Head is newest, tail is oldest

Every read moves a node to the head; eviction always takes the tail.

Plain prev and next pointers

The JVM's garbage collector frees cycles, so unlink only has to null the pointers. No weak references needed.

Cost, not count

Each entry carries its own cost; eviction loops until the total fits.

3.2Solution

Complete, compiling Kotlin with coroutines, built with warnings as errors and covered by tests/mobile/MobileTests.kt. The Java and TypeScript tabs do the same job with each language's own tools: Java compiled and run in our tests, TypeScript run in our tests.

KotlinJavaTypeScript
LruCache.ktKotlinCopy
1/**2 * A least-recently-used cache with O(1) reads and writes and a total-cost limit,3 * for example decoded image bytes. Not thread-safe on its own: confine it to one4 * coroutine or guard it with a Mutex (see ImageLoader).5 */6class LruCache<K : Any, V : Any>(val costLimit: Int) {7  private class Node<K, V>(val key: K, var value: V, var cost: Int) {8    var prev: Node<K, V>? = null9    var next: Node<K, V>? = null10  }11 12  private val nodes = HashMap<K, Node<K, V>>()13  private var head: Node<K, V>? = null   // most recently used14  private var tail: Node<K, V>? = null   // least recently used15  var totalCost = 016    private set17  val size: Int get() = nodes.size18 19  init {20    require(costLimit > 0) { "costLimit must be positive" }21  }22 23  operator fun get(key: K): V? {24    val node = nodes[key] ?: return null25    moveToFront(node)26    return node.value27  }28 29  fun put(key: K, value: V, cost: Int = 1) {30    val node = nodes[key]31    if (node != null) {32      totalCost += cost - node.cost33      node.value = value34      node.cost = cost35      moveToFront(node)36    } else {37      val fresh = Node(key, value, cost)38      nodes[key] = fresh39      insertAtFront(fresh)40      totalCost += cost41    }42    evictIfNeeded()43  }44 45  fun remove(key: K) {46    val node = nodes.remove(key) ?: return47    unlink(node)48    totalCost -= node.cost49  }50 51  fun clear() {52    nodes.clear()53    head = null54    tail = null55    totalCost = 056  }57 58  private fun evictIfNeeded() {59    while (totalCost > costLimit) {60      remove(tail?.key ?: return)61    }62  }63 64  private fun insertAtFront(node: Node<K, V>) {65    node.prev = null66    node.next = head67    head?.prev = node68    head = node69    if (tail == null) tail = node70  }71 72  private fun unlink(node: Node<K, V>) {73    node.prev?.next = node.next74    node.next?.prev = node.prev75    if (head === node) head = node.next76    if (tail === node) tail = node.prev77    node.prev = null78    node.next = null79  }80 81  private fun moveToFront(node: Node<K, V>) {82    if (head === node) return83    unlink(node)84    insertAtFront(node)85  }86}
86 linesUTF-8Kotlin
LruCache.javaJavaCopy
1import java.util.HashMap;2import java.util.Map;3 4/**5 * A least-recently-used cache with O(1) reads and writes and a total-cost limit,6 * for example decoded image bytes. Not thread-safe on its own: guard it with a lock (see ImageLoader).7 */8public final class LruCache<K, V> {9  private static final class Node<K, V> {10    final K key;11    V value;12    int cost;13    Node<K, V> prev;14    Node<K, V> next;15 16    Node(K key, V value, int cost) {17      this.key = key;18      this.value = value;19      this.cost = cost;20    }21  }22 23  private final Map<K, Node<K, V>> nodes = new HashMap<>();24  private final int costLimit;25  private Node<K, V> head;   // most recently used26  private Node<K, V> tail;   // least recently used27  private int totalCost;28 29  public LruCache(int costLimit) {30    if (costLimit <= 0) throw new IllegalArgumentException("costLimit must be positive");31    this.costLimit = costLimit;32  }33 34  public int size() { return nodes.size(); }35 36  public int totalCost() { return totalCost; }37 38  public V get(K key) {39    Node<K, V> node = nodes.get(key);40    if (node == null) return null;41    moveToFront(node);42    return node.value;43  }44 45  public void put(K key, V value) { put(key, value, 1); }46 47  public void put(K key, V value, int cost) {48    Node<K, V> node = nodes.get(key);49    if (node != null) {50      totalCost += cost - node.cost;51      node.value = value;52      node.cost = cost;53      moveToFront(node);54    } else {55      Node<K, V> fresh = new Node<>(key, value, cost);56      nodes.put(key, fresh);57      insertAtFront(fresh);58      totalCost += cost;59    }60    evictIfNeeded();61  }62 63  public void remove(K key) {64    Node<K, V> node = nodes.remove(key);65    if (node == null) return;66    unlink(node);67    totalCost -= node.cost;68  }69 70  public void clear() {71    nodes.clear();72    head = null;73    tail = null;74    totalCost = 0;75  }76 77  private void evictIfNeeded() {78    while (totalCost > costLimit && tail != null) remove(tail.key);79  }80 81  private void insertAtFront(Node<K, V> node) {82    node.prev = null;83    node.next = head;84    if (head != null) head.prev = node;85    head = node;86    if (tail == null) tail = node;87  }88 89  private void unlink(Node<K, V> node) {90    if (node.prev != null) node.prev.next = node.next;91    if (node.next != null) node.next.prev = node.prev;92    if (head == node) head = node.next;93    if (tail == node) tail = node.prev;94    node.prev = null;95    node.next = null;96  }97 98  private void moveToFront(Node<K, V> node) {99    if (head == node) return;100    unlink(node);101    insertAtFront(node);102  }103}
103 linesUTF-8Java
LruCache.tsTypeScriptCopy
1/**2 * A least-recently-used cache with O(1) reads and writes and a total-cost limit,3 * for example decoded image bytes. JavaScript runs one task at a time, so no lock is needed.4 */5class Node<K, V> {6  prev: Node<K, V> | null = null;7  next: Node<K, V> | null = null;8  key: K;9  value: V;10  cost: number;11  constructor(key: K, value: V, cost: number) {12    this.key = key;13    this.value = value;14    this.cost = cost;15  }16}17 18export class LruCache<K, V> {19  readonly costLimit: number;20  totalCost = 0;21  private nodes = new Map<K, Node<K, V>>();22  private head: Node<K, V> | null = null;   // most recently used23  private tail: Node<K, V> | null = null;   // least recently used24 25  constructor(costLimit: number) {26    if (!(costLimit > 0)) throw new Error("costLimit must be positive");27    this.costLimit = costLimit;28  }29 30  get size(): number {31    return this.nodes.size;32  }33 34  get(key: K): V | undefined {35    const node = this.nodes.get(key);36    if (!node) return undefined;37    this.moveToFront(node);38    return node.value;39  }40 41  put(key: K, value: V, cost = 1): void {42    const node = this.nodes.get(key);43    if (node) {44      this.totalCost += cost - node.cost;45      node.value = value;46      node.cost = cost;47      this.moveToFront(node);48    } else {49      const fresh = new Node(key, value, cost);50      this.nodes.set(key, fresh);51      this.insertAtFront(fresh);52      this.totalCost += cost;53    }54    this.evictIfNeeded();55  }56 57  remove(key: K): void {58    const node = this.nodes.get(key);59    if (!node) return;60    this.nodes.delete(key);61    this.unlink(node);62    this.totalCost -= node.cost;63  }64 65  clear(): void {66    this.nodes.clear();67    this.head = null;68    this.tail = null;69    this.totalCost = 0;70  }71 72  private evictIfNeeded(): void {73    while (this.totalCost > this.costLimit && this.tail) this.remove(this.tail.key);74  }75 76  private insertAtFront(node: Node<K, V>): void {77    node.prev = null;78    node.next = this.head;79    if (this.head) this.head.prev = node;80    this.head = node;81    if (!this.tail) this.tail = node;82  }83 84  private unlink(node: Node<K, V>): void {85    if (node.prev) node.prev.next = node.next;86    if (node.next) node.next.prev = node.prev;87    if (this.head === node) this.head = node.next;88    if (this.tail === node) this.tail = node.prev;89    node.prev = null;90    node.next = null;91  }92 93  private moveToFront(node: Node<K, V>): void {94    if (this.head === node) return;95    this.unlink(node);96    this.insertAtFront(node);97  }98}
98 linesUTF-8TypeScript

3.3Line-by-line walkthrough

The same code in the order you would explain it in the room. The line numbers follow the Kotlin file; the Java and TypeScript tabs above have the same steps in the same order.

1

A node per entry

Each node holds key, value and cost, plus pointers to its neighbours in recency order.

LruCache.ktKotlinCopy
7  private class Node<K, V>(val key: K, var value: V, var cost: Int) {8    var prev: Node<K, V>? = null9    var next: Node<K, V>? = null10  }
lines 7–10UTF-8Kotlin
2

Map plus list

The HashMap gives O(1) lookup; head and tail mark the most and least recently used ends. totalCost is read-only outside.

LruCache.ktKotlinCopy
12  private val nodes = HashMap<K, Node<K, V>>()13  private var head: Node<K, V>? = null   // most recently used14  private var tail: Node<K, V>? = null   // least recently used15  var totalCost = 016    private set
lines 12–16UTF-8Kotlin
3

Reads refresh recency

operator get lets callers write cache[key]. A hit moves the node to the head, so popular thumbnails survive eviction.

LruCache.ktKotlinCopy
23  operator fun get(key: K): V? {24    val node = nodes[key] ?: return null25    moveToFront(node)26    return node.value27  }
lines 23–27UTF-8Kotlin
4

Writes insert or update

Updating adjusts the running total by the cost difference; new nodes go to the head. Then evict.

LruCache.ktKotlinCopy
29  fun put(key: K, value: V, cost: Int = 1) {30    val node = nodes[key]31    if (node != null) {32      totalCost += cost - node.cost33      node.value = value34      node.cost = cost35      moveToFront(node)36    } else {37      val fresh = Node(key, value, cost)38      nodes[key] = fresh39      insertAtFront(fresh)40      totalCost += cost41    }42    evictIfNeeded()43  }
lines 29–43UTF-8Kotlin
5

Evict from the tail

While over budget, drop the least recently used node. One oversized item can evict many small ones, including itself.

LruCache.ktKotlinCopy
58  private fun evictIfNeeded() {59    while (totalCost > costLimit) {60      remove(tail?.key ?: return)61    }62  }
lines 58–62UTF-8Kotlin
6

O(1) list surgery

insertAtFront, unlink and moveToFront only touch neighbours, never walk the list.

LruCache.ktKotlinCopy
64  private fun insertAtFront(node: Node<K, V>) {65    node.prev = null66    node.next = head67    head?.prev = node68    head = node69    if (tail == null) tail = node70  }71 72  private fun unlink(node: Node<K, V>) {73    node.prev?.next = node.next74    node.next?.prev = node.prev75    if (head === node) head = node.next76    if (tail === node) tail = node.prev77    node.prev = null78    node.next = null79  }80 81  private fun moveToFront(node: Node<K, V>) {82    if (head === node) return83    unlink(node)84    insertAtFront(node)85  }
lines 64–85UTF-8Kotlin

Complexity: O(1) per get, put and remove; O(n) memory

Part 4 of 5

Q&A

The questions interviewers ask after the code works. Answer out loud, then open.

4.1Follow-up questions

How do you make it thread-safe?
Own it behind a Mutex (as ImageLoader does) or confine it to one dispatcher. Never share it across threads unprotected.
Why not android.util.LruCache?
Use it in production: override sizeOf() to return bitmap.byteCount. Writing it yourself shows you know the map + list structure underneath, which is what the round tests.
How would you add a disk tier?
Put a disk cache behind the memory cache: read memory, then disk, then network, and write back to both. See the image loader problem.
Part 5 of 5

Extra depth

The cases that break naive solutions, how the same design looks on iOS, and what to practise next.

5.1Edge cases

Say these before the interviewer does.

Show detailsHide details
  • Putting an item larger than the whole budget evicts everything, including itself
  • Updating an existing key with a bigger cost
  • Reading a missing key must not change order
  • clear() during onTrimMemory

5.2On iOS

The same design in Swift and Apple's frameworks.

Show detailsHide details
ApproachSwift / iOS
Built-inNSCache with totalCostLimit; thread-safe and purges on memory warnings, but the eviction order is undocumented.
From scratchThe same map + doubly linked list in Swift, with a weak prev pointer to avoid retain cycles under ARC.
Memory warningsUIApplication.didReceiveMemoryWarningNotification → removeAll().