大厂真题 / 蚂蚁

蚂蚁 4.9 笔试真题 - 算法岗

本场考试概述

考试时间：2026年4月9日 考试岗位：算法岗 难度评级：中等偏难

考点分析：

第一题：贪心（难度简单）
第二题：HMM Viterbi 动态规划（难度困难）
第三题：质因数分解 + DFS 枚举（难度中等）

建议策略：

第一题是送分题，关键是发现运算对值的单调性，快速拿下
第二题是 ML 编程题，需要熟悉 HMM 模型和 NumPy 向量化实现
第三题数论基础扎实的同学应该能顺利解出

第一题：穿过黑暗之门

题目描述

初始权值为 1。经历 n 关，每关有两扇门，通过时权值做对应运算（+x、-x、*x、/x 向下取整）。权值始终限制在 [1, 10^9] 范围内（超出则截断）。求穿过所有关卡后的最大权值。

样例

输入

3
+ 10 * 2
* 2 / 5
- 5 / 2

输出

思路分析

第一步：观察题目性质

四种运算 +、-、*、/（正整数参数）有一个共同性质：当前权值越大，运算后的权值一定不会更小。加法和乘法显然如此；减法和除法虽然让值变小，但起点越高结果也越高（例如 100-5=95 > 50-5=45）。截断操作也不破坏这个单调性。

第二步：贪心策略

由于单调性成立，每一关只需选让当前值更大的那扇门。当前值越大，未来无论怎么选都不会更差，因此贪心策略全局最优。

题解代码

import sys
input = sys.stdin.readline

def apply_op(v, op, x):
    if op == '+':
        v += x
    elif op == '-':
        v -= x
    elif op == '*':
        v *= x
    else:
        v //= x
    return max(1, min(v, 10**9))

n = int(input())
v = 1
for _ in range(n):
    parts = input().split()
    op1, x1, op2, x2 = parts[0], int(parts[1]), parts[2], int(parts[3])
    v = max(apply_op(v, op1, x1), apply_op(v, op2, x2))
print(v)

复杂度分析

时间复杂度：O(n)，每关常数次运算。 空间复杂度：O(1)。

第二题：离散型马尔可夫模型预测

题目描述

在仅使用 NumPy 的前提下，实现隐马尔可夫模型（HMM）的 Viterbi 动态规划解码。给定初始分布 pi、状态转移矩阵 A、观测概率矩阵 B 和多条离散观测序列，为每条序列计算最优隐藏状态序列和对数概率。

要求在对数域计算避免下溢，输出对数概率保留 6 位小数。

样例

输入

{"pi":[0.6,0.4],"A":[[0.7,0.3],[0.4,0.6]],"B":[[0.5,0.4,0.1],[0.1,0.3,0.6]],"obs":[[0,0]]}

输出

{"paths": [[0, 0]], "logp": [-2.253795]}

思路分析

第一步：理解 HMM 与 Viterbi

隐马尔可夫模型描述”隐藏状态序列产生观测信号”的过程。Viterbi 算法是一个 T 步、N 状态的 DP：定义 delta[t][j] 为”到时刻 t、处于状态 j 的最优路径概率”，每步从 N 个前驱状态中选概率最大的转移过来。

第二步：对数域计算

概率连乘会导致浮点下溢，取对数后乘法变加法。递推式变为 delta[t][j] = max_i(delta[t-1][i] + logA[i][j]) + logB[j][obs[t]]。

第三步：NumPy 向量化

将 delta[t-1] 扩展为列向量，与 logA 矩阵相加得到得分矩阵，沿 axis=0 取 argmax 和 max 即可一次性算出所有状态的最优前驱和累积对数概率。

题解代码

import json
import numpy as np

