面试官是做 Kafka / streaming infrastructure 的工程师，风格非常明显：
不急着让你写代码，也不追求“第一分钟就给最优解”，而是不断通过 follow-up 把问题推向真实系统。
面试一开始：一个“看起来很干净”的数据结构题
面试官开场就给了一个问题，大概意思是：
系统里会不断插入 key → value，每个 key 插入时都有时间戳。
有一个固定的过期时间窗口（expiry time）。
现在你要支持一个操作：
getAverage()
返回当前所有 还没过期 的 value 的平均值。
他特意补了一句：
getAverage 会被频繁调用。
这一句其实已经在埋雷了。
第一轮思路：时间顺序 + 滑动窗口
我先确认了基本假设：
key 和 value 都是整数，expiry 是固定的，过期数据不参与计算。
然后给出一个直觉上很合理的方案：
- 用一个 HashMap 存 key → value
- 再用一个按插入时间顺序的队列，存
(key, timestamp, value) - 同时维护两个变量：
- 当前未过期 value 的 sum
- 当前未过期 key 的 count
每次 getAverage() 之前，从队列头开始清理过期 key。
因为是按时间顺序插入的，只要第一个没过期，后面都安全。
清理完之后，直接 sum / count。
面试官没有接着往下，而是盯住了复杂度
他没有说“好”或者“不好”，而是问：
你这个 getAverage，复杂度是多少？
我如实回答：
单次最坏是 O(n)，但每个 key 只会被清理一次，所以从长期来看是 摊销 O(1)。
他继续追问：
n 是什么？
为什么你觉得这是 amortized O(1)？
我解释了 sliding window 的直觉：
慢的那一次，其实是在把之前积攒的过期数据一次性处理掉，之后队列会变短。
这一步，面试官是认可的，但他明显还没打算停。
第一个关键 follow-up：访问会不会刷新时间？
就在我以为这道题要结束的时候，他突然加了一个条件：
如果我们再加一个 API：
get(key)
一旦这个 key 被访问，就刷新它的时间戳。
这一句话，直接让原方案露出了问题。
我当场意识到：队列不够用了
如果访问会刷新时间，那意味着：
- key 可能在时间队列的中间
- 我需要把它“挪”到最新的位置
而普通队列 / deque 删除中间元素是 O(n)。
我没有硬拗，而是直接承认：
这个需求下，原结构不合适了。
面试官这时才慢慢引导到“真正的解法”
我给出的改进是：
- HashMap：key → node
- 双向链表：按时间顺序维护
- 头是最老
- 尾是最新
这样的话：
- put 是 O(1)
- get(key) 并刷新时间是 O(1)
- 过期清理只从头部开始
- getAverage 依然是摊销 O(1)
我当时说了一句总结性的话：
这题本质上是一个
带统计信息的 LRU / Sliding Window 结构。
面试官点头，这一题正式结束。
后面几道题，节奏明显加快，但思路是一致的：
给你一个问题 → 看你第一反应 → 看你是否能在真实约束下调整设计。
多层链表 Flatten
接下来是一个 多层链表 flatten 的问题：
节点除了 next，还有一个 down 指针。
要求把所有 down 链表插入到父节点和父节点原本的 next 之间，最终变成一条普通链表。
这里面试官明显更关心的是：
- 你是否能保证节点顺序
- 你是否意识到递归深度的问题
- 你会不会一开始就假设“层数不深”
我提到了递归和显式栈两种方案，也顺带聊到了在真实系统里如何避免过深递归。
CSV 文件递归遍历
接下来是一道偏工程的题：
给一个目录，递归遍历所有 CSV 文件，把第二列的整数全部加起来。
Bus Tracker / Station Distance：建模能力
给一条单向站点链路和若干公交车当前位置，
问从某个站点往前，最近的公交还有多少站。
Calendar Busy View
最后是一道区间合并题：
给一堆事件时间段，输出合并后的 busy time。
典型排序 + 合并，但面试官会非常敏感：
- 边界是否算重叠
- 是否处理相邻区间
- 输出是否有序
整个过程中，面试官会不断穿插一些问题，比如：
- 如果这是线上系统，你最担心什么？
- 你有没有遇到过设计假设被流量打脸的情况？
- 你是更偏快速落地，还是一开始就想清楚？
- 你有没有在不该你扛的时候扛过太多？
