美团 2026-09-01 笔试真题 - 算法策略岗

本场考试概述

考试时间：2026 年 9 月 1 日

考试岗位：算法策略方向（算法岗）

难度评级：中等偏上

题型说明：原始材料称本场共有 10 道选择题、1 道编程题和 1 道 AI Coding 题，但现有抽取结果只能可靠恢复前 5 道选择题的完整题面。本文仅整理这 5 道，不补写或猜测其余 5 道；编程题和 AI Coding 题各整理 1 道。

可恢复考点：

选择题：岭回归的概率解释、分布式训练性能诊断、Batch Normalization、栈、RNN 与 LSTM。
编程题：无向图欧拉回路、Hierholzer 算法、大规模图的隐式建边。
AI Coding：共享单车需求预测与库存决策、输出合法性、特征泄漏、冷启动和离线运行。

选择题（可恢复 5 道）

选择题 1：岭回归的概率解释

岭回归在概率框架下假定

\[y_i\sim\mathcal N(\beta_0+x_i^\mathsf T\beta,\sigma^2),\]

并且

\[\beta_j\sim\mathcal N(0,\tau^2),\]

则岭回归中的正则化参数 $\lambda$ 为（）。

A. $\displaystyle\frac{\sigma^2}{\tau^2}$
B. 无法确定
C. $\displaystyle\frac{\tau}{\sigma}$
D. $\displaystyle\frac{\tau^2}{\sigma^2}$

答案：A

解析：高斯似然与高斯先验的负对数分别产生

\[\frac{1}{2\sigma^2}\sum_i(y_i-\beta_0-x_i^\mathsf T\beta)^2\]

和

\[\frac{1}{2\tau^2}\sum_j\beta_j^2.\]

整体乘以 $2\sigma^2$ 后，最大后验估计等价于最小化

\[\sum_i(y_i-\beta_0-x_i^\mathsf T\beta)^2+\lambda\lVert\beta\rVert_2^2,\]

其中 $\lambda=\sigma^2/\tau^2$。噪声越大，数据越不可信，正则化应越强；先验方差越大，对参数约束越松，正则化应越弱，也与该结果一致。

选择题 2：分布式训练性能诊断

预训练千亿参数推荐模型时，nvidia-smi 显示 GPU Util = 30%，同时 NVLink/PCIe 出流量饱和。造成这种情况的原因最可能是（）。

A. 数据加载流水线未启用 NVMe SSD 加速
B. 梯度累积步数设置过多
C. 激活函数 GELU 计算未做融合内核优化
D. 张量并行（TP）通信量过大导致带宽饱和

答案：D

解析：GPU 利用率低而卡间互联带宽饱和，说明计算单元主要在等待通信。张量并行会在模型层内频繁同步张量，通信量过大时正会产生这种现象。数据加载瓶颈主要影响磁盘、主机内存到设备的数据通路；梯度累积通常用于降低同步频率；GELU 未融合属于卡内计算与访存问题，都不能同时解释卡间带宽打满。

选择题 3：卷积网络中的 BN

卷积神经网络中，某个 batch 的数据维度为 $[N,C,W,H]$。对其进行 BN（批标准化）时，需要计算均值和方差，则该 batch 中均值和方差的数量分别为（）。

A. $C$
B. $W\times H$
C. $N\times C$
D. $N$

答案：A

解析：卷积网络中的 BN 按通道统计。对每个通道，沿 $N,W,H$ 三个维度汇总 $N\times W\times H$ 个激活值，得到一个均值和一个方差，因此均值与方差各有 $C$ 个。

选择题 4：栈的最小容量

栈 $S$ 和队列 $Q$ 的初始状态均为空。8 个元素 abcdefgh 依次进入队列 $Q$，每个元素出队后立即进入栈 $S$。若 8 个元素的出栈顺序为 bdcfehga，则栈 $S$ 的容量至少为（）。

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

答案：C

解析：元素进入栈的顺序仍为 abcdefgh。先压入 a,b 后弹出 b；再压入 c,d 后依次弹出 d,c；随后对 e,f 和 g,h 做同样操作，最后弹出一直留在栈底的 a。过程中最多同时保存 3 个元素，因此最小容量为 3。

