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.