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
Coding & Algorithms
Software Engineer
ByteDance
March 3, 2025
Software Engineer
Coding Round
Coding & Algorithms
Medium

10

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
LRU cache
Doubly-linked list
Hash map
Data structure design
O(1) operations
How to Approach This
  1. Clarify input constraints and edge cases before writing code.
  2. Walk through your approach verbally and confirm with the interviewer before coding.
  3. Start with a brute force solution, then optimize. Mention time and space complexity.
  4. Test your solution with examples, including edge cases like empty input or duplicates.
  5. 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 Problems
Sample 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
Markdown supported

Related Questions