选择题 5：RNN 与 LSTM

下列关于 RNN 与 LSTM 的说法正确的是（）。

A. RNN 主要用于处理图像数据
B. LSTM 的门控结构一般采用 ReLU 作为激活函数
C. LSTM 一共有三个门来控制 cell state
D. RNN 可以很好地处理序列的长期依赖

答案：C

解析：经典 LSTM 包含遗忘门、输入门和输出门，三者共同控制 cell state 的保留、写入与输出。门控通常使用 Sigmoid，将值限制在 0 到 1 之间。普通 RNN 容易出现梯度消失或梯度爆炸，长程依赖正是其短板。

编程题：等分等边三角形

题意

有一个共 $n$ 层的三角形图，第 $i$ 层有 $i$ 个节点。第 $i$ 层的节点编号依次为

\[\frac{i(i-1)}2+1,\ \frac{i(i-1)}2+2,\ \ldots,\ \frac{i(i-1)}2+i.\]

对于所有 $2\le i\le n$ 以及 $1\le j<i$，记

\[u=\frac{i(i-1)}2+j,\]

图中存在以下三条无向边：

$u$ 与 $u+1$ 之间的同层边；
$u$ 与 $\displaystyle\frac{(i-1)(i-2)}2+j$ 之间的斜边；
$u+1$ 与 $\displaystyle\frac{(i-1)(i-2)}2+j$ 之间的斜边。

给定起点 $m$，请从 $m$ 出发，将图中每条边恰好经过一次，最后回到 $m$。题目保证在限制范围内存在解。

图中共有

\[E=\frac{3n(n-1)}2\]

条边，因此需要输出 $E+1$ 个节点。

输入描述

第一行输入整数 $T$，表示测试数据组数，满足

\[1\le T\le 50.\]

接下来 $T$ 行，每行输入两个整数 $n,m$，满足

\[2\le n\le 1000,\qquad 1\le m\le\frac{n(n+1)}2.\]

单个测试文件内所有测试数据的 $n$ 之和不超过 1000。

输出描述

对每组测试数据输出一行，共

\[\frac{3n(n-1)}2+1\]

个整数，表示从 $m$ 出发、遍历每条边恰好一次并回到 $m$ 的路径。若有多个答案，输出任意一个。

样例

输入

2
2 1
3 6

输出

1 2 3 1
6 3 1 2 4 5 3 2 5 6

样例说明：第一组的 3 条边依次为 $(1,2),(2,3),(3,1)$。第二组输出也是一种合法回路；答案不唯一。

思路

题目要求的是无向图的欧拉回路。三角形图连通，塔尖度数为 2，边界点度数为 4，内部点度数为 6，所有节点的度数均为偶数，所以从任意给定起点出发都存在欧拉回路。

使用 Hierholzer 算法：

将起点压入栈。
若栈顶节点还有未使用的边，标记该边并将另一端压栈。
若栈顶节点已没有未使用的边，将其弹出并加入回路。
栈空后，收集到的是逆序回路，将其翻转即可。

直接建立邻接表会为近 150 万条边保存大量 Python 对象。这里利用三角形的规则结构：由节点所在层 $i$ 和层内位置 $j$，最多可以计算出同层左右、上层两个、下层两个共 6 个邻居。

每条边唯一属于一个“尖朝上的小三角形”。将第 $i$ 层的第 $j$ 个小三角形编号为

\[t=\frac{(i-1)(i-2)}2+j-1,\]

再把其底边、左斜边、右斜边依次编码为 $3t,3t+1,3t+2$，即可用字节数组标记边。每个节点再维护一个只增不减的方向指针，避免反复从第一个方向开始扫描。

正确性证明

首先证明算法输出的是闭合路径。图连通且每个节点度数均为偶数。沿未使用边行走时，每到达一个非起点，进入该点会消耗一条边；由于该点原度数为偶数，在它首次无法继续前，一定存在与进入边配对的离开边。因此一次连续行走只可能在起点处闭合。Hierholzer 的栈式过程会把后续发现的闭合子回路自动拼接进已有回路，最终得到以 $m$ 为首尾的闭合路径。

