10.14 腾讯后台开发一面：设计带过期时间的缓存与两道手撕

《面试题目》

1. 设计一个支持设置过期时间的缓存系统。
2. key 过期后如何清理？
3. 续期和删除发生冲突如何解决？
4. 手撕（LeetCode 变体）：人口最多的年份。
5. 手撕（LeetCode 变体）：每日温度。

《参考解析》

过期缓存的整体设计：先定存储结构，再谈清理策略

这题是「设计题 + 八股」的混合，答的时候要有结构。先明确接口：set(key, value, ttl)、get(key)、del(key)、expire(key, ttl)，并说明 ttl 可以覆盖式设置。再定存储：一个字典存 key 到值的映射，另一个字典（或同一结构的字段）单独存 key 的到期时间戳——过期时间独立存而不是混进 value，是为了让清理和判断不必反序列化值。然后是语义问题：get 遇到已过期但还没被清理的 key，行为必须是当作不存在并顺手删掉（惰性删除），绝不能返回过期数据。最后把清理策略、内存淘汰、持久化和并发一致性逐个展开，面试官基本就是顺着这几条追问。

key 过期后的清理：惰性删除 + 定期删除 + 内存淘汰三层配合

惰性删除在每次读写该 key 时检查过期时间，代价是访问不到的死 key 会一直占内存；定期删除按固定频率随机抽样一批带过期时间的 key，删掉过期的，如果过期比例超过阈值就继续抽样——随机抽样是为了给清理行为一个 CPU 上界，避免全量扫描卡住主线程；内存淘汰是最后一层兜底，当内存达到上限时按策略（LRU/LFU/随机/TTL）淘汰，保证服务不会因为 key 只增不减而 OOM。三层要一起讲，只说「定时器扫描」会被追问「几百万 key 怎么办」，只说惰性删除会被追问「冷 key 谁来删」。加分点还有几个：从库不主动删过期 key，读到逻辑过期返回空、等主库的删除命令同步过来，否则主从数据会不一致；持久化时过期时间戳要一起存，RDB 加载时按当前时间判断是否已过期，AOF 重放要保证删除命令到位；单机非分布式场景可以用时间轮或最小堆做到期调度，精度高但每个 key 都有额外结构开销，key 量大时仍然要靠抽样。

续期与删除的冲突：本质是并发下的所有权校验

这道追问几乎一定会被问，面试官想听的是「你意识到这里有竞态」。典型场景是分布式锁的看门狗续期与持锁方释放同时发生：如果续期请求晚于释放到达，并且校验不严，就会出现「锁已经被释放、却被续了命」的经典 bug。解决思路有四条：一是把校验和续期做成原子操作，用 Lua 脚本或单线程命令在同一把锁上完成「比对持有者标识 + 延长租约」；二是给每次持有分配版本号或 epoch，续期只认当前版本，释放时版本加一，迟到的续期请求因为版本对不上直接失败；三是让删除优先——一旦删除发生，续期必须失败，续期方要能感知到失败并停止工作；四是租约本身要设上限和最大续期次数，网络分区或进程卡死时不能靠无限续期活着，再配合 fencing token 让下游拒绝过期持有者的写请求。缓存场景同理：滑动过期与主动失效并发时，用「删除后旧版本续期一律拒绝」的规则收口，比在两个接口里各自加判断可靠。

两道手撕：差分数组与单调栈

人口最多的年份是差分（扫描线）的标准变体：每个人贡献两个端点，出生年在差分数组上加一、死亡年减一，注意死亡当年不算在世，所以是「死亡年」这个位置减一而不是死亡年加一；再做一次前缀和，取最大的那个年份，年份相同时取更早的。要主动交代边界：年份范围固定可以直接开数组，范围大就用有序表或排序后扫描；并列时的取舍规则要事先跟面试官确认。每日温度是单调栈的入门题：维护一个存下标的栈，栈内温度严格递减，遍历到更高温度时不断弹栈并把天数差写进答案，均摊 O(n)；暴力双层循环是 O(n²)，面试时至少要说清为什么单调栈更优。原帖提到双机位手撕共三道、第一道记不清，说明这轮代码量不小——练的时候要按 15 分钟内写完一道并自己跑边界（空输入、单元素、全递增全递减）的标准来。