大厂真题 / 美团

美团 2026-8-25 笔试真题 - 算法岗

本场考试概述

考试时间：2026 年 8 月 25 日

考试岗位：算法岗

难度评级：中等偏难

题型：10 道选择题、1 道编程题、1 道 AI Coding。

考点分析：

选择题：线性回归留一交叉验证、表达式 DAG、多任务学习、散列表、SVM、卷积参数量、双栈求值、SFT、Dropout、递归。
编程题：离散化、树状数组、单点修改、全局统计量的增量维护。
AI Coding：工业时序回归、时间泄漏防范、物理特征、加权 RMSE、分组与时序验证。

一、选择题（10 道）

1. 留一交叉验证

有三个样本点 $(0,1)$、$(1,2)$、$(2,2)$。使用最简单的一元线性回归模型拟合，并采用每折留出一个样本的留一交叉验证。三折预测误差的均方误差是多少？

A. $3/4$
B. $3/2$
C. $1/2$
D. $1/4$

答案：A

解析：每一折用另外两个点确定一条直线。

留出 $(0,1)$：由 $(1,2)$、$(2,2)$ 得 $y=2$，预测误差平方为 $1$。
留出 $(1,2)$：由 $(0,1)$、$(2,2)$ 得 $y=1+0.5x$，预测值为 $1.5$，误差平方为 $0.25$。
留出 $(2,2)$：由 $(0,1)$、$(1,2)$ 得 $y=1+x$，预测值为 $3$，误差平方为 $1$。

所以均方误差为 $(1+0.25+1)/3=3/4$。不能先用全部样本拟合再计算训练误差，那不是留一交叉验证。

2. 表达式 DAG 的最少顶点数

使用有向无环图表示表达式

\[(a*b)*(a*b)*(a*b)*c,\]

其中公共子表达式允许共享，乘法按左结合处理。所需顶点数最少是多少？

A. $11$
B. $13$
C. $7$
D. $3$

答案：C

解析：变量结点为 $a,b,c$，共 $3$ 个。公共子表达式 $ab$ 只建一个结点；随后依次建立 $(ab)(ab)$、再乘一个 $(a*b)$、最后乘 $c$，共 $4$ 个运算结点。因此最少需要 $3+4=7$ 个顶点。

3. 多任务学习中的损失振荡

推荐与搜索共享底座进行多任务预训练，两类任务数据均已清洗。搜索任务损失正常下降，推荐任务损失持续振荡，更可能的根本原因是什么？

A. 推荐任务数据噪声更大
B. 没有使用任务专属 Adapter
C. 共享层学习率过高
D. 两个任务的梯度方向冲突且未解耦

答案：D

解析：共享参数同时接收两个任务的梯度。若梯度内积为负，一个任务的更新会破坏另一个任务刚学到的表示，常表现为强势任务正常收敛、弱势任务反复振荡。PCGrad、GradNorm 或任务权重调整可以缓解该问题。没有 Adapter 并不是必然成因；共享层学习率过高通常会同时影响两个任务。

4. 散列表填装因子

将 $7$ 个关键词装入表长为 $14$ 的散列表，散列函数为 $H(key)=key\bmod 13$。填装因子是多少？

A. $0.8$
B. $1$
C. $0.6$
D. $0.5$

答案：D

解析：填装因子只取决于已装入元素数与表长：

\[\alpha=\frac{7}{14}=0.5.\]

散列函数的模数以及冲突次数都不会改变填装因子。

5. 硬间隔 SVM 的支持向量

一组包含两类、共 $100$ 个样本的数据线性可分。运行带截距项的标准硬间隔 SVM 后得到 $3$ 个支持向量。下列说法错误的是哪一项？

A. 这 $3$ 个支持向量到分离超平面的距离相等
B. 这 $3$ 个支持向量是距离分离超平面最近的样本
C. 删除这 $3$ 个支持向量之外的样本后重新训练，分离超平面保持不变
D. 这 $3$ 个支持向量可能全部属于同一类别

答案：D

解析：硬间隔 SVM 的支持向量位于两侧间隔边界上，到分离超平面的距离均为 $1/\lVert w\rVert$，并决定最大间隔超平面。带截距项的对偶问题满足

\[\sum_i \alpha_i y_i=0.\]

支持向量对应正的 $\alpha_i$。要使上式成立，正负两类都必须至少存在一个支持向量，所以全部支持向量不可能来自同一类别。

6. 卷积层参数量

