Mobile machine coding reels
The prompt
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.
Ask first
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.
The design
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.
Edge cases
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.
Follow-up
“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.
LRU cache with a memory budget
O(1) get and put, evicting the least recently used item when bytes exceed a limit.
5 */6class LruCache<K : Any, V : Any>(val costLimit: Int) {7private class Node<K, V>(val key: K, var value: V, var cost: Int) {8var prev: Node<K, V>? = null9var next: Node<K, V>? = null10}11 12private val nodes = HashMap<K, Node<K, V>>()
The prompt
Design and implement the image loader behind a scrolling feed. Many rows ask for the same URL at once; rows get recycled while images load; the app must work from disk when offline.
Ask first
Decode in the loader or the view? The loader returns bytes here; decode and downsample off the main thread (Dispatchers.Default) before display. How big is the disk cache? A few hundred MB with LRU eviction; out of scope for this round, injected as an interface. Do we need priorities? Nice to have: visible rows first. Mention it, implement if time allows.
The design
A Mutex owns the state. The memory cache and the in-flight map are only touched while holding the lock: no data races. In-flight map of Deferreds. The first caller starts an async download; later callers await the same Deferred. That is request coalescing. Downloads live in the app scope. The Deferred runs in an injected scope with a SupervisorJob, so one caller leaving does not cancel it for the others, and one failure does not cancel the scope. Interfaces for I/O. Fetcher and disk cache are interfaces, so tests inject fakes and count network calls.
Edge cases
A download fails: every joiner gets the same exception and the URL can be retried. Cancelling a URL another visible row still needs (keep a reference count before cancelling). onTrimMemory: clearMemory(), keep disk. Very large images: downsample before caching.
Follow-up
“How would you add priorities?” Keep a queue of pending URLs with priority; visible rows bump priority, off-screen ones lower it; limit concurrent downloads with a Semaphore.