You are asked to implement an in-memory key-value cache with a fixed capacity. When the cache is full and a new item must be inserted, an eviction policy decides which existing item to remove.
Implement an LRU (Least Recently Used) cache supporting the operations below in O(1) average time:
get(key) -> value | -1
: Return the value for
key
if present, otherwise
-1
. A successful
get
counts as a “use”.
put(key, value) -> void
: Insert or update the key. A
put
of an existing key counts as a “use”. If insertion causes the cache to exceed
capacity
, evict the
least recently used
key.
Implement an LFU (Least Frequently Used) cache supporting the same get/put operations. Eviction rules:
get/put
.
Extend the cache design so that eviction behavior can be customized. For example, the cache may be constructed with something like:
evict_fn(keys, metadata) -> key_to_evict
Requirements:
get/put
.
capacity
is a positive integer.
capacity == 0
, all
put
operations store nothing and all
get
return
-1
.