面灵AI→

今日头条后端暑期实习一面:LRU 加过期、两栈队列与断点续传由谁决定分片

轮次
一面
时间
2026-11
来源
牛客网

《面试题目》

  1. 算法:实现 LRU 缓存,并支持「x 秒后自动过期」。
  2. 算法:用两个栈模拟队列,先写暴力解法,再优化。
  3. SQL 题:select * from 表 where a < 1 and b > 1 and c = 1,如何优化?
  4. 了解索引下推吗?
  5. HTTP 请求的数据结构是什么样的?
  6. 讲讲断点续传,每次传输的数据大小是服务端决定还是客户端决定?
  7. 简历追问:为什么从 WXG 离职?实习之后有什么感受?实习中最大的收获是什么?
  8. 还了解哪些限流算法?
  9. 为什么做开源?提过哪些 PR?
  10. 我们这边是 Go,对语言有要求吗?你觉得 C++ 和 Java 最大的不同是什么?
  11. 你觉得自己的沟通能力怎么样?
  12. AI Coding 方面有哪些经验?
  13. 讲讲上下文工程?讲讲 harness engineering?
  14. 现在是大三吗?有读研打算吗?办公地点在深圳可以吗?
  15. 反问环节。

《参考解析》

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 实践讲一个具体取舍,比背定义有说服力。