Design an LRU Cache
Last updated: March 3, 2025
Quick Overview
Design a Least Recently Used (LRU) Cache that supports the following operations: `get(key)` which retrieves the value of the key if it exists in the cache, and `put(key, value)` which updates or adds the key-value pair in the cache. The cache should evict the least recently used item when it exceeds its capacity, and both operations should run in O(1) time. The cache's capacity will be defined upon initialization.
ByteDance
March 3, 202510
3
4,565 solved
Design a Least Recently Used (LRU) Cache that supports the following operations: `get(key)` which retrieves the value of the key if it exists in the cache, and `put(key, value)` which updates or adds the key-value pair in the cache. The cache should evict the least recently used item when it exceeds its capacity, and both operations should run in O(1) time. The cache's capacity will be defined upon initialization.
Data structure design is a common ByteDance pattern. LRU cache appears frequently and tests combining hash maps with linked lists.
What the Interviewer Expects
- Implement O(1) get and put operations
- Use doubly-linked list and hash map combination
- Handle capacity-based eviction correctly
- Write clean, bug-free pointer manipulation code
- Discuss real-world applications
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you implement this in a thread-safe way?
- How would you add TTL expiration?
- How would you make this distributed across multiple machines?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
To implement an LRU Cache, we need to efficiently manage the storage of key-value pairs while ensuring that both retrieval (get) and insertion (put) operations run in O(1) time. The specific patte...
Approach
- Data Structures: Use a hash map (
dict) to store key-node pairs and a doubly-linked list to maintain the order of usage. The head of the list will represent the most recently used item, while ...
Submit Your Answer
