大厂真题 / OPPO

OPPO 2026-8-22 笔试真题 - 算法岗

本场考试概述

考试时间：2026 年 8 月 22 日

考试岗位：算法岗

难度评级：中等

题型：10 道单选题、2 道编程题。

考点分析：

单选题：堆、Python 生成器、线性代数、SQL 聚合、InnoDB 可重复读、高等数学、上下文管理、Python 可变默认参数、BFS。
编程第 1 题：模意义差分、最长连续等值段。
编程第 2 题：随机子空间、Bootstrap、最近质心、NumPy、投票。

一、单选题（10 道）

1. 最大堆

任务队列用最大堆保存优先级，当前堆里已有 $3$、$8$、$5$。接着依次插入 $6$ 和 $10$，其间没有弹出。下一次从堆顶取出的优先级是多少？

A. $5$
B. $8$
C. $10$
D. $6$

答案：C

解析：最大堆的堆顶恒为当前集合中的最大元素。插入后集合为 ${3,8,5,6,10}$，最大值为 $10$。

2. Python 生成器

执行下面的 Python 代码，打印结果是什么？

squares = (k * k for k in range(4))
view = squares
p = next(squares)
q = next(view)
rest = list(squares)
try:
    tail = next(view)
except StopIteration:
    tail = "end"
print(p, q, rest, tail)

A. 0 0 [1, 4, 9] 1
B. 0 1 [0, 1, 4, 9] end
C. 0 1 [4, 9] end
D. 0 1 [4, 9] 0

答案：C

解析：view = squares 只是给同一个生成器对象增加了一个引用，两者共享迭代进度。前两次 next 依次取出 $0$、$1$，list(squares) 取出余下的 $4$、$9$，之后生成器耗尽。

3. 秩与零空间

线性变换对应矩阵 $A\in\mathbb{R}^{4\times 6}$，且 $\operatorname{rank}(A)=3$。齐次方程 $Ax=0$ 的自由未知量个数，以及解空间一组基里的向量个数，分别是多少？

A. $4$ 个；$3$ 个
B. $3$ 个；$4$ 个
C. $1$ 个；$1$ 个
D. $3$ 个；$3$ 个

答案：D

解析：由秩—零化度定理，

\[\dim\ker(A)=n-\operatorname{rank}(A)=6-3=3.\]

自由未知量个数和零空间一组基中的向量个数均为 $3$。

4. SQL 聚合查询

表 exam_mark 数据如下：

id	kind	point
1	A	92
2	A	78
3	A	85
4	B	81
5	B	73
6	B	90
7	C	88

执行：

SELECT kind, COUNT(*) AS cnt
FROM exam_mark
WHERE point >= 80
GROUP BY kind
HAVING COUNT(*) >= 2
ORDER BY kind;

结果是哪一项？

A. 仅返回 A、B 两组，计数均为 $2$
B. 返回 A、B、C 三组，计数依次为 $2$、$2$、$1$
C. 仅返回 A、B 两组，计数均为 $3$
D. 返回 A、B、C 三组，计数依次为 $3$、$3$、$1$

答案：A

解析：WHERE 先留下 id 为 $1,3,4,6,7$ 的记录，分组计数分别为 A：$2$、B：$2$、C：$1$；HAVING 再剔除 C 组。

5. InnoDB 可重复读

InnoDB 隔离级别为 REPEATABLE READ，账户余额初始为 $200$。事务 T1 第一次普通 SELECT 读到 $200$；随后事务 T2 把余额改成 $250$ 并提交。T1 再执行一次相同的普通 SELECT，接着执行 SELECT ... FOR UPDATE。忽略其他事务，两次分别读到什么？

A. 第二次普通查询得到 $250$，锁定查询也得到 $250$
B. 第二次普通查询得到 $200$，锁定查询得到 $250$
C. 第二次普通查询被阻塞，锁定查询得到 $250$
D. 第二次普通查询得到 $200$，锁定查询也得到 $200$

答案：B

解析：普通 SELECT 是快照读，仍读取事务内 ReadView 对应的 $200$；SELECT ... FOR UPDATE 是当前读，读取最新已提交版本，因此得到 $250$。

6. 函数极值与区间最小值

考查函数

\[f_a(x)=x^3-3ax,\qquad x\in[-1,2],\quad a>0.\]

若它在开区间 $(-1,2)$ 内恰有一个极值点且为极小值点，并且在闭区间上的最小值不小于 $-2\sqrt{2}$，则 $a$ 的范围是？