再证明每条边恰好经过一次。算法只有在边标记为未使用时才选择它，并在压入另一端之前立即标记，所以任何边至多经过一次。节点只有在其所有关联边均已使用后才会弹栈；算法结束时起点所在连通分量内不可能还留有未使用边，否则该边的端点不会完成弹栈。整张图连通，因此所有边均被经过，且每条边恰好一次。

最后，隐式生成的 6 类邻接关系逐一对应题面中的底边和两类斜边，统一边号又使同一条无向边从两个端点访问时得到相同标记。因此隐式图与题目定义的图完全一致。综上，算法输出的是题目要求的欧拉回路。

完整 ACM Python

import sys
from array import array


def euler_circuit(n, start):
    vertex_count = n * (n + 1) // 2
    edge_count = 3 * n * (n - 1) // 2

    # used[e] 表示边 e 是否已经走过。
    used = bytearray(edge_count)
    # next_dir[u] 表示节点 u 下一次从哪个方向继续扫描。
    next_dir = bytearray(vertex_count + 1)

    # n <= 1000，层号可以用无符号短整型紧凑保存。
    layer = array('H', [0]) * (vertex_count + 1)
    base = 0
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            layer[base + j] = i
        base += i

    stack = array('I', [start])
    circuit = array('I')

    while stack:
        u = stack[-1]
        i = layer[u]
        j = u - i * (i - 1) // 2

        # 三个可能相关的小三角形的编号。
        up_triangle = (i - 1) * (i - 2) // 2 + j - 1
        left_triangle = up_triangle - 1
        down_triangle = i * (i - 1) // 2 + j - 1

        direction = next_dir[u]
        found = False

        while direction < 6:
            v = 0
            edge_id = -1

            if direction == 0:       # 上层左邻居
                if i > 1 and j > 1:
                    v = u - i
                    edge_id = 3 * left_triangle + 2
            elif direction == 1:     # 上层右邻居
                if i > 1 and j < i:
                    v = u - i + 1
                    edge_id = 3 * up_triangle + 1
            elif direction == 2:     # 同层左邻居
                if j > 1:
                    v = u - 1
                    edge_id = 3 * left_triangle
            elif direction == 3:     # 同层右邻居
                if j < i:
                    v = u + 1
                    edge_id = 3 * up_triangle
            elif direction == 4:     # 下层左邻居
                if i < n:
                    v = u + i
                    edge_id = 3 * down_triangle + 1
            else:                    # 下层右邻居
                if i < n:
                    v = u + i + 1
                    edge_id = 3 * down_triangle + 2

            if v and not used[edge_id]:
                used[edge_id] = 1
                next_dir[u] = direction + 1
                stack.append(v)
                found = True
                break

            direction += 1

        if not found:
            next_dir[u] = 6
            circuit.append(stack.pop())

    circuit.reverse()
    return circuit


def write_path(path):
    # 分块输出，避免一次性创建上百万个字符串对象。
    out = sys.stdout
    chunk = []
    for index, vertex in enumerate(path):
        chunk.append(("" if index == 0 else " ") + str(vertex))
        if len(chunk) == 8192:
            out.write("".join(chunk))
            chunk.clear()
    if chunk:
        out.write("".join(chunk))
    out.write("\n")


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    test_cases = data[0]
    position = 1

    for _ in range(test_cases):
        n = data[position]
        start = data[position + 1]
        position += 2
        write_path(euler_circuit(n, start))


if __name__ == "__main__":
    solve()

复杂度分析

设节点数 $V=n(n+1)/2$，边数 $E=3n(n-1)/2$。

时间复杂度：$O(V+E)=O(n^2)$。每个节点最多检查 6 个方向，每条边仅被选取一次，输出长度也为 $E+1$。

空间复杂度：$O(V+E)=O(n^2)$，用于层号、方向指针、边标记、显式栈和最终回路。

易错点

