Design a least-recently-used cache that supports fast insert, lookup, and eviction.
Problem
Design a data structure that stores key-value pairs with a fixed capacity and supports the following operations efficiently:
get(key): return the value associated withkeyif it exists; otherwise return-1.put(key, value): insert or update the value forkey.
When the cache reaches its capacity and a new key must be inserted, evict the entry that was used least recently. A key is considered recently used whenever it is accessed by get or updated/inserted by put.
Your implementation should aim for constant-time average complexity per operation.
Input Format
Input
A sequence of operations on an LRU cache instance:
LRUCache(capacity)creates the cache.get(key)queries a key.put(key, value)inserts or updates a key.
For interview practice, the cache is usually tested through method calls rather than a single standard input format.
Output Format
Output
For each get(key) operation, return the stored value if present; otherwise return -1. put operations do not return a value.
Constraints
Constraints
- Cache capacity is a positive integer.
- Keys and values are typically integers.
- Aim for average time for both
getandput. - The cache must evict exactly one least-recently-used entry when inserting into a full cache.
Example 1
Input
capacity = 2 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
After put(1,1) and put(2,2), key 1 is most recently used because of get(1). Inserting 3 evicts key 2. Inserting 4 later evicts key 1. The remaining keys are 3 and 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.