Design an in-memory cache whose capacity is limited by total weight rather than by the number of entries.
Each entry has:
-
a
key
-
a
value
-
a positive integer
weight
Support the following operations:
-
get(key)
: return the value associated with
key
, or
-1
if the key is not present.
-
put(key, value, weight)
: insert a new entry or update an existing one.
The cache has a maximum allowed total weight W. After every put, if the sum of weights of all cached entries exceeds W, repeatedly evict entries until the total weight is at most W.
Eviction rule:
-
Evict the entry with the
largest weight
first.
-
If multiple entries have the same weight, evict the
least recently used
among them.
Additional rules:
-
A successful
get
makes the entry most recently used.
-
Updating an existing key through
put
also makes it most recently used.
-
If a single entry's weight is greater than
W
, it should not remain in the cache.
Implement this data structure efficiently.