一个 $3\times3$ 卷积层输入为 $3$ 通道的 $224\times224$ 图像，输出为 $224\times224\times64$，不使用偏置项。该卷积层有多少参数？

A. $50176$
B. $3211264$
C. $1728$
D. $576$

答案：C

解析：卷积参数量与特征图的空间尺寸无关，只取决于卷积核尺寸、输入通道数和输出通道数：

\[3\times3\times3\times64=1728.\]

7. 双栈表达式求值

对表达式

\[6+5*(3*2+1)-9\]

使用操作数栈和运算符栈求值。当扫描到数字 $1$、但尚未把它压入栈时，操作数栈自底向上是什么？

A. 6 5 6
B. 6 5 3 2
C. 6 5 3 2 1
D. 6 5 6 1

答案：A

解析：扫描到括号中的 3*2+ 时，由于 + 的优先级不高于栈顶的 *，需要先计算 $3*2=6$ 并压回操作数栈。此时数字 $1$ 尚未入栈，所以操作数栈为 6 5 6。

8. SFT 中的角色标记与损失掩码

监督微调时没有添加角色边界，也没有做 loss mask，而是对多轮对话整段计算损失。模型上线后经常复述用户的话，更可能的原因是什么？

A. Tokenizer 的特殊符号数量不足
B. 学习率过高导致普通意义上的过拟合
C. 用户文本也被当作生成目标，模型学到了复述整段对话的模式
D. 训练轮数太少，模型尚未自动区分角色

答案：C

解析：标准对话 SFT 通常只对 assistant 段计算损失，user 段作为条件输入而被掩码。若整段都参与损失，模型会被直接训练去预测用户文本，因此更容易在推理时复述输入。

9. Dropout 与推理耗时

在神经网络第 $2$ 层和第 $5$ 层分别增加 Dropout，丢弃率为 $0.2$ 和 $0.3$。原模型平均每条数据推理耗时 $1$ 秒。假设测试时 Dropout 关闭，且不考虑框架调用开销，新模型的平均推理耗时是多少？

A. 等于 $1$ 秒
B. 无法确定
C. 小于 $1$ 秒
D. 大于 $1$ 秒

答案：A

解析：推理模式下 Dropout 退化为恒等映射，不随机丢弃神经元，也不改变原网络层的计算量。在题目明确忽略框架调用开销的条件下，平均耗时保持不变。

10. 汉诺塔递归调用次数

给定以下伪代码，输入 $n=10$，最终输出的 step 是多少？

step = 0

Move(s_pos, e_pos):
    step = step + 1

Hanoi(n, s_pos, t_pos, e_pos):
    if n == 1:
        Move(s_pos, e_pos)
    else:
        Hanoi(n - 1, s_pos, e_pos, t_pos)
        Move(s_pos, e_pos)
        Hanoi(n - 1, t_pos, s_pos, e_pos)

A. $2047$
B. $2048$
C. $1024$
D. $1023$

答案：D

解析：设规模为 $n$ 时调用 Move 的次数为 $T(n)$，则

\[T(1)=1,\qquad T(n)=2T(n-1)+1.\]

解得 $T(n)=2^n-1$，代入 $n=10$ 得 $1023$。

第 1 题：动态维护两两绝对差之和

题目描述

给定长度为 $n$ 的整数数组 $a$，需要依次执行 $m$ 次操作。每次操作基于上一次操作后的数组：

1 i x：把 $a_i$ 修改为 $x$；
2：查询当前所有无序下标对的绝对差之和

\[S(a)=\sum_{1\le i<j\le n}\lvert a_i-a_j\rvert.\]

输入描述

第一行输入测试数据组数 $T$。

每组数据中，第一行输入 $n,m$；第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$；接下来 $m$ 行每行输入一次操作。

数据范围：

\[1\le T\le10^5,\qquad 1\le n,m\le2\times10^5,\] \[\lvert a_i\rvert\le10^9,\qquad \lvert x\rvert\le10^9.\]

所有测试数据中 $n+m$ 的总和不超过 $5\times10^5$。

输出描述

对每次类型 2 的查询输出一行，表示当前数组的两两绝对差之和。

样例 1

输入

输出

样例 2

输入

输出

0
24

思路分析

朴素查询要枚举全部数对，单次需要 $O(n^2)$。但一次单点修改只会改变包含该下标的 $n-1$ 个数对，其余数对的贡献完全不变。因此可以始终维护总答案，只在修改时删除旧值的贡献、加入新值的贡献。

