Implement LRU/LFU cache with custom eviction

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.

Part A — LRU Cache

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.

Part B — LFU Cache

Implement an LFU (Least Frequently Used) cache supporting the same get/put operations. Eviction rules:

• Evict the key with the lowest access frequency .
• If multiple keys tie on frequency, evict the least recently used among those tied keys .
• Target O(1) average time for get/put .

Part C — Custom Eviction Function

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:

• The cache must still support get/put .
• When full, it must call the provided eviction function (or policy object) to select a key to remove.
• Clearly define what metadata is tracked (e.g., recency, frequency, timestamps) and how it is updated.

Clarifications / Constraints

• Keys are hashable (e.g., integers or strings) and values are arbitrary objects.
• capacity is a positive integer.
• If capacity == 0 , all put operations store nothing and all get return -1 .
• State any additional assumptions you need.