Build fluency in the vocabulary of a fixed-size cache evicting whichever entry hasn't been used in the longest time.
0 / 5 completed
1 / 5
At standup, a dev mentions a fixed-size cache that, once full, discards whichever entry hasn't been accessed for the longest time to make room for a new one. What is this eviction strategy called?
Least recently used (LRU) eviction discards whichever entry hasn't been accessed for the longest time once a fixed-size cache fills up, on the assumption that an entry nobody has touched in a while is also the least likely to be needed again soon. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This recency-based eviction rule is exactly what an LRU cache is named for, and it's typically implemented with a combination of a hash map for fast lookup and a doubly linked list to track access order efficiently.
2 / 5
During a design review, the team pairs a hash map for O(1) lookup with a doubly linked list tracking access order, specifically so both getting a cached value and evicting the least recently used entry stay fast. Which capability does this pairing provide?
This pairing provides constant-time get and evict operations, since the hash map locates any cached entry instantly by key, and the doubly linked list lets that same entry be moved to the most-recently-used end, or removed entirely when evicting the least-recently-used one, in constant time as well, because a doubly linked list allows removing a node without scanning the whole list. Scanning every cached entry's last-access time on every operation would instead cost time proportional to the cache's size on every single get or evict. This hash-map-plus-linked-list pairing is exactly the standard implementation behind a genuinely fast LRU cache.
3 / 5
In a code review, a dev notices an LRU cache implementation tracks each entry's last-access time as a plain field, but finds the actual least-recently-used entry by scanning every single cached entry whenever an eviction is needed. What does this represent?
This is an LRU cache with a linear-time eviction operation, since scanning every single cached entry to find the one with the oldest last-access time costs time proportional to how many entries the cache currently holds, which is far slower than the constant-time eviction a properly linked-list-backed implementation provides. Constant-time eviction is exactly what this implementation is missing, not something it happens to already achieve. This scan-based approach is exactly the kind of implementation detail a performance-focused reviewer flags, since the cache technically enforces LRU semantics while giving up the performance benefit a linked list is meant to provide.
4 / 5
An incident report shows an application's response times spiked whenever its LRU cache filled up and needed to evict an entry, because the implementation scanned every cached entry's last-access time in full to find the least-recently-used one instead of tracking access order with a linked list. What practice would prevent this?
Tracking access order with a doubly linked list alongside the hash map lets the least-recently-used entry be located and removed in constant time on every single eviction, which is exactly the fix for the response-time spikes described in this incident. Continuing to scan every cached entry's last-access time in full on every eviction is exactly what caused those spikes as the cache filled up and had to make room for new entries. This hash-map-plus-linked-list combination is the standard, well-understood implementation for an LRU cache that needs to stay fast under real load.
5 / 5
During a PR review, a teammate asks why the team bothers maintaining a doubly linked list alongside the hash map instead of just storing a last-access timestamp on each entry and scanning for the oldest one only occasionally. What is the reasoning?
Scanning for the oldest timestamp, even if done only occasionally rather than on every eviction, still costs time proportional to how many entries the cache currently holds every single time that scan actually runs, and as the cache grows larger, each of those occasional scans gets correspondingly more expensive. The linked list instead keeps every single eviction, and every single access-order update, at a small constant cost no matter how large the cache grows, since it never needs to scan anything. The tradeoff is the small extra bookkeeping cost of maintaining the linked list's pointers on every access, which is well worth it for a cache expected to handle a large, high-throughput workload.