Thumbnail Cache With Least-Recent Eviction

Design a class ThumbCache that keeps at most capacity rendered thumbnails and throws away the one that has gone unused the longest:

• ThumbCache(capacity): capacity >= 1.
• get(key) returns the stored value, or -1 if key is absent. A successful get counts as a use.
• put(key, value) stores or replaces the value and counts as a use. If the cache then holds more than capacity keys, the least recently used key is removed.

Examples

ops:  ["ThumbCache", "put", "put", "get", "put", "get", "get", "put", "get", "get"]
args: [[2], [1, "a"], [2, "b"], [1], [3, "c"], [2], [3], [4, "d"], [1], [4]]
Output: [None, None, None, "a", None, -1, "c", None, -1, "d"]
Explanation: put(3) evicts key 2 (key 1 was used more recently); put(4) evicts key 1.

Constraints

• 1 <= capacity <= 10**4; keys are integers, values are strings or integers
• Up to 10**4 calls in total
• Target: get and put in O(1) average time

Goals

• Combine a hash map with an order structure for O(1) recency updates
• Evict the least recently used entry when a fixed capacity is exceeded