A. $(0,\sqrt[3]{2}]$
B. $[\sqrt[3]{2},4)$
C. $[1,\sqrt[3]{2}]$
D. $[1,\sqrt[3]{2})$

答案：C

解析：

\[f'(x)=3(x^2-a),\]

驻点为 $x=\pm\sqrt a$，其中 $\sqrt a$ 为极小值点，$-\sqrt a$ 为极大值点。区间内只保留极小值点要求

\[\sqrt a<2,\qquad -\sqrt a\le -1,\]

即 $1\le a<4$。此时最小值为

\[f(\sqrt a)=-2a^{3/2}.\]

由 $-2a^{3/2}\ge-2\sqrt2$ 得 $a\le\sqrt[3]2$，故 $a\in[1,\sqrt[3]2]$。

7. 大模型上下文管理

多轮问答每次都把全部历史拼进提示。对话变长后会逼近上下文上限，早期闲聊还会冲淡当前任务约束。下面哪项更合适作为基础处理？

A. 保留关键事实和约束，摘要相关历史，并裁剪低价值内容
B. 提高生成温度，让模型在长上下文里尝试更多答法
C. 继续追加全部历史，只在超限后截掉最新一轮
D. 把全部历史改写成少量示例，不再保留当前任务的明确约束

答案：A

解析：应原样保留关键事实和约束，压缩相关历史，删除低价值闲聊。调整温度不能解决上下文长度问题，而删除最新信息或当前约束会直接损害任务完成质量。

8. 最小堆插入与删除

最小堆的层序数组为 $[2,5,4,9,7,8]$。先插入 $1$，再删除当前堆顶，并按标准上浮、下沉调整。完成后，堆顶以及它的左、右孩子依次是什么？

A. $2,4,5$
B. $1,5,2$
C. $2,5,4$
D. $4,5,8$

答案：C

解析：插入并上浮后得到 $[1,5,2,9,7,8,4]$。删除堆顶，以末尾的 $4$ 补根并下沉，得到 $[2,5,4,9,7,8]$，前三项为 $2,5,4$。

9. Python 可变默认参数

执行下面的 Python 代码，打印结果是什么？

def push(x, buf=[]):
    buf.append(x)
    return buf

print(push(1), push(2))

A. [1] [2]
B. [1, 2] [1, 2]
C. [1] [1, 2]
D. [1, 2] [2]

答案：B

解析：默认列表在函数定义时只创建一次，两次调用共享同一对象。print 格式化参数时，两次调用均已完成，共享列表已经是 [1, 2]。

10. 无权图最短路

在无权无向图上求从指定起点到其余可达点的最少边数，下列做法最合适的是？

A. 从起点做 DFS，把递归深度直接当作到该点的距离
B. 任选一棵生成树，树上的路径长度就是最短路
C. 用最大堆按节点编号弹出，编号小的点距离更短
D. 从起点做 BFS，第一次到达某点时的层数就是最短距离

答案：D

解析：BFS 按距离逐层扩展，所以第一次到达节点时的层数就是从起点出发的最少边数。

二、编程题

第 1 题：最长匀差脉冲

题目描述

航标站记录了 $p$ 个读数 $x_1,x_2,\ldots,x_p$，每个读数都是模 $K$ 意义下的非负整数。相邻两次脉冲的前向变化量定义为

\[(x_{i+1}-x_i)\bmod K.\]

若一段连续读数中每一对相邻读数的变化量都相同，就称其为一段匀差脉冲。求最长的匀差脉冲；若有多段长度相同，取起始下标最小的一段。只有一个读数时也视为一段，公共变化量记为 $0$。

输入描述

第一行输入两个整数 $p,K$，其中

\[1\le p\le 200000,\qquad 2\le K\le 10^9.\]

第二行输入 $p$ 个整数 $x_1,x_2,\ldots,x_p$。所有输入均为整数。

输出描述

输出三个整数：最长匀差脉冲的长度、左端点下标（从 $1$ 开始）及公共变化量。

样例 1

输入

5 10
0 2 4 7 0

输出

3 1 2

前三个读数的变化量均为 $2$；后三个读数在模 $10$ 下的变化量均为 $3$。两段等长，取起点更小的一段。

样例 2

输入

1 5
3

输出

1 1 0

样例 3

输入

6 9
2 2 2 5 8 2

输出

4 3 3

思路分析

构造差分序列

\[d_i=(x_{i+1}-x_i)\bmod K,\qquad 1\le i<p.\]

读数中的匀差段恰好对应差分序列中的连续等值段。若差分等值段长度为 $L$，则对应读数段长度为 $L+1$。从左向右扫描，只有当前段严格更长时才更新答案，便能在等长时保留最早出现的区间。

当 $p=1$ 时差分序列为空，直接按约定输出 1 1 0。

正确性说明

差分定义逐项等价于题目规定的模 $K$ 前向变化量，因此一段读数是匀差脉冲，当且仅当它对应的差分子段全部相等。扫描会枚举每个极大连续等值段并记录最长者；严格大于才更新又保证等长时保留最小起点。因此输出的长度、起点及公共变化量均正确。

ACM Python 代码

import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    p, mod = data[0], data[1]
    values = data[2:2 + p]

    if p == 1:
        print(1, 1, 0)
        return

    diff = [(values[i + 1] - values[i]) % mod for i in range(p - 1)]
    best_len = 1
    best_start = 0
    current_start = 0

    for i in range(1, p - 1):
        if diff[i] != diff[i - 1]:
            current_start = i
        current_len = i - current_start + 1
        if current_len > best_len:
            best_len = current_len
            best_start = current_start

    print(best_len + 1, best_start + 1, diff[best_start])


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(p)$。

空间复杂度：$O(p)$。

易错点

差值必须在模 $m$ 意义下计算，直接相减会在读数回绕处断开等差段。
多个最长段并列时取起点更小者，扫描时只能在严格变长时更新答案。
单个读数也构成长度为 $1$ 的合法区间，其公差按题意输出为 $0$。

第 2 题：抽检子空间质心投票

题目描述

给定训练特征 $X\in\mathbb{R}^{n\times d}$ 和非负整数标签 $y$，用 $T$ 个基分类器对测试集分类。输入还给出每个分类器使用的特征数 $m$ 和随机种子 seed。只能使用 numpy、pandas、scikit-learn，并且必须使用：

rg = np.random.RandomState(seed)

构造每个基分类器时，严格依次执行：

有放回抽袋：调用 rg.randint(0, n, size=n) 得到训练样本下标。
无放回抽特征：调用 rg.choice(d, size=m, replace=False)，并将抽出的特征下标升序保存。
最近质心分类：在该袋样本和特征子集上，对每个类别 $c$ 计算质心 $\mu_c$。测试点 $z$ 的预测为

\[\arg\min_c\|z-\mu_c\|_2^2.\]

距离相同时取类别编号较小者。

若某个类别在该袋中一次都没有抽到，不能删除该类别，而要使用完整训练集中该类别在相同特征子集上的全局质心。

全部基分类器各投一票，最终选择票数最多的类别；票数并列时同样取较小的类别编号。

输入描述

标准输入为一行 JSON，对象字段如下：

{
  "train": [[f11, f12, ..., y1], [f21, f22, ..., y2]],
  "test": [[g11, g12, ...], [g21, g22, ...]],
  "n_estimators": 5,
  "max_features": 1,
  "seed": 42
}

train 为二维列表，每行最后一列是标签，其余列是特征；
test 只包含特征；
n_estimators 是基分类器数 $T$；
max_features 是每袋抽取的特征数 $m$；
标签为非负整数；
训练条数与测试条数均在 $[2,19]$ 内；
$1\le d\le9$，$1\le m\le d$。

输出描述

只输出一个紧凑 JSON 对象：

{"features":[[1],[0],[0]],"bootstraps":[[2,3,0,2],[3,0,0,2],[2,2,2,2]],"pred":[0,1,0]}

features：每个基分类器使用的升序特征下标；
bootstraps：每个基分类器的抽袋下标，保持随机抽取顺序；
pred：测试集的最终预测。

样例 1

输入

{"train":[[1,0,0],[2,0,0],[0,4,1],[0,5,1]],"test":[[1,0],[0,4],[1,2]],"n_estimators":2,"max_features":1,"seed":7}

输出

{"features":[[0],[0]],"bootstraps":[[3,0,1,2],[3,3,3,0]],"pred":[0,1,0]}

样例 2

输入

{"train":[[0,0,0],[1,0,0],[0,1,1],[8,8,2]],"test":[[0,0],[8,8]],"n_estimators":4,"max_features":2,"seed":1}

输出

{"features":[[0,1],[0,1],[0,1],[0,1]],"bootstraps":[[1,3,0,0],[1,3,1,3],[0,1,0,3],[0,2,1,2]],"pred":[0,2]}

样例 3

输入

{"train":[[3,1,0,0],[3,2,0,0],[1,3,1,1],[1,4,1,1],[9,9,9,2]],"test":[[3,1,0],[1,3,1],[9,9,9]],"n_estimators":3,"max_features":2,"seed":13}

输出

{"features":[[1,2],[0,1],[1,2]],"bootstraps":[[2,0,2,0,2],[4,2,3,2,4],[2,1,3,4,2]],"pred":[0,1,2]}

思路分析

全程只创建一个 RandomState，每轮必须先抽样本、后抽特征，否则随机数流会变化。先将类别编号升序排列，并预计算各类别在完整特征空间中的全局质心。

每轮按袋内样本计算各类别在所选子空间中的均值；袋内缺失的类别则切出对应全局质心。对所有测试点向量化计算平方欧氏距离。由于类别编号有序，argmin 首值语义自然实现距离并列取小编号；同理，票箱上的 argmax 实现票数并列取小编号。

正确性说明

每轮抽袋和抽特征严格复现题面指定的随机调用顺序。对袋内存在的类别，代码使用袋内均值；对缺失类别，使用完整训练集的全局均值，故质心定义正确。平方欧氏距离与欧氏距离具有相同的大小关系，argmin 得到最近质心；升序类别数组保证距离并列取小编号。最终逐测试点统计全部票数并用相同规则取最大值，所以最终预测正确。

ACM Python 代码

import json
import sys

import numpy as np


def solve():
    case = json.loads(sys.stdin.buffer.readline())
    train = np.asarray(case["train"], dtype=float)
    x_train = train[:, :-1]
    labels = train[:, -1].astype(int)
    x_test = np.asarray(case["test"], dtype=float)

    n_estimators = case["n_estimators"]
    max_features = case["max_features"]
    n_samples, n_dims = x_train.shape

    classes = np.unique(labels)
    n_classes = len(classes)
    global_centers = np.stack([
        x_train[labels == class_id].mean(axis=0)
        for class_id in classes
    ])

    rg = np.random.RandomState(case["seed"])
    all_features = []
    all_bootstraps = []
    votes = np.zeros((len(x_test), n_classes), dtype=int)

    for _ in range(n_estimators):
        bag_rows = rg.randint(0, n_samples, size=n_samples)
        feature_ids = np.sort(
            rg.choice(n_dims, size=max_features, replace=False)
        )

        bag_x = x_train[bag_rows][:, feature_ids]
        bag_y = labels[bag_rows]
        centers = np.empty((n_classes, max_features), dtype=float)

        for slot, class_id in enumerate(classes):
            mask = bag_y == class_id
            if mask.any():
                centers[slot] = bag_x[mask].mean(axis=0)
            else:
                centers[slot] = global_centers[slot, feature_ids]

        gaps = x_test[:, feature_ids][:, None, :] - centers[None, :, :]
        squared_distances = np.einsum("qcm,qcm->qc", gaps, gaps)
        winners = squared_distances.argmin(axis=1)
        votes[np.arange(len(x_test)), winners] += 1

        all_features.append([int(value) for value in feature_ids])
        all_bootstraps.append([int(value) for value in bag_rows])

    prediction_slots = votes.argmax(axis=1)
    predictions = [int(classes[slot]) for slot in prediction_slots]
    answer = {
        "features": all_features,
        "bootstraps": all_bootstraps,
        "pred": predictions,
    }
    sys.stdout.write(json.dumps(answer, separators=(",", ":")))


if __name__ == "__main__":
    solve()

复杂度分析

设测试样本数为 $q$、类别数为 $C$。

时间复杂度：$O\bigl(T(Cn+nm+qCm)\bigr)$。

空间复杂度：$O(nd+qCm+T(n+m))$，其中最后一项用于保存并输出每个基分类器的抽袋下标和特征下标。

易错点

每轮必须先调用 randint 抽袋，再调用 choice 抽特征。
特征下标需要排序，抽袋下标不能排序。
袋内缺失的类别不能删除，必须改用该类别的全局质心。
距离并列和票数并列都取较小类别编号。
输出必须是紧凑 JSON，不能混入日志或解释文字。

这篇文章有帮助吗？

| GitHub 留言