The Question
CodingDesign an LRU Cache
Design and implement a data structure for a Least Recently Used (LRU) Cache. It should support 'get' and 'put' operations in O(1) time complexity. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.
Java
HashMap
Doubly Linked List
LRU Cache
Questions & Insights
Clarifying Questions
What are the constraints on capacity? Can the capacity be zero or negative, and what is the maximum expected number of elements?
What should the behavior be for `get` operations on non-existent keys? (Standard is returning -1 or null).
Are the keys and values restricted to integers, or should the solution be generic?
Is thread safety required for this implementation?
Thinking Process
To achieve O(1) lookup, a Hash Map is essential to map keys to their corresponding values or nodes.
To achieve O(1) updates for the "Least Recently Used" ordering, a Doubly Linked List (DLL) is the ideal structure. It allows us to remove a node from the middle and move it to the "head" (most recent) in constant time, provided we have a reference to the node.
Each time a key is accessed (
get) or updated (put), we move the corresponding node to the head of the DLL.When the cache exceeds its capacity during a
put operation, we remove the node at the tail of the DLL (the least recently used item) and delete its entry from the Hash Map.Implementation Breakdown
Problem Set
Functional Requirements:
LRUCache(int capacity): Initialize the cache with a fixed size.int get(int key): Return the value if the key exists, otherwise -1. Move the key to the "most recently used" position.void put(int key, int value): Update the value if the key exists or insert the key-value pair. If capacity is reached, evict the least recently used item.Constraints:
Time Complexity: O(1) for both
get and put.Space Complexity: O(capacity).
Approach
Algorithm: LRU Eviction Policy logic.
Data Structure:
HashMap<Integer, Node> + Custom Doubly Linked List.Complexity:
Time: O(1)
Space: O(N) where N is the capacity.
Implementation
Wrap Up
Advanced Topics
Readability vs. Performance: In Java, one could extend
LinkedHashMap and override removeEldestEntry. While concise, a custom DLL (as shown above) is often preferred in interviews to demonstrate low-level pointer manipulation and data structure design.Concurrency: To make this thread-safe, one could wrap operations in
synchronized blocks or use ReentrantReadWriteLock. However, a ReadWriteLock is tricky here because get operations modify the DLL (a write operation), making every call essentially a write.Distributed Adaptation: In a distributed system (like Redis), LRU is often approximated using sampling rather than a strict DLL to save memory and reduce lock contention across multiple shards.