Design and Implement a Thread-Safe LRU Cache
SnapchatSoftware Engineer · Technical Screen
Last updated
Design an `O(1)` LRU cache and extend it with clear thread-safety semantics. The solution covers hash-map and doubly linked-list invariants, boundary cases, linearization points, single-lock correctness, sharding trade-offs, eviction callbacks, and concurrent testing.
Design and Implement a Thread-Safe LRU Cache
Design an in-memory cache with fixed positive capacity and operations get(key) and put(key, value).
getreturns the value when present and marks the key most recently used; otherwise it returns a defined miss result.putupdates and refreshes an existing key, or inserts a new key as most recently used.- Inserting beyond capacity evicts the least recently used key.
- Both operations should be
O(1)average time.
After explaining the single-threaded data structure, make the cache safe for concurrent callers. Define the consistency guarantee and identify the exact linearization point of get, put, and eviction.
Clarifying Questions to Ask
- Are keys and values immutable, and may a stored value be null?
- Is strict linearizability required, or is approximate recency acceptable for higher concurrency?
- Can a value require cleanup when evicted?
- Is one cache instance small enough for a single lock, or is contention already measured?
Follow-up questions
- Why can a read-write lock fail to improve concurrency when every hit changes recency?
- How would you invoke an eviction callback without deadlocking the cache?
- What semantics would you choose if two threads update the same key concurrently?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.