Design an LRU Cache
Last updated: March 3, 2025
Quick Overview
Implement a data structure supporting O(1) get and put with least-recently-used eviction. A ByteDance classic.
ByteDance
March 3, 202510
3
4,565 solved
Implement a data structure supporting O(1) get and put with least-recently-used eviction. A ByteDance classic.
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
Implementation
```python class Node: def __init__(self, key=0, val=0): self.key, self.val = key, val self.prev = self.next = None class LRUCache...
Key Design
Dummy head and tail nodes simplify edge cases (no null checks). The hash map provides O(1) lookup. The doubly-linked list provides O(1) removal and in...
Submit Your Answer
