The bug

You're asked to implement an LRU cache for decoded bitmap thumbnails in a coding round, or you
write one for real in a feed screen. Either way, the first version almost everyone writes looks
like this:

class NaiveLruCache(private val capacity: Int) { private val map = LinkedHashMap<String, ByteArray>(capacity, 0.75f, true) fun get(key: String): ByteArray? = map[key] fun put(key: String, value: ByteArray) { map[key] = value if (map.size > capacity) { val oldest = map.keys.first() map.remove(oldest) } } }

It passes every test you'd obviously write. It evicts the right key. get promotes recency
because LinkedHashMap's accessOrder = true constructor flag reorders on access. Looks done.

It isn't. Two things are wrong with it, and both are exactly the kind of thing that turns a
"looks correct" coding-round answer into a follow-up question you can't answer cleanly.

Problem 1: capacity by entry count, not by cost

A thumbnail cache's real constraint is memory, not item count. A capacity of 50 is meaningless
if entry #1 is a 40x40 placeholder icon and entry #2 is a 2000x2000 decoded bitmap. You evict
the wrong thing at the wrong time no matter which way you tune the number.

The fix is to track a running byte budget instead of an entry count, and evict from the tail
until you're back under budget — not just once:

class ByteBudgetLruCache(private val maxBytes: Long) { private data class Entry(val key: String, var value: ByteArray?) private val map = HashMap<String, Entry>() private val order = ArrayDeque<String>() // front = most recently used private var currentBytes = 0L @Synchronized fun get(key: String): ByteArray? { val entry = map[key] ?: return null order.remove(key) order.addFirst(key) return entry.value } @Synchronized fun put(key: String, value: ByteArray) { map[key]?.let { currentBytes -= it.value?.size ?: 0; order.remove(key) } map[key] = Entry(key, value) order.addFirst(key) currentBytes += value.size while (currentBytes > maxBytes && order.isNotEmpty()) { val lruKey = order.removeLast() currentBytes -= map.remove(lruKey)?.value?.size ?: 0 } } }

The while, not if, is the detail that matters: a single large put can push you over budget
by more than one entry's worth, and an if only evicts once.

Problem 2: ArrayDeque.remove(key) is O(n)

This is the part that actually gets asked as a follow-up. order.remove(key) on every get
and every re-put is a linear scan — fine in a coding round where nobody's timing you against a
real dataset, not fine in a cache that's supposed to be O(1).

The real fix — the one Android's own LruCache effectively does internally — is to combine a
hash map with a doubly-linked list, where each map value is a node with prev/next
pointers, so removing a node by reference is O(1) instead of a scan for its position:

class LruBitmapCache(private val maxBytes: Long) { private class Node(val key: String, var value: ByteArray?, var size: Long, var prev: Node? = null, var next: Node? = null) private val map = HashMap<String, Node>() private val head = Node("head", null, 0) private val tail = Node("tail", null, 0) private var currentBytes = 0L init { head.next = tail; tail.prev = head } private fun unlink(node: Node) { node.prev?.next = node.next node.next?.prev = node.prev } private fun pushFront(node: Node) { node.next = head.next node.prev = head head.next?.prev = node head.next = node } @Synchronized fun get(key: String): ByteArray? { val node = map[key] ?: return null unlink(node) pushFront(node) return node.value } @Synchronized fun put(key: String, value: ByteArray) { map[key]?.let { unlink(it); currentBytes -= it.size } val node = Node(key, value, value.size.toLong()) map[key] = node pushFront(node) currentBytes += node.size while (currentBytes > maxBytes) { val lru = tail.prev ?: break if (lru === head) break unlink(lru) map.remove(lru.key) currentBytes -= lru.size } } }

Now get and put are genuinely O(1) — no scan, ever, regardless of cache size. Every pointer
reassignment is a fixed handful of operations.

Why this is worth getting right, not just passing the happy path

Nobody notices an O(n) remove in a cache with 50 entries. It shows up as jank once the cache
grows past a few hundred, by which point it's load-bearing production code and the "quick fix"
from a coding round six months ago is now a profiler flag nobody can explain. The byte-budget
version matters even sooner — a fixed entry-count cache silently blows past its intended memory
footprint the first time someone adds a screen with larger images, and nothing in the type
system or a code review catches it, because the code still compiles and the tests (which use
small fixtures) still pass.

Both fixes are small. Catching the need for them before they ship is the actual skill.

If you want more problems in this shape — a real coding-round question wrapped around a real
Android scenario, with the solution and the follow-up question that usually trips people up —
I put together a free sample here: a sliding-window debounce problem, worked the same way as
this one. Debounce a Search API Call Without Dropping the Latest Keystroke — free sample on
GitHub

The full set is 27 problems across arrays/strings, hashing & caching (including the cache
above), tries, coroutines, sliding windows, graphs, and heaps — it's the
Android Coding Round Question Bank
if you want the whole thing as one PDF.