Implement a Key-Value Cache with Per-Entry Expiration

## Prompt Design and implement a key-value cache whose entries have independent expiration times. `get` must never return an expired value. When the cache reaches its memory limit, evict the oldest live entry. Explain method contracts, data structures, cleanup, capacity accounting, and concurrency. ### Constraints & Assumptions - Each `put` supplies a key, value, byte cost, and expiration timestamp. - Updating a key replaces its value, age, cost, and expiration. - Expired entries should be reclaimed before a live entry is evicted. - Oldest means earliest successful insertion or replacement time, with a sequence number breaking ties. ### Clarifying Questions to Ask - Is capacity measured by entry count or bytes? Use bytes for this design. - Does `get` refresh age? It does not under oldest-insertion eviction. - May an individual value exceed the entire cache capacity? ```hint Use generations for lazy deletion Put an entry generation in both ordering structures and compare it with the key map before changing state. ``` ```hint Clean expiration before capacity eviction An entry can be oldest and expired; reclaiming it must not trigger a second capacity decrement when its age record appears later. ``` ### What a Strong Answer Covers - Precise `put`, `get`, and delete behavior at expiration boundaries. - Structures for key lookup, oldest-live eviction, and efficient expiration cleanup. - Safe replacement and single-source capacity accounting despite stale queue entries. - Complexity, concurrency control, and a bound on cleanup work. - Tests for overwrite, expired-oldest ordering, oversized values, and simultaneous operations. ### Follow-up Questions 1. How would you change the policy from oldest-insertion to LRU? 2. How would you bound tail latency when millions of entries expire at once? 3. How would you shard the cache while keeping an approximate global byte limit?