Weighted Cache / Timed Cache

Implement a cache with either weighted capacity eviction or fixed per-item expiration. Follow-ups focus on cleanup strategy, hot-path `get`, capacity limits, and production trade-offs. Requirements Weighted cache variant: put(key, value, weight) inserts or updates an item. get(key) returns the value if present. Total weight must not exceed capacity; when over capacity, evict the heaviest item or apply the interviewer-specified policy. Timed cache variant: Each item has a fixed cache time / TTL. get is the hot path and should avoid doing heavy cleanup. A sidecar cleanup process may remove expired entries. Build the implementation from scratch, including the cache class, tests, and a dry run. Clarify the input/output contract and edge cases before coding. Follow-ups: lazy cleanup, capacity limit, LRU cleanup, concurrency, scale, OOM failure modes, and the choice among cache-eviction policies. Notes For weighted eviction, maintain key -> node plus an ordered structure by weight. A max-heap is simple but needs lazy deletion for updates; a balanced tree or buckets by weight gives cleaner deletions. If the policy is truly "evict heaviest," it is not LFU or LRU. Clarify ties: oldest, newest, or arbitrary. For timed cache, store expires_at with each value. get can check only the requested key and return miss if stale; background cleanup handles memory pressure. If get must never clean, stale entries remain until sidecar cleanup, so memory can exceed live-key count. Make this trade-off explicit. With concurrency, use either a coarse lock first or lock striping by key. Avoid holding a global lock during long cleanup scans. Be ready to connect OOM behavior to stale-entry buildup, capacity enforcement, cleanup cadence, and the chosen eviction policy. The production discussion also covers scalability rather than stopping at an in-memory implementation. A common timed-cache phrasing is a print-dedup: print a key's value only if it was not printed within the last 10 seconds. The interviewer then pivots to engineering follow-ups — if the server crashes in production, how does the cache survive (persistence, replication, warm rebuild)? Have a durability story ready, not just the in-memory data structure. Preparation Implement weighted cache with lazy heap deletion. Implement TTL cache with put, get, deleteExpired(now). Add tests for update existing key, equal weights, expired key, and capacity overflow. Prepare a production discussion around cleanup cadence, clock skew, and memory pressure.