Design a least-recently-used cache
DSA, Medium
Which structure or algorithm, and what does it cost.
Build a cache with a fixed capacity. It has two operations. get(key) returns the stored value, or -1 if the key is absent, and marks the key as most recently used. put(key, value) stores the value and marks the key as most recently used. If the key already exists, it updates the value. If storing a new key would exceed the capacity, first remove the key that was used least recently. Both operations must run in O(1) average time.
Examples
Input Capacity 2: put(1,1), put(2,2), get(1)
Output 1
Why Order from oldest to newest is now 2, 1.
Input Capacity 2: put(3,3), then get(2)
Output -1
Why put(3,3) removes key 2, because key 2 is the least recently used.
Input Capacity 2: put(4,4), then get(1), get(3), get(4)
Output -1, 3, 4
Why put(4,4) removes key 1.
Constraints
- 0 <= capacity <= 100,000.
- Up to 1,000,000 calls.
- Keys and values are integers.
Your answer must contain
- The data structures and why each is needed; code for both operations (a helper list class may be described, not written, if you say so); cost; a hand trace of example 2.