今日头条后端暑期实习一面:LRU 加过期、两栈队列与断点续传由谁决定分片
- 轮次
- 一面
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 算法:实现 LRU 缓存,并支持「x 秒后自动过期」。
- 算法:用两个栈模拟队列,先写暴力解法,再优化。
- SQL 题:
select * from 表 where a < 1 and b > 1 and c = 1,如何优化? - 了解索引下推吗?
- HTTP 请求的数据结构是什么样的?
- 讲讲断点续传,每次传输的数据大小是服务端决定还是客户端决定?
- 简历追问:为什么从 WXG 离职?实习之后有什么感受?实习中最大的收获是什么?
- 还了解哪些限流算法?
- 为什么做开源?提过哪些 PR?
- 我们这边是 Go,对语言有要求吗?你觉得 C++ 和 Java 最大的不同是什么?
- 你觉得自己的沟通能力怎么样?
- AI Coding 方面有哪些经验?
- 讲讲上下文工程?讲讲 harness engineering?
- 现在是大三吗?有读研打算吗?办公地点在深圳可以吗?
- 反问环节。
《参考解析》
LRU 加自动过期:LRU 本身用哈希表加双向链表即可,get 与 put 都是 O(1)。加上「x 秒过期」后,需要为每个节点记录写入时间戳,读取时先判断是否过期,过期就当作未命中并删除。这种惰性删除会让已过期的键继续占内存,因此再配一个按过期时间排序的结构(最小堆或时间轮)做定期清理。用 LinkedHashMap 的 removeEldestEntry 也能实现 LRU,但过期时间仍要自己维护。面试时先说清两个维度的淘汰规则谁优先:一般先看是否过期,再按 LRU 淘汰容量。
两个栈模拟队列:入队压入 in 栈;出队时若 out 栈为空,把 in 全部倒入 out 再弹出。单次出队最坏 O(n),但每个元素最多被搬运两次,均摊 O(1)。优化点是避免「每次出队都倒栈」的写法,以及注意 out 非空时不能倒入,否则顺序会乱。
这条 SQL 的优化思路:a < 1 and b > 1 是两个范围条件,c = 1 是等值条件。联合索引应按「等值列在前、范围列在后」排列,建 (c, a) 或 (c, b) 取决于两列的选择性与业务查询分布;同一个索引里放两个范围列时,第二个范围列只能用于索引下推过滤,无法缩小扫描区间。若 select * 需要回表且命中行数多,优化器可能宁愿全表扫,此时要么收敛查询列做覆盖索引,要么接受全表扫。回答时给出「先看 EXPLAIN 的 type、key、rows,再决定建什么索引」的顺序,比直接报一个索引定义更可信。
索引下推(ICP):MySQL 5.6 引入,把 WHERE 中能用索引列判断的条件下推到存储引擎层,在遍历索引时就过滤掉不匹配的记录,减少回表次数。EXPLAIN 的 Extra 出现 Using index condition 即表示生效。它不改变扫描区间,只是少回表,因此不能把「范围列后面的等值条件」当成真正用上了索引。
HTTP 请求报文结构:请求行(方法、URI、协议版本)、请求头(Host、Content-Type、Content-Length、Cookie 等)、空行、请求体。响应报文对应状态行、响应头、空行、响应体。追问点通常在 Content-Length 与 Transfer-Encoding: chunked 的互斥关系,以及 Host 在虚拟主机场景下的作用。
断点续传由谁决定分片:由客户端发起。客户端在请求头带 Range: bytes=start-end,服务端若支持则返回 206 Partial Content 与 Content-Range,并在响应头声明 Accept-Ranges: bytes。分片大小通常由客户端根据网络与重试策略决定,服务端只负责按范围返回;服务端可以用 ETag / Last-Modified 配合 If-Range 校验文件是否变化,避免续传拼出错文件。
限流算法:固定窗口计数器实现最简单,但窗口边界会出现两倍突刺;滑动窗口把统计粒度细化,内存开销随粒度上升;漏桶以固定速率流出,能整形流量但不允许突发;令牌桶按速率放令牌、允许一定突发,是最常用的方案。分布式场景要把计数放到 Redis,用 Lua 保证原子性,并注意时钟漂移与 key 过期。
C++ 与 Java 的最大不同:可以从内存管理(手动与 GC)、运行方式(编译为机器码与字节码加 JIT)、对象模型(值语义与引用语义、多重继承与单继承加接口)、以及生态与工程约束四个角度讲。落到岗位上,重点表达「语言不是障碍,Go 的 goroutine 与 channel 模型、GC 行为我可以很快补上」,并给一个自己跨语言迁移的具体例子。
上下文工程与 harness engineering:上下文工程指在有限窗口内决定「给模型看什么、以什么顺序看、哪些该压缩或丢弃」,包括系统提示、工具定义、检索片段、历史裁剪与结构化输出约束。Harness 指包在模型外面的执行框架:工具调用协议、循环控制、失败重试、权限与沙箱、状态持久化、可观测性。两者关系是「上下文工程决定模型每次看到的世界,harness 决定模型能对这个世界上做什么」。回答时结合自己做过的 Agent 或 AI Coding 实践讲一个具体取舍,比背定义有说服力。