TikTok OA 面试真题解析：Cache Design（LRU Cache + TTL）

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 get or set within x seconds, 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 set operation is performed and the cache already contains n objects, the cache should automatically remove the least recently used object and insert the new one.

Please design such a cache.

这道题要求设计一个同时支持 <code>set</code>、<code>get</code>、TTL 过期和 LRU 淘汰的缓存系统。核心思路通常是用哈希表保证按 <code>id</code> 快速查找，再配合双向链表维护访问顺序，方便在容量满时删除最久未使用的元素；同时每个节点还要记录过期时间，<code>get</code> 和 <code>set</code> 时先判断是否过期，过期则直接清理。实现重点在于把“按时间失效”和“按最近使用淘汰”这两套规则统一到同一套数据结构中。