/Practice

Mobile machine coding reels

Mobile machine coding1 / 18
1 / 5

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.

Requirementsget(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 / 5

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.

3 / 5

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.

4 / 5

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.

ComplexityO(1) per get, put and remove; O(n) memory
5 / 5

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.

On iOSBuilt-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().
LRU cache with a memory budget
#mobile#machine coding
Mobile machine coding2 / 18
Medium · LruCache.kt

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>>()
Step 1/6A node per entry. Each node holds key, value and cost, plus pointers to its neighbours in recency order.
LRU cache with a memory budget · the code
A node per entry. Each node holds key, value and cost, plus pointers to its neighbours in recency order.
#kotlin#walkthrough
Mobile machine coding3 / 18
1 / 5

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.

RequirementsServe from memory, then disk, then network · Concurrent requests for one URL share a single download · Cancel work when a row is recycled · Safe to call from any coroutine
2 / 5

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.

3 / 5

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.

4 / 5

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.

ComplexityO(1) locked work per request; one network call per unique URL
5 / 5

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.

On iOSIn production: Kingfisher or Nuke: memory and disk caches plus request coalescing out of the box. · From scratch: An actor holding [URL: Task<Data, Error>]; callers await the same Task's value. · Cancellation: Cancel in prepareForReuse(), or tie the Task to the SwiftUI view with .task(id:).
Image loader with coalescing and two cache tiers
#mobile#machine coding
Image loader with coalescing and two cache tiers · the code
Offline outbox with idempotent sync
Offline outbox with idempotent sync · the code
Retry with exponential backoff and jitter
Retry with exponential backoff and jitter · the code
Search-as-you-type with debounce and cancellation
Search-as-you-type with debounce and cancellation · the code
Cursor-based infinite feed
Cursor-based infinite feed · the code
Resumable multipart uploader
Resumable multipart uploader · the code
Client-side token bucket rate limiter
Client-side token bucket rate limiter · the code
List diffing for animated UI updates
List diffing for animated UI updates · the code