How would you design a Least Recently Used (LRU) cache using Python's built-in data structures?
LRU cache with OrderedDict in O(1) per operation
An LRU cache needs O(1) lookup, O(1) update, and O(1) eviction of the least recently used item. collections.OrderedDict is a natural fit: it preserves order and provides move_to_end(key) and popitem(last=False). On get, move the key to the end. On put, insert or update and move to the end; if over capacity, pop from the front. A plain dict plus a doubly linked list is the classic manual implementation, but OrderedDict encapsulates it. For function memoization, functools.lru_cache is usually the right tool.
- 1
Use OrderedDict when you need explicit LRU behavior with custom keys and values.
- 2
Use functools.lru_cache for pure functions; it is C-optimized and thread-safe for the cache structure.
- 3
Trade-off: an LRU cache adds memory and locking overhead. For high concurrency, sharding or a dedicated cache service may be better.
- 4
Common mistake: using a list and pop(0), which makes eviction O(n).
- 5
Version note: OrderedDict.move_to_end exists since Python 3.2; functools.lru_cache since 3.2 and has evolved with typed and user_function options.
Scenario Questions
0-2 years experience
- 1You need a cache that evicts oldest inserted. What built-in?
- 2You need a cache that evicts least recently used. What structure?
2-5 years experience
- 1Implement an LRU for a function. What is functools.lru_cache?
- 2Your LRU uses list and pop(0). Why is it slow?
5-8 years experience
- 1You need TTL plus LRU. How do you extend OrderedDict?
- 2You need thread-safe LRU. How do you synchronize?
8+ years experience
- 1Design a sharded LRU cache for a multi-core service with O(1) operations and consistent eviction.
- 2You need LRU with persistence and crash recovery. How do you design it?
Follow-up Questions
- How would you add TTL expiration to this LRU cache?
- How would you make this cache thread-safe without killing throughput?