Implement LRU/LFU cache with custom eviction

Problem Statement

Design a thread-safe CustomCache class that supports a fixed capacity and allows for pluggable eviction policies. You must implement the data structure to handle put(key, value) and get(key) operations in O(1) average time complexity, regardless of the eviction policy.

The class should accept an EvictionPolicy interface, which defines how an entry is selected for removal when the cache reaches capacity.

Requirements

1. put(key, value): Insert or update a key-value pair. If capacity is exceeded, invoke the policy to evict an item.
2. get(key): Return the value associated with the key and update the policy's metadata (e.g., frequency or recency).
3. You must implement two policies: LRU (Least Recently Used) and LFU (Least Frequently Used).

Interface

class CustomCache:
    def __init__(self, capacity: int, policy: str):
        pass

    def get(self, key: int) -> int:
        pass

    def put(self, key: int, value: int) -> None:
        pass

Constraints

• capacity is a positive integer.
• key and value are integers.
• Ensure get operations on non-existent keys return -1.

Example

# Using LRU
cache = CustomCache(2, "LRU")
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)    # returns 1
cache.put(3, 3) # evicts key 2
cache.get(2)    # returns -1