146. LRU Cache
LRU Cache (LeetCode 146) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.
How to solve LRU Cache
LRU Cache is a Data Structure Design problem, part of Design Patterns. Design and implement data structures: LRU cache, LFU cache, HashMap, and specialized structures.
Work towards the solution in these steps:
- Think about which data structures allow for fast access and also maintain an order of usage.
- Consider combining a hash map with a doubly linked list to achieve both O(1) access and ordering.
- Use the hash map to quickly locate nodes in the linked list that store key-value pairs.
The reference solution runs in O(1) time and O(capacity) space.
The LRU Cache solution and editorial walks through the full approach with reference code.
Problem statement
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return -1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
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 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4
Constraints:
- 1 <= capacity <= 3000
- 0 <= key <= 104
- 0 <= value <= 105
- At most 2 105 calls will be made to get and put.
Topics and companies
Topics: Hash Table, Linked List, Design, Doubly-Linked List.
Reported in interviews at Amazon, Microsoft, Facebook, Apple, Bloomberg, Intuit, Snapchat, eBay, ByteDance, Google, Oracle, Zillow and others.
How to practise LRU Cache on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) time and O(capacity) space.
Open LRU Cache in the code editor, or read the LRU Cache editorial for a worked solution with its approach and complexity analysis.
Where LRU Cache sits in the DSA pattern sheet
Problems related to LRU Cache
Other problems that use the same Design (General/Specific) and Design Patterns techniques:
- All O`one Data Structure — Hard, same subpattern
- Design a Stack With Increment Operation — Medium, same subpattern
- Design a Text Editor — Hard, same subpattern
- Design Circular Deque — Medium, same subpattern
- Design Circular Queue — Medium, same subpattern
- Design Compressed String Iterator — Easy, same subpattern
LRU Cache FAQ
What is the LeetCode number of LRU Cache?
LRU Cache is LeetCode problem 146, rated Medium.
What pattern is used to solve LRU Cache?
LRU Cache is a Data Structure Design problem. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.
What is the time complexity of LRU Cache?
The reference solution runs in O(1) time and O(capacity) space.
Which companies ask LRU Cache?
LRU Cache has been reported in interviews at Amazon, Microsoft, Facebook, Apple, Bloomberg, Intuit, Snapchat, eBay, ByteDance, Google, Oracle, Zillow and others.