节点编号从 1 开始，而小三角形编号和边编号从 0 开始，公式中的 -1 不能遗漏。
同一条无向边从两个端点访问时必须映射到同一个 edge_id，否则会被重复遍历。
Hierholzer 在节点无边可走时才记录节点，得到的是逆序结果，输出前需要翻转。
路径必须包含起点和最终返回的起点，共输出 $E+1$ 个节点，而不是 $E$ 个。
数据规模较大，不宜递归，也不宜用嵌套 Python 列表存储完整邻接表。
分块输出时只有整行第一个数字前不能有空格，不能在每个分块开头都重置分隔逻辑。

AI Coding：共享单车站点调拨目标库存

题目概述

实现一个离线批处理程序。程序从工作目录根目录启动，调用方式为：

python3 main.py --input <输入文件路径> --output <输出文件路径>

输入包含多个彼此独立的决策批次，每一行对应“某次决策中的一个站点”。程序需要根据历史运营记录和决策时刻可获得的信息，为每一行给出调拨后的目标车辆数。

评测会在隐藏的真实借还请求上回放该库存方案，综合计算借车失败、还车失败和调拨车辆数带来的成本；三类成本中，借车失败最高，还车失败次之，调拨本身也有成本。隐藏数据可能来自更晚日期、不同天气或活动强度，也可能包含历史中未出现的新站点。

输出契约

输出为 CSV，严格只含示例和字段文档指定的两列：行 ID 与整数目标车辆数；列名及顺序必须与题目示例完全一致。
输出行 ID 必须与输入一一对应：不得为空、重复、缺失或新增；行顺序可以不同。
目标库存必须是有限整数，并落在 $[0,\text{站点容量}]$ 内。
对每个决策批次，所有站点的总调入量不得超过该批次的调拨预算。
不得额外输出索引列或其他字段。
任一批次违反上述约束，该批次不获得业务指标分，因此合法性优先于模型效果。

关键风险

标签泄漏：历史记录同时含决策时字段和服务结束后才产生的结果字段。后者只能构造训练标签，不能作为正式预测特征。
约束遗漏：只在建模中零散裁剪数值，容易漏掉容量、整数、ID 对齐或批次预算中的某一项，导致整批失分。
新站点冷启动：只按站点 ID 查询历史统计，遇到未见站点会失效，应准备全局、区域或相似站点层面的兜底。
分布变化：时间、天气、活动和长期空满站场景都可能偏离训练数据，随机切分得到的本地成绩可能过于乐观。
运行环境：程序必须离线、限时、可复现；不能联网下载模型、安装依赖或读取工作目录外文件，用到随机过程时必须固定种子。

作答策略

先按字段说明明确划分“决策时可用特征”和“事后结果字段”，再开始训练；采用按时间向后切分的验证方式，避免随机切分掩盖时间漂移。
建立稳健基线，例如按时段、工作日类型、天气和区域估计借还需求，再结合容量与当前库存产生连续目标；为新站点逐级回退到区域统计和全局统计。
将借不到车、还不进去和调拨成本的相对权重反映到目标分位数或决策规则中，而不只优化对称预测误差。
编写唯一的输出收尾函数，所有预测路径都必须经过：处理非有限值、取整、裁剪到容量范围，再按批次调整调入量以满足预算，最后核对 ID 集合和列结构。
先运行题目自带样例与自测，再从历史数据切出一段模拟正式输入，逐批检查 ID、整数性、容量边界和调拨预算；对同一输入重复运行，确认结果稳定。
在合法基线之上一次只改一个因素，并分别观察常规日期、分布变化、新站点和长期空满站场景，避免一次性重写导致无法定位退化来源。

小结

原始材料虽称有 10 道选择题，但当前只有 5 道题面可可靠恢复，本文没有杜撰缺失题目。
编程题的核心是把规则三角形视为全偶度连通图，使用 Hierholzer 构造欧拉回路，并通过隐式邻居和统一边编号控制大规模数据下的内存占用。
AI Coding 题应先保证输出契约和批次约束，再优化预测与决策效果，同时防止事后字段泄漏并处理未见站点。

这篇文章有帮助吗？

| GitHub 留言