Design LRU Cache
Design an LRU Cache that supports get(key) and put(key, value) operations in O(1) time with automatic eviction of the least recently used item when capacity is exceeded.
What is an LRU Cache?
LRU stands for Least Recently Used. LRU Cache is a type of cache replacement policy that evicts the least recently accessed item when the cache reaches its capacity.
In performance-critical systems (like web servers, databases, or OS memory management), caching helps avoid expensive computations or repeated data fetching. But cache memory is limited so when it's full, we need a policy to decide which item to remove.
LRU chooses the least recently accessed item, based on the assumption that:
“If you haven’t used something for a while, you probably won’t need it soon.”
The LRU strategy is both intuitive and effective. It reflects real-world usage patterns. We tend to access the same small subset of items frequently, and rarely go back to older, untouched entries.
This makes LRU a popular default caching policy in many systems where speed and memory efficiency are critical.
Example
Suppose we have an LRU cache with capacity = 3, and we perform the following operations:
Final cache state: {3:C, 1:A, 4:D} (in order of usage from least to most recent)
In this chapter, we will explore the low level design of a LRU cache.
Lets start by clarifying the requirements:
1. Clarifying Requirements
Before starting the design, it's important to ask thoughtful questions to uncover hidden assumptions, clarify ambiguities, and define the system's scope more precisely.
Here is an example of how a discussion between the candidate and the interviewer might unfold:
Candidate: Should the LRU Cache support generic key-value pairs, or should we restrict it to specific data types?
Interviewer: The cache should be generic and support any type of key-value pair, as long as keys are hashable.
Candidate: Should the cache operations be limited to get and put, or do we also need to support deletion?
Interviewer: For now, we can limit operations to get and put.
Candidate: What should the get operation return if the key is not found in the cache?
Interviewer: You can return either null or a sentinel value like -1.
Candidate: How should we handle a put operation on an existing key? Should it be treated as a fresh access and move the key to the most recently used position?
Interviewer: Yes, an update through put should count as usage. The key should be moved to the front as the most recently used.
Candidate: Will the cache be used in a multi-threaded environment? Do we need to ensure thread safety?
Interviewer: Good question. Assume this cache will be used in a multi-threaded server environment. It must be thread-safe.
Candidate: What are the performance expectations for the get and put operations?
Interviewer: Both get and put operations must run in O(1) time on average.
After gathering the details, we can summarize the key system requirements.
1.1 Functional Requirements
- Support
get(key)operation: returns the value if the key exists, otherwise returnsnullor-1 - Support
put(key, value)operation: inserts a new key-value pair or updates the value of an existing key - If the cache exceeds its capacity, it should automatically evict the least recently used item.
- Both
getandputoperations should update the recency of the accessed or inserted item. - Keys and values should be generic (e.g.,
<K, V>), provided the keys are hashable.
1.2 Non-Functional Requirements
- Time Complexity: Both
getandputoperations must run in O(1) time on average. - Thread Safety: The implementation must be thread-safe for use in concurrent environments.
- Modularity: The design should follow object-oriented principles with clean separation of responsibilities.
- Memory Efficiency: The internal data structures should be optimized for speed and space within the defined constraints.
After the requirements are clear, the next step is to identify the core entities that we will form the foundation of our design.