设修改位置从 old 变为 new。先把 old 从当前多重集合中删除，剩下的元素集合记为 $R$。答案更新为

\[S\leftarrow S-f(old)+f(new),\]

其中

\[f(v)=\sum_{u\in R}\lvert v-u\rvert.\]

要快速求 $f(v)$，把元素按是否不超过 $v$ 分成两部分。设 $c_{\le}$、$s_{\le}$ 分别是不超过 $v$ 的元素个数与元素和，$c_{tot}$、$s_{tot}$ 是集合总个数与总和，则

\[f(v)=v\cdot c_{\le}-s_{\le}+(s_{tot}-s_{\le})-v\cdot(c_{tot}-c_{\le}).\]

这只需要“值域前缀个数”和“值域前缀和”。分别使用两棵树状数组维护即可，单点增删和前缀查询都是 $O(\log K)$，其中 $K$ 是离散值数量。

数组值可达 $10^9$，不能直接作为树状数组下标。每组数据先读完全部操作，把初始值和所有修改目标一起排序去重，再做离散化。

初始答案也不需要枚举数对。对排序后的数组从左向右扫描，当前第 $k$ 个元素 value 与前面所有元素的绝对差之和为 k * value - prefix_sum，累加即可。

正确性证明

引理 1：修改 $a_i$ 时，不包含下标 $i$ 的数对贡献保持不变。

证明：这些数对的两个元素都没有被修改，其绝对差自然不变。

引理 2：从集合删除旧值后，$f(v)$ 的计算公式等于 $v$ 与剩余所有元素的绝对差之和。

证明：对 $u\le v$，有 $\lvert v-u\rvert=v-u$，这部分总和为 $v\cdot c_{\le}-s_{\le}$；对 $u>v$，有 $\lvert v-u\rvert=u-v$，这部分总和为 $(s_{tot}-s_{\le})-v\cdot(c_{tot}-c_{\le})$。两部分相加即为全部贡献。

定理：每次查询时，算法维护的 $S$ 等于当前数组所有无序下标对的绝对差之和。

证明：初始 $S$ 由排序扫描准确计算。每次修改时，由引理 1，只需调整包含被修改下标的数对；算法先减去旧值与其余元素的贡献，再加入新值与其余元素的贡献，两项均由引理 2 准确计算。因此修改后不变量仍成立，查询直接输出 $S$ 即为正确答案。

ACM Python 代码

import sys
from bisect import bisect_left


def bit_add(count_bit, sum_bit, index, count_delta, sum_delta):
    size = len(count_bit) - 1
    while index <= size:
        count_bit[index] += count_delta
        sum_bit[index] += sum_delta
        index += index & -index


def bit_prefix(count_bit, sum_bit, index):
    count = 0
    total = 0
    while index > 0:
        count += count_bit[index]
        total += sum_bit[index]
        index -= index & -index
    return count, total


def contribution(count_bit, sum_bit, index, value, total_count, total_sum):
    left_count, left_sum = bit_prefix(count_bit, sum_bit, index)
    left_part = value * left_count - left_sum
    right_part = (total_sum - left_sum) - value * (total_count - left_count)
    return left_part + right_part


def initial_pair_sum(values):
    prefix_sum = 0
    answer = 0
    for index, value in enumerate(sorted(values)):
        answer += index * value - prefix_sum
        prefix_sum += value
    return answer


def solve():
    data = sys.stdin.buffer.read().split()
    cursor = 0
    test_cases = int(data[cursor])
    cursor += 1
    output = []

    for _ in range(test_cases):
        n = int(data[cursor])
        operation_count = int(data[cursor + 1])
        cursor += 2
        values = list(map(int, data[cursor:cursor + n]))
        cursor += n

        operations = []
        all_values = set(values)
        for _ in range(operation_count):
            operation_type = int(data[cursor])
            cursor += 1
            if operation_type == 1:
                index = int(data[cursor])
                new_value = int(data[cursor + 1])
                cursor += 2
                operations.append((index, new_value))
                all_values.add(new_value)
            else:
                operations.append(None)

        coordinates = sorted(all_values)
        size = len(coordinates)
        count_bit = [0] * (size + 1)
        sum_bit = [0] * (size + 1)

        answer = initial_pair_sum(values)
        total_count = n
        total_sum = sum(values)
        for value in values:
            position = bisect_left(coordinates, value) + 1
            bit_add(count_bit, sum_bit, position, 1, value)

        for operation in operations:
            if operation is None:
                output.append(str(answer))
                continue

            index, new_value = operation
            old_value = values[index - 1]
            if old_value == new_value:
                continue

            old_position = bisect_left(coordinates, old_value) + 1
            new_position = bisect_left(coordinates, new_value) + 1

            bit_add(count_bit, sum_bit, old_position, -1, -old_value)
            total_count -= 1
            total_sum -= old_value

            answer -= contribution(
                count_bit, sum_bit, old_position, old_value,
                total_count, total_sum
            )
            answer += contribution(
                count_bit, sum_bit, new_position, new_value,
                total_count, total_sum
            )

            bit_add(count_bit, sum_bit, new_position, 1, new_value)
            total_count += 1
            total_sum += new_value
            values[index - 1] = new_value

    sys.stdout.write("\n".join(output))


