大厂真题 / 美团
美团算法岗 2026-09-15
本场考试概述
考试时间：2026-09-15
考试岗位：算法岗
难度评级：中等
考点分析：
- 选择题：8 道，涉及磁盘调度、IPv4 子网、参数高效微调、扩展欧几里得、三维并行与 OCR 推理。
- 第一题 叉车往返：周期展开与整数计数（难度中等）。
建议策略：
- 选择题中有多道反向设问，先圈出“不准确”“错误”和“不重新训练”等限定词。
- SSTF 要把同一柱面上的剩余请求视为寻道距离 0；子网题算完地址范围后还要排除网络地址和广播地址。
- 编程题单张工单距离可达 $10^{12}$，不能逐次模拟碰撞；应把折返运动映射到长度 $2H$ 的周期上。
选择题（8 道）
单选题
1、磁头当前停在 38 号柱面，采用最短寻道时间优先（SSTF）。等待请求为：1→30、2→45、3→45、4→58、5→30、6→58、7→90。以下服务顺序符合 SSTF 的是：
A. 2-4-6-3-5-1-7
B. 1-3-2-4-7-6-5
C. 2-3-6-4-1-5-7
D. 3-2-5-4-1-7-6
答案：C
解析：从 38 出发先到距离 7 的柱面 45，并连续服务同柱面的 2、3；再到 58 服务 4、6；随后 30 比 90 更近，最后才到 90。同柱面内的先后不影响寻道距离，因此 C 合法。
2、IPv4 网段 10.40.64.0/19 中，既属于该子网又可分配给普通主机的地址是：
A. 10.40.96.1
B. 10.40.64.0
C. 10.40.95.255
D. 10.40.95.254
答案：D
解析：/19 使第三个字节按 32 为块长。该子网范围是 10.40.64.0 到 10.40.95.255，首地址是网络地址，末地址是广播地址，因此最大可分配地址是 D。
3、全参数微调与 PEFT 相比，哪一项说法不准确：
A. 全参数微调在样本很少时更容易破坏旧能力
B. 多任务共用主干时，PEFT 更容易保持底座参数稳定
C. PEFT 便于一份主干搭配多份任务增量参数部署
D. PEFT 往往更占显存，训练开销也更大
答案：D
解析：PEFT 冻结绝大多数预训练参数，只训练 LoRA、Adapter 等少量参数，梯度和优化器状态也更少，通常比全参数微调节省显存与计算。
4、教务问答模型已经用 PEFT 训练完成，但上线后无法回答新学期选课规则。要以较小代价补充时效性，应优先：
A. 提高 LoRA 秩，但不增加新数据
B. 用新规则样本做小步增量微调，并保留版本隔离和回滚
C. 提高推理温度
D. 只用全部历史数据从头训练
答案：B
解析：问题来自训练数据中没有新规则。增量微调能让模型接触新信息，并通过版本隔离降低发布风险。只增大容量、提高随机性或重复旧数据都不能引入新规则。
5、关于大模型微调，错误的是：
A. Adapter 通过插入小型子网络减少需更新参数
B. Prompt Tuning 冻结原权重，只修改每一层注意力投影矩阵
C. 全参数微调对算力要求高
D. LoRA 用低秩分解表示权重增量
答案：B
解析：Prompt Tuning 训练的是加在输入前的可学习软提示向量，并不修改各层注意力投影矩阵。对投影矩阵加入低秩增量是 LoRA 的常见做法。
6、执行以下扩展欧几里得代码，初始 cnt=0，调用 exgcd(34,21,x,y) 后，cnt 等于：
int exgcd(int a, int b, int* x, int* y) {
if (!b) {
*x = 1;
*y = 0;
cnt += *x;
return a;
}
int d = exgcd(b, a % b, y, x);
*y -= a / b * (*x);
cnt += *x;
return d;
}
A. 1
B. 5
C. -3
D. 0
答案：C
解析：递归参数交换了 x、y 指针。由最深层回溯时，各层累加的 x 依次是 $1,0,1,-1,2,-3,5,-8$，总和为 $-3$。最外层系数为 $x=-8,y=13$，也满足 $34x+21y=1$。
7、关于三维并行训练，错误的是：
A. 张量并行中每台设备都会独立完成整个前向和反向
B. 流水线并行把不同层放到不同设备
C. 数据并行需要在设备间同步梯度
D. ZeRO-3 在数据并行基础上进一步分片参数
答案：A
解析：张量并行把同一层的张量计算切到多台设备，每台只完成一部分，并通过集合通信组合中间结果。每台设备持有完整模型副本并独立前后向是数据并行的特征。
8、景区导览牌 OCR 对手写标注的漏检率较高。在不重新训练的前提下，应优先采用：
A. 加入对抗样本微调模型
B. 把 RGB 转成 YCbCr 并提高亮度
C. 推理阶段使用多尺度滑动窗口扫描可疑区域
D. 修改网络以增大局部注意力感受野
答案：C
解析：手写标注通常是小目标。多尺度滑窗能在不改参数的前提下放大局部区域，提高召回。A 和 D 都需要重新训练；随意更换颜色空间还可能造成输入分布偏移。
第 1 题：叉车往返
题目描述
一台叉车在长度为 $H$ 的直线轨道 $[0,H]$ 上运行。叉车抵达任一端点时会立即发生一次碰撞并掉头。已知初始位置 $p$、朝向 L 或 R，以及依次执行的 $n$ 张工单；第 $i$ 张工单要求它沿当前朝向总共行驶 $x_i$，途中可以多次碰撞掉头。
若初始状态为 $p=0,d=L$，开始前先把朝向修正为 R；若 $p=H,d=R$，修正为 L。这次初始修正不计碰撞。工单距离为 0 时也不发生碰撞。
求执行全部工单后的总碰撞次数、最终位置和最终朝向。
输入描述
第一行是 $n,H,p,d$，满足 $1\le n\le2\times10^5$、$1\le H\le10^9$、$0\le p\le H$，$d$ 为 L 或 R。
第二行是 $n$ 个非负整数 $x_i$，满足 $0\le x_i\le10^{12}$。
输出描述
依次输出总碰撞次数、最终位置和最终朝向，以空格分隔。
样例
输入
4 8 2 L
3 6 10 4
输出
3 5 R
思路分析
第一步：把折返展开成环。 从 0 向右走到 $H$，再向左回到 0，是长度 $2H$ 的一个周期。定义环上坐标：朝右时 $q=p$，朝左时 $q=(2H-p)\bmod 2H$。此后叉车只需在环上沿坐标增大方向前进。
这个映射也自动完成题目的初始朝向修正：0 L 和 0 R 都映射到 0，H R 和 H L 都映射到 $H$。
第二步：用整除统计碰撞。 环上每个 $H$ 的整数倍都对应轨道端点。一次行驶距离 $x$ 时，经过的端点个数是区间 $(q,q+x]$ 中 $H$ 的倍数个数：
\[\left\lfloor\frac{q+x}{H}\right\rfloor- \left\lfloor\frac{q}{H}\right\rfloor\]左开保证起点恰在端点时不重复计数，右闭保证终点恰好到端点时计一次。
第三步：还原位置和方向。 更新 $q=(q+x)\bmod 2H$。若 $q<H$，位置为 $q$、方向为 R；否则位置为 $2H-q$、方向为 L。
正确性说明
映射把轨道上带方向的每个状态一一对应到长度 $2H$ 的周期位置，并把每次直线折返变成环上的单向前进。碰撞恰好发生在展开坐标经过 $H$ 的整数倍时，整除差准确统计了所有且仅有这些倍数。最终按环的前后半段反向映射，因此碰撞次数、位置和朝向都正确。
题解代码
import sys
def solve():
tokens = sys.stdin.buffer.read().split()
n = int(tokens[0])
track_length = int(tokens[1])
position = int(tokens[2])
direction = tokens[3].decode()
distances = map(int, tokens[4:4 + n])
period = 2 * track_length
if direction == "R":
ring_position = position
else:
ring_position = (period - position) % period
collisions = 0
for distance in distances:
collisions += (
(ring_position + distance) // track_length
- ring_position // track_length
)
ring_position = (ring_position + distance) % period
if ring_position < track_length:
position = ring_position
direction = "R"
else:
position = period - ring_position
direction = "L"
print(collisions, position, direction)
solve()
复杂度分析
时间复杂度：$O(n)$，每张工单只做常数次整数运算。
空间复杂度：$O(n)$，输入解析保存了 $n$ 个距离 token；运动状态本身只需 $O(1)$。
易错点
- 工单结束时恰好抵达端点，要计入碰撞，并把朝向改为离开该端点的方向。
- 初始端点上的错误朝向只修正方向，不计碰撞。
- 固定宽度语言需要 64 位整数保存最多约 $2\times10^{17}$ 次碰撞。
小结
- 选择题既考概念，也考 SSTF、子网和递归回溯的手工推演。
- 编程题把折返展开为周期运动后，每张工单都能用整除和取模直接处理。