360 笔试 10.10

《面试题目》

1. 笔试整体：2 小时，40 道选择题 + 2 道编程题；选择题范围很广，操作系统、大模型、Python 线程、元组、数据库都有，单选里还混了一些多选题。
2. 编程题一：给出 A、B、C、D 四个数字，通过它们可以构建一个无限长的序列，构建公式为 a[i] = (a[i-1] * b * c + c) % d，求这个序列的 MEX 值。
3. 编程题二：给出 a、b、s 三个参数表示打车的花费——耗时小于等于 s 只需付本金 a，超时需要加钱，总花费是 a + b * (x - s)；再给出 N 段路和 N-1 个红灯的耗时，保证每次重新打车不耗费时间，且 a > b * s 因此不存在无限重新打车的情况。问如何打车做到花费最小。

《参考解析》

这场笔试的构成与做题节奏。 两小时里 40 道选择题加 2 道编程题，时间并不宽裕，所以选择题不能恋战。范围横跨操作系统、大模型、Python 线程与元组、数据库，说明它考的是「计算机基础面」而不是某个方向深度；最容易踩的坑是单选题里混进了多选题——题干里「以下正确的是」与「以下正确的有」含义完全不同，前者单选、后者多选，读题时先确认问法再落笔，否则会在选项数量上被扣分。编程题两道都不算难，属于「想清楚就能一次写对」的类型，值得先花两分钟把边界条件写在纸上。

编程题一：取模递推序列的 MEX。 MEX 的定义是序列中没有出现过的最小非负整数，所以解题分两步：把序列生成出来并记录出现过的值，再从 0 开始往上找第一个没出现过的数。关键在于「无限长序列」不能真的无限生成——递推式 a[i] = (a[i-1] * b * c + c) % d 中，a[i] 完全由 a[i-1] 决定，取值只可能落在 [0, d) 这个有限集合里，因此状态最多 d 种，一旦出现曾经出现过的值，后续必然进入循环，再往后不会产生新值，此时可以停止生成。实现上用哈希表或布尔数组记录见过哪些值，生成到首次重复即退出，然后从 0 开始扫到第一个未记录的值就是 MEX。复杂度是 O(d) 时间与 O(d) 空间。两个容易翻车的细节：一是乘法 b * c 以及乘上 a[i-1] 后可能超出 32 位整数范围，要用 64 位甚至更大类型再取模；二是初值与下标起点要严格按题面给的定义来（a[0] 与 a[1] 用哪一个递推是按题面写的），不要凭习惯改动，否则首个元素错了后面全错。

编程题二：红灯处分段重新打车的贪心。 先把费用模型写清楚：一次打车从上车到下车，若总耗时 x 不超过 s，只付 a；超过 s 的部分按 b 每分钟加钱，即单段费用为 a + b * max(0, x - s)。中途重新打一辆车，等于把当前这一段结算掉、并从此刻起开一段新的计时，重新打车本身不消耗时间。条件 a > b * s 的作用是给出边界保证：等待超过 s 后每分钟只增加 b，而重新打一次要多付一次本金 a，所以「重打」的收益是有限的，不会出现无限重打反而更便宜的退化情形。策略是在每个红灯处做局部比较：算出「继续坐原车等完这个红灯」之后这一段的总花费，以及「此刻重新打车」的总花费（当前段结算 + 新段从零开始计时），哪个更小就选哪个。这个贪心可以这样论证：整个行程只能在红灯处切分，于是问题等价于「选择若干个切分点，使各段费用之和最小」；单段费用是分段线性的凸函数，越往后延长的边际成本只会在 b 与 b 之间变化（一旦超过 s 就是常数斜率 b），而重打的边际收益固定，因此最优切分点具有单调性与局部可比性，逐点取更优者即得全局最优。原帖作者自己也怀疑过会不会是次优，验证方式很简单：写一版 O(n²) 的动态规划（f[i] 表示到达第 i 个红灯的最小花费，枚举上一段起点）与小数据暴力对比，跑几百组随机用例就能确认贪心是否成立——面试或笔试里如果时间够，用「小数据对拍」来验证贪心，比空想更有说服力。

平台操作上的坑。 这场笔试在赛码平台进行，提交时必须先把测试用例窗口关掉才算真正提交，否则切到下一题会自动提交，等于把没写完的代码交上去；做编程题时建议养成「先在本地或草稿确认样例通过，再关闭用例窗口提交，最后才切换题目」的顺序。另外 40 道选择题里如果出现自己完全没听过的方向（比如大模型相关），不要在单题上纠结超过一分钟，先把能拿的分拿稳，再回头处理不确定的题。