LRU Cache
MediumDesign a Least Recently Used (LRU) cache that supports get(key) and put(key, value), both in O(1) time complexity.
Example:
Input: LRUCache cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // removes key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // removes key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4
Test Cases
Test Cases
Input
10 LRUCache 2 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4
Expected Output
1 -1 -1 3 4
Step 1
Step 2
Step 3
Step 1: Identify the Pattern
LRU Cache
MediumDesign a Least Recently Used (LRU) cache that supports get(key) and put(key, value), both in O(1) time complexity.
Example:
Input: LRUCache cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // removes key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // removes key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4
Test Cases
Test Cases
Input
10 LRUCache 2 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4
Expected Output
1 -1 -1 3 4
Step 1
Step 2
Step 3
Step 1: Identify the Pattern