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.
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.
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.
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).
Limit total bytes, not item count: one 2 MB photo should weigh as much as a thousand 2 KB icons.
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.
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 ask | Interviewer 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. |
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.
The map finds a node in O(1); the list keeps recency order so moving or evicting is O(1).
Every read moves a node to the head; eviction always takes the tail.
The JVM's garbage collector frees cycles, so unlink only has to null the pointers. No weak references needed.
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.
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}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}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}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.
A node per entry
Each node holds key, value and cost, plus pointers to its neighbours in recency order.
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 }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.
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 setReads refresh recency
operator get lets callers write cache[key]. A hit moves the node to the head, so popular thumbnails survive eviction.
23 operator fun get(key: K): V? {24 val node = nodes[key] ?: return null25 moveToFront(node)26 return node.value27 }Writes insert or update
Updating adjusts the running total by the cost difference; new nodes go to the head. Then evict.
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 }Evict from the tail
While over budget, drop the least recently used node. One oversized item can evict many small ones, including itself.
58 private fun evictIfNeeded() {59 while (totalCost > costLimit) {60 remove(tail?.key ?: return)61 }62 }O(1) list surgery
insertAtFront, unlink and moveToFront only touch neighbours, never walk the list.
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 }Complexity: O(1) per get, put and remove; O(n) memory
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?
Why not android.util.LruCache?
How would you add a disk tier?
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
| Approach | Swift / iOS |
|---|---|
| Built-in | NSCache with totalCostLimit; thread-safe and purges on memory warnings, but the eviction order is undocumented. |
| From scratch | The same map + doubly linked list in Swift, with a weak prev pointer to avoid retain cycles under ARC. |
| Memory warnings | UIApplication.didReceiveMemoryWarningNotification → removeAll(). |