Design and Implement an LRU Cache
Last updated: October 30, 2025
Quick Overview
Design and implement a Least Recently Used cache with O(1) get and put operations. Include proper eviction logic and handle all edge cases.
Intuit
October 30, 202514
6
4,557 solved
Design and implement a Least Recently Used cache with O(1) get and put operations. Include proper eviction logic and handle all edge cases.
A classic data structure question that appears in phone screens and Glider assessments. Intuit evaluates code cleanliness and API design alongside correctness.
What the Interviewer Expects
- Implement O(1) get and put using a hash map and doubly linked list
- Handle cache eviction correctly when capacity is reached
- Write clean, well-structured code with meaningful variable names
- Cover edge cases like accessing non-existent keys and zero-capacity cache
- Discuss thread safety considerations
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 make this thread-safe?
- How would you add TTL-based expiration to each cache entry?
- What changes would you make for an LFU cache instead?
- How would you implement a distributed version of this cache?
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 (Least Recently Used) cache, we need to ensure that both get and put operations run in O(1) time complexity. The optimal data structures for this are:
- Hash Map: This al...
Approach
Here's a step-by-step algorithm for implementing the LRU Cache:
- Initialize the Cache: Create an empty hash map and a doubly linked list. The hash map will store the keys and their correspondin...
Submit Your Answer
