Design and Implement an In-Memory Cache with Eviction and Memory Bound

Problem: Design and Implement an In-Memory Cache (Capacity Bound + Eviction) Implement an in-process (in-memory) cache that supports eviction when the cache reaches its capacity. You should also be able to discuss how to prevent unbounded memory growth and how the design could scale (discussion only; no need to code a distributed cache). Functional Requirements Implement the following APIs: get(key) -> value | None Return the value if the key exists (and is not expired, if you implement expiration); otherwise return None. put(key, value) -> None Insert or update a key/value pair. delete(key) -> bool Remove a key; return True if it existed, else False. Eviction and Capacity The cache has a fixed capacity capacity measured by number of entries. If a put makes the number of entries exceed capacity, evict according to the policy below. Use LRU (Least Recently Used): Every get/put counts as an access and updates recency. On eviction, remove the least recently accessed entry. Complexity Targets Average O(1) time for get/put/delete. O(capacity) space. Design Discussion Prompts (verbal) How do you ensure you don't run out of memory (capacity control, what if values are huge, bytes-based sizing, object lifetimes/references, etc.)? How would you scale this (multi-process / multi-machine): How to shard? How to route keys (e.g., consistent hashing)? How to handle consistency/propagation of evictions/invalidations? I/O Format (for this coding version) Read from stdin: Line 1: integer capacity Then one operation per line: PUT key value GET key DEL key For each GET, print one line (NULL if missing). For each DEL, print true/false. Example Input: 2 PUT a 1 PUT b 2 GET a PUT c 3 GET b GET c DEL a DEL c Output: 1 NULL 3 false true Explanation: capacity is 2. After GET a, a becomes most recent; inserting c evicts the least-recently-used entry b. Example Input 2 PUT a 1 PUT b 2 GET a PUT c 3 GET b GET c DEL a DEL c Output 1 NULL 3 false true