def viterbi(log_pi, log_A, log_B, obs_list):
    N = len(log_pi)
    paths = []
    logps = []

    for obs in obs_list:
        T = len(obs)
        delta = np.full((T, N), -np.inf)
        psi = np.zeros((T, N), dtype=int)

        # 初始化
        delta[0] = log_pi + log_B[:, obs[0]]

        # 递推
        for t in range(1, T):
            scores = delta[t - 1, :, None] + log_A
            psi[t] = np.argmax(scores, axis=0)
            delta[t] = np.max(scores, axis=0) + log_B[:, obs[t]]

        # 回溯
        path = [0] * T
        path[T - 1] = int(np.argmax(delta[T - 1]))
        best_logp = float(delta[T - 1, path[T - 1]])
        for t in range(T - 2, -1, -1):
            path[t] = int(psi[t + 1, path[t + 1]])

        paths.append(path)
        logps.append(round(best_logp, 6))

    return paths, logps

data = json.loads(input())
pi = np.array(data["pi"], dtype=np.float64)
A = np.array(data["A"], dtype=np.float64)
B = np.array(data["B"], dtype=np.float64)
obs_list = [list(map(int, seq)) for seq in data["obs"]]

log_pi = np.log(pi)
log_A = np.log(A)
log_B = np.log(B)

p, l = viterbi(log_pi, log_A, log_B, obs_list)
print(json.dumps({"paths": p, "logp": l}))

复杂度分析

时间复杂度：O(T * N^2 * Q)，T 为序列长度，N 为状态数，Q 为序列条数。 空间复杂度：O(T * N)，存储 delta 和 psi 矩阵。

第三题：公倍数对和

题目描述

给定正整数 x，找到正整数三元组 (a, b, c) 使得 lcm(a, b, c) = x 且 a + b + c 最小。

样例

输入

输出

思路分析

第一步：观察题目性质

a, b, c 都必须是 x 的因子，且对 x 的每个质因子 p^e，三者中至少有一个在 p 上取到指数 e（否则 lcm 在 p 上的指数不够）。

第二步：问题转化

把 x 分解为 p1^e1 * p2^e2 * …，每个质因子的指数分配互不影响。对质因子 p_i，枚举 a, b, c 在该因子上的指数 (i, j, k)，约束 max(i, j, k) = e_i。各质因子的幂次独立相乘，因此可以逐质因子 DFS 搜索最小和。

第三步：DFS + 剪枝

初始时 a=b=c=1，上界为 x+2（对应最差方案 (1,1,x)）。对第 idx 个质因子，枚举三个指数中满足”最大值等于 e”的所有组合，将 a, b, c 分别乘以 p^指数后递归。当 a+b+c 已超过当前最优解时直接剪枝。

题解代码

import sys
input = sys.stdin.readline

def factorize(x):
    factors = []
    d = 2
    while d * d <= x:
        if x % d == 0:
            e = 0
            while x % d == 0:
                e += 1
                x //= d
            factors.append((d, e))
        d += 1
    if x > 1:
        factors.append((x, 1))
    return factors

def solve(x):
    if x == 1:
        return 3
    factors = factorize(x)
    # 预计算每个质因子的所有幂次
    pw = [[p ** i for i in range(e + 1)] for p, e in factors]
    best = [x + 2]

    def dfs(idx, a, b, c):
        if a + b + c >= best[0]:
            return
        if idx == len(factors):
            best[0] = a + b + c
            return
        _, e = factors[idx]
        for i in range(e + 1):
            for j in range(e + 1):
                for k in range(e + 1):
                    if max(i, j, k) != e:
                        continue
                    dfs(idx + 1, a * pw[idx][i], b * pw[idx][j], c * pw[idx][k])

    dfs(0, 1, 1, 1)
    return best[0]

cache = {}
T = int(input())
for _ in range(T):
    x = int(input())
    if x not in cache:
        cache[x] = solve(x)
    print(cache[x])

复杂度分析

时间复杂度：单次查询 O(sqrt(x)) 分解质因数，DFS 搜索空间在剪枝下极小；多次查询通过缓存均摊。 空间复杂度：O(log x)，用于存储质因数列表和幂次数组。

小结

第一题贪心，四种运算对权值具有单调性，每关选更大结果即全局最优
第二题 HMM Viterbi 是 ML 编程题，对数域 DP 避免下溢，NumPy 向量化实现高效解码
第三题质因数分解 + DFS 枚举，按质因子独立分配指数，剪枝后搜索空间极小

这篇文章有帮助吗？

| GitHub 留言