What is the least recently used cache problem?

The Least Recently Used (LRU) Cache problem is a crucial algorithmic challenge that appears in software engineering interviews. This problem assesses a programmer's ability to manage memory and data access efficiently using caching mechanisms. Grasping the LRU cache problem is vital for demonstrating advanced problem-solving skills and understanding of data structures, which are essential for optimizing software performance.

Problem Statement

Design and implement a data structure for a Least Recently Used (LRU) cache. This cache should support two operations: get and put.

  • get(key): Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  • put(key, value): Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Examples

  • Input:
    ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
    [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
  • Output:
    [null, null, null, 1, null, -1, null, -1, 3, 4]
  • Explanation:
    The cache reached its capacity of 2, so the least recently used item ([2,2]) was removed to make space for the new item ([4,4]).

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 3000
  • 0 <= value <= 10^4
  • At most 3 * 10^4 calls will be made to put and get.

Approaches to the LRU Cache Problem

Using Ordered Dictionary

Method: Utilize Python's collections.OrderedDict to keep items in order of use.

Python3
Python3

. . . .

Explanation: This approach leverages the OrderedDict to automatically maintain the order of insertion. Items are moved to the end when accessed or updated, ensuring that the least recently used items are at the start.

Time Complexity: O(1) for both put and get operations.
Space Complexity: O(n) as the cache size is bounded by the capacity.

Using Hash Map and Double-Linked List

Method: Combine a hash map and a double-linked list to achieve efficient item look-up and insertion/removal operations.

Python3
Python3

. . . .

Explanation: This method uses a hash map to track nodes' addresses, which allows constant time access, and a double-linked list to keep the nodes in order of use, allowing constant time insertions and deletions.

Time Complexity: O(1) for both put and get operations.
Space Complexity: O(n) due to the storage required for the cache and double-linked list.

Application

The LRU cache problem is fundamental in systems design interviews and is crucial for creating efficient web servers, databases, and caching systems that require fast access to frequently used data while maintaining tight control over memory usage.

Conclusion

The LRU cache problem showcases how combining simple data structures in innovative ways can significantly enhance performance in critical systems. Mastering the implementation of such algorithms is vital for any software engineer aiming to develop high-performance applications and excel in technical interviews.

TAGS
Coding Interview Questions
CONTRIBUTOR
Arslan Ahmad
Arslan Ahmad
ex-FAANG engineering manager and author or Grokking series.

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
700. Search in a Binary Search Tree - Detailed Explanation
Find a value in a binary search tree by comparing at each node and descending one side, in O(h) time, with the iterative loop that uses no stack.
199. Binary Tree Right Side View - Detailed Explanation
How to collect the rightmost node of every level of a binary tree with a queue, plus a right first depth first search and the cost of each.
334. Increasing Triplet Subsequence - Detailed Explanation
Why two running candidates decide an increasing triplet in a single pass, with O(1) extra space.
What is a good revision strategy for coding interview problems?
338. Counting Bits - Detailed Explanation
Count the set bits of every number from 0 to n in linear time, by reusing the count of a number you have already solved rather than counting bits again.
739. Daily Temperatures - Detailed Explanation
How to answer Daily Temperatures with a monotonic stack of indices that resolves every waiting day in one linear pass.
Related Courses
New
Grokking Agentic Design Patterns course cover
Grokking Agentic Design Patterns
Design agents that act safely, recover from failure, and justify their cost.
4.9
(561 learners)
Discounted price for Your Region

$98

New
Grokking the AI System Design Interview course cover
Grokking the AI System Design Interview
Learn to design AI systems the way interviewers expect: classic ML products, LLM and RAG architectures, and agentic systems, all through the lens of the system design interview.
4.6
(3,192 learners)
Discounted price for Your Region

$98

Grokking the Coding Interview: Patterns for Coding Questions course cover
Grokking the Coding Interview: Patterns for Coding Questions
The 24 essential patterns behind every coding interview question. Available in Java, Python, JavaScript, C++, C#, and Go. The most comprehensive coding interview course with 543 lessons. A smarter alternative to grinding LeetCode.
4.6
Discounted price for Your Region

$197

Design Gurus logo
One-Stop Portal For Tech Interviews.
About Us
Our Team
Careers
Partners
Contact Us
Become Affiliate
Copyright © 2026 Design Gurus, LLC. All rights reserved.