Design an LRU Cache

hard

Your image service keeps thumbnails in a fixed-size memory cache. When it's full and a new thumbnail arrives, evict the one that's been untouched the longest — Least Recently Used. Both operations must be O(1): this sits on the hot path of every request.

Implement an LRUCache class with:

get(key) — return the value, or -1 if absent. Counts as a "use".
put(key, value) — insert or update. Counts as a "use". If inserting over capacity, evict the least recently used key first.

Tests drive your class through an operations list: ops like [["put", 1, 1], ["get", 1]] plus a capacity. The harness (already written) replays them and collects outputs — null for put, the returned value for get. Your work is the class.

Example 1

in ops = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3]], capacity = 2

out [null, null, 1, null, -1, 3]

get(1) refreshes key 1, so put(3,3) evicts key 2 — the least recently used.

Example 2

in ops = [["get", 5]], capacity = 1

out [-1]

Example 3

in ops = [["put",2,1],["get",2],["put",3,2],["get",2],["get",3]], capacity = 1

out [null, 1, null, -1, 2]

Constraints

· 1 <= capacity <= 3000
· 0 <= key, value <= 10^4
· up to 10^5 operations
· get and put must each be O(1) average