LRU Cache
Design a data structure that follows the Least Recently Used (LRU) cache policy.
Implement the following operations:
- get(key) — return the value associated with key, or -1 if the key does not exist.
- put(key, value) — insert or update a key-value pair.
When the cache reaches its capacity, inserting a new key should remove the least recently used key.
Both get and put should run in O(1) average time.
Example 1
Input
2 9 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4
Output
1 -1 -1 3 4
Explanation
The cache capacity is 2.
After get(1), key 1 becomes recently used. When 3 is inserted, key 2 is the least recently used and is removed.
Later, inserting 4 removes key 1.
Example 2
Input
2 7 put 1 10 put 2 20 put 1 15 get 1 put 3 30 get 2 get 3
Output
15 -1 30
Explanation
put(1, 15) updates the existing value and makes key 1 recently used. Therefore, when key 3 is inserted, key 2 is removed.
Constraints
Hints:
Hint 1
Use a Hash Map to find a key in O(1) average time.
Hint 2
Use a Doubly Linked List to maintain the order of recently used keys, allowing insertion, deletion, and movement in O(1).
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 18, 2026
Last updated
Aug 19, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output