面试了一个某为员工，连归并排序都写不出来会 就一道leetcode中等难度的题都做不出，拜拜吧
python约 3 分钟有人说自己面了个“某为”员工，结果一道 LeetCode 中等题没做出来，归并排序也写不顺，当场就给判死刑了：拜拜吧。
我看完倒不是替谁洗，算法不会当然会扣分，面试嘛，你考啥人家就得接啥。但把“某为员工”四个字拎出来嘲，就有点意思了。大厂员工也不是统一流水线下来的，每个人做的东西不一样。有的人天天写业务、有的人搞工程落地、有的人可能几年都碰不到手撕排序。
更关键的是，面试考算法没问题，但别考完一道题就觉得自己看穿人家全部水平。真干活的时候，能不能定位问题、拆需求、扛线上事故、跟一堆乱七八糟的人沟通，这些也挺要命的。
当然了，归并排序都写不出来，确实尴尬。
员工薪水表一查，最容易写歪的地方不是累加，是“最新月份不要算”。
这题我第一眼会先盯两个点： 每个员工单独算； 每个员工最后一个月要排除掉。
数据大概长这样：
# id, month, salary
rows = [
(1, 1, 20),
(1, 2, 30),
(1, 3, 40),
(1, 4, 60),
(2, 1, 15),
(2, 2, 25),
(2, 4, 35),
]
要查的是每个员工最近三个月的累计薪水，但这里的“最近三个月”不是全公司最近三个月，而是站在员工每一条记录的 month 往前看三个月。
比如员工 1 的 4 月是最新月份，不能输出。 3 月要算 1、2、3 月：20 + 30 + 40 = 90。 2 月算 1、2 月：50。 1 月算自己：20。
这种题不要上来就双重循环。数据一多，写得很热闹，跑得很难看。
我一般会先按员工分组，再在每个员工内部按月份排序，用一个小窗口往前滑。窗口里只保留当前月份往前数 2 个月的数据。
from collections import defaultdict, deque
defquery_cumulative_salary(records):
emp_months = defaultdict(list)
for emp_id, month, salary in records:
emp_months[emp_id].append((month, salary))
ans = []
for emp_id, items in emp_months.items():
items.sort(key=lambda x: x[0])
last_month = items[-1][0]
window = deque()
window_sum = 0
for month, salary in items:
window.append((month, salary))
window_sum += salary
while window and window[0][0] < month - 2:
_, old_salary = window.popleft()
window_sum -= old_salary
if month == last_month:
continue
ans.append((emp_id, month, window_sum))
ans.sort(key=lambda x: (x[0], -x[1]))
return ans
跑一下：
print(query_cumulative_salary(rows))
输出：
[
(1, 3, 90),
(1, 2, 50),
(1, 1, 20),
(2, 2, 40),
(2, 1, 15)
]
这里有个坑，员工 2 没有 3 月记录，4 月又是他的最新月份，所以 4 月不输出。2 月只累加 1 月和 2 月，不要脑补一个不存在的 3 月。
窗口这段是关键：
while window and window[0][0] < month - 2:
_, old_salary = window.popleft()
window_sum -= old_salary
当前是 5 月，就只允许窗口里有 3、4、5 月。2 月的数据必须弹出去。 当前是 2 月，就允许 0、1、2 月，实际只有 1、2 月，那就算已有的。
这题如果放到数据库里，很多人会用自连接或者窗口函数。用 Python 写的时候，思路其实一样：先把数据按员工隔离，再按月份推进，不要让不同员工的数据串进一个窗口。
最后复杂度也比较干净。每条记录进窗口一次、出窗口一次，排序之外就是线性扫描。比那种“每一条都回头扫三个月”的写法稳得多。