Design a Local Cache with Overflow Eviction

Problem Design a local cache — in-memory or disk-backed — that stores key-value data and evicts entries once it overflows a configured size limit.

Requirements

• get(key) -> value? — O(1)
• put(key, value) — O(1); evicts when inserting past capacity
• remove(key) and clear()
• Fixed capacity with a defined eviction policy on overflow
• Safe for concurrent access if shared across threads

Areas to design

• The structures giving O(1) lookup plus a recency ordering for eviction.
• A swappable eviction policy, and how "size" is defined (entry count vs bytes).
• Concurrency (reads mutate recency), TTL/staleness, and the small edge cases.