mediumCodingConceptMidSeniorStaff
A cache must evict the least recently used entry and every operation has to be O(1). Which two structures do you need, and why is one of them not enough?
A hash map from key to a doubly linked list node, over one recency-ordered list. The map answers find-by-key, the list answers find-the-oldest, and neither answers the other in constant time. The detail that decides the answer is that the map stores the node rather than the value, which is what makes unlinking on a hit a fixed number of pointer writes.
5 min readUpdated 2026-08-15
Answer
Short answer
An O(1) LRU cache needs a hash map from key to list node and a doubly linked list ordered by recency. The map gives constant-time access by key, while the list exposes the least recently used node at one end for eviction. A hash map alone cannot find the oldest entry in O(1), and a list alone cannot find an arbitrary key in O(1).
Was this answer helpful?
Likely follow-ups
- Make it safe for many threads without serialising every read behind one lock. What do you give up?
- Change the policy to evict the least frequently used entry instead. What does the structure become?
- The cache holds entries with different byte sizes and the budget is in megabytes, not entries. What breaks?
- Implement it without a linked list at all, using only arrays and integer indices. Why might you want that?
Related questions
- Insert, delete and get-a-uniformly-random-member all have to be O(1). What breaks when you delete from the middle?mediumAlso on hash-map and amortised-complexity6 min
- Count the subarrays whose elements sum to k, where the values may be negative.mediumAlso on hash-map4 min
- You put @functools.lru_cache on a method to speed it up, and the service's memory keeps growing. Why, and which fix do you choose?mediumAlso on lru-cache4 min
- Group a list of words so that words which are anagrams of each other end up together. What is your key, and what does it cost?mediumAlso on hash-map5 min