Cache Design
Design a cache that supports the following two basic operations:
set(id, object): store an object by its id;get(id): retrieve an object by its id.
At the same time, the cache has the following properties:
- Time-based expiration: if an object in the cache is not accessed by
getorsetwithinxseconds, it should expire automatically; - Capacity limit: the cache can be configured with an integer
n, which represents the maximum number of objects the cache can store; - LRU eviction: when a
setoperation is performed and the cache already containsnobjects, the cache should automatically remove the least recently used object and insert the new one.
Please design such a cache.
This problem asks you to design a cache that supports <code>set</code> and <code>get</code>, while also handling TTL expiration and LRU eviction. A typical solution combines a hash map for O(1) lookup by id with a doubly linked list to track recency for eviction when the cache reaches capacity. Each entry also needs expiration metadata so that expired items can be removed or ignored on access. The main challenge is coordinating time-based invalidation with least-recently-used replacement in a clean, efficient design.
END
