Design an in-memory cache with a fixed capacity. When it is full and a new item arrives, it must evict one item by a rule: least recently used (LRU) or least frequently used (LFU). Both `get` and `put` must run in O(1) time.
It must
get(key) returns the value or nothing, and counts as a use.put(key, value) adds or updates, and evicts one item if the cache is over capacity.- Both operations run in O(1) time.
- The eviction rule is pluggable: LRU and LFU at least.
- Optional extras: items that expire after a time, and use from several threads.
Keep in mind
- A hash map alone gives O(1) lookup but not O(1) 'which item was used least recently?'.
- Keys and values are generic (any type).
- Persistence and distribution (many machines) are out of scope.