if __name__ == "__main__":
    solve()

复杂度分析

设一组数据中参与离散化的不同值数量为 $K$，其中 $K\le n+m$。

时间复杂度：$O((n+m)\log(n+m))$。其中初始排序、离散化和树状数组操作都在该上界内；每次查询为 $O(1)$。

空间复杂度：$O(n+m)$，用于保存操作、离散值和两棵树状数组。

易错点

求和对象是 $i<j$ 的无序下标对，不能把每对计算两次。
修改时必须先删除旧值，再计算旧值和新值相对“其余元素”的贡献。
所有修改目标都要提前加入离散值集合。
相同值可能出现多次，所以既要维护元素个数，也要维护元素和。
答案可能超过 32 位整数范围；Python 可直接处理，其他语言应使用 64 位整数。

AI Coding：风电机组未来功率预测

任务概述

给定风电机组在一个 SCADA 快照时刻已经形成的状态、当前气象观测与短时气象预测，预测未来一小时可安全并网的功率 next_power_mw。提交程序以命令行方式运行：

python main.py --input <csv_path> --output <pred_path>

输出仅包含 record_id,next_power_pred 两列，记录必须与输入一一对应，预测值必须有限，并满足题目定义的容量边界。运行环境为 Python 3.11，可使用 numpy、pandas、scikit-learn，训练与预测需要在给定时间预算内完成。

评价核心为加权 RMSE，并综合考查常规未来周期以及新机型、新区域等泛化场景。以下内容是基于这些约束整理的作答策略，而不是唯一指定方案。

作答策略

1. 先按时间可用性筛选字段

逐字段检查数据字典，确认该值在预测时刻是否已经产生。任何依赖未来一小时结算结果、事后故障判定或未来实测值的字段都应排除，避免时间泄漏。不能只删除标签列后把其余字段全部输入模型。

2. 构造有物理意义的候选特征

可尝试风速平方与立方、风向的正余弦编码、气象预报与当前观测的差值、湍流强度，以及风速与额定容量、可用容量之间的交互。是否保留这些特征，应通过严格的组外验证判断，而不能假定它们一定有效。

3. 让训练目标尽量贴近评价指标

若题目给出了可复现的样本权重公式，可将权重传给支持 sample_weight 的回归器。若只披露了加权方向而没有精确公式，只能把加权训练作为近似策略，不能声称与线上指标完全一致。

4. 面向新机型与新区域验证

随机逐行切分容易让相邻时刻或同一机组的信息同时出现在训练集和验证集。应根据评测场景尝试按时间块、机组或区域分组切分。机组 ID、区域 ID 是否保留也应通过组外验证决定：直接使用可能形成记忆，完全删除也可能损失稳定差异。

5. 建立稳健基线再迭代

在依赖和时间受限的环境中，可先用 HistGradientBoostingRegressor 等 sklearn 模型建立基线，再逐项验证容量归一化、物理特征和样本加权。每轮只改变一个因素，记录离线指标与耗时，避免在有限时间内进行不可解释的堆叠。

6. 最终提交前做机械验收

输出行数必须与输入一致；
record_id 不得重复、缺失或重排；
列名与列顺序必须完全符合要求；
预测值不得出现 NaN 或无穷大；
按题目给定的有效范围裁剪预测值；
固定随机种子，并在干净环境中完整执行一次命令行流程。

小结

选择题覆盖机器学习、深度学习、大模型训练与经典数据结构，需要兼顾计算和概念边界。
编程题的关键是把全局两两绝对差拆成单点贡献，再用两棵树状数组维护值域前缀个数与前缀和。
AI Coding 的优先级应是防止时间泄漏、建立可信验证方式、跑通稳健基线，最后再做特征与模型迭代。

这篇文章有帮助吗？

| GitHub 留言