Thread-Safe LRU Cache
Concurrency · Data Structures
Challenge Prompt
Implement a thread-safe LRU (Least Recently Used) cache using Arc<Mutex<>>. The cache should have a configurable capacity, support get and put operations, and evict the least recently used item when capacity is exceeded. Write unit tests that exercise concurrent access from multiple threads.
Common Bootcamp Mistakes
- Wrapping just the HashMap without tracking insertion/access order — LRU requires eviction order, not just storage
- Holding a MutexGuard across an .await point — this deadlocks on the next thread that tries to acquire the lock
- Only updating recency on put but not on get — a cache hit should also promote the key to most-recently-used
- Using Vec<K> for the ordering list — O(n) removal blows up under load; use VecDeque or a linked structure
Expert Hint
Keep two structures inside your locked state: HashMap<K, V> for O(1) lookup, and VecDeque<K> for LRU order. On every access, remove the key from VecDeque and push it to the back. On eviction, pop from the front. Wrap the whole inner struct in Arc<Mutex<LruInner>> so callers can .clone() the handle to share across threads without any unsafe.
Seeing this prompt on a real take-home?
Book a session