2026 京东秋招算法工程师-机器学习岗：笔试

1. 前言

这周投了京东的 2026 秋招 JDS，投的是算法工程师-机器学习岗，笔试的试卷是大算法笔试卷，一共 2 个小时。这个大算法笔试试卷一共 30 个选择题和 2 个编程题，一共 100 分。这两个部分是分开的，如果选择题部分提交了，就不能够后续修改了，编程题提交了还能继续修改（笔者就手滑把提交当成了调试）。

选择题考的主要是 SQL、概率论、算法、机器学习和深度学习的内容。对于有 SQL 题这一回事挺无语的，本来研究生期间就没时间准备 SQL 的内容，还考 SQL 题，花了我 1 小时左右。

编程题总体上难度称不上高，但是涉及到的参数很多，有时候老忘记符号对应的参数，导致花了很多时间在调试上。写这两道编程题只有 50 分钟不到的时间，审题就得花个 5 ~ 10 分钟，外加输入输出调试，基本没留几分钟给我做，最后随便弄了一下解决战斗。

2. 第一题

问题描述：

某宠物收容所有 n 只宠物，这些宠物每一只都有两种毛色，第 i 只宠物的第一种毛色为 ai，第二种毛色为 bi。另外根据收容时长，收容所赋予了每个宠物唯一的 “领养编号” xi，可理解为领养优先级，编号越小优先级越高。近期收容所开放了宠物领养活动。共有 m 个领养人依次来到收容所，每个领养人都有一个偏好的毛色，记为 ci。领养人只会领养第一种毛色或第二种毛色中至少一种是他们偏好毛色的宠物。如果收容所剩余的宠物中有当前领养人偏好的宠物，则他会选择符合要求的宠物中领养编号最小的那一只宠物领养结束后（或放弃领养），下一位领养人才会来到收容所进行领养。如果没有心仪的宠物（或已经没有剩余的宠物）则会放弃领养。只有当前一位领养人领养宠物的情况结束后，下一位领养人才会进行领养。领养活动结束后，收容所想要了解每个领养人领养宠物的情况，请你帮助他们进行统计。

输入格式：

1. n：初始宠物数量。
2. xi 列表：每只宠物的领养编号。
3. ai 列表：每只宠物的第一种毛色。
4. bi 列表：每只宠物的第二种毛色。
5. m：领养人数量。
6. ci 列表：每个领养人的偏好毛色。

其中，1 ≤ xi ≤ 10^9，1 ≤ ai, bi, ci ≤ 3，1 ≤ n ≤ 30000，1 ≤ m ≤ 100000

输出格式：

一行 m 个数，表示每个领养人领养的宠物的领养编号（或 -1）

示例：

输入：

4
25 10 5 40
1 2 3 2
3 1 2 2
5
2 1 3 2 1

输出：

5 10 25 40 -1

解题思路：

1. 数据结构选择：

• 我们需要高效地查询和删除当前剩余宠物中，满足 ai == ci 或 bi == ci 的宠物中 xi 最小的那个。
• 对于每个毛色，维护一个最小堆，存储当前剩余宠物中 ai == ci 或 bi == ci 的宠物的 xi 和索引。每次查询时，从对应的堆中取出最小的 xi，但需要检查该宠物是否已被领养（即是否已被删除）。
  2. 具体步骤：
• 初始化三个最小堆（对应毛色1、2、3），每个堆中存储 (xi, index) 对，其中 index 是宠物的原始索引。
• 对于每个毛色 c，将满足 ai == c 或 bi == c 的宠物加入堆 c。
• 对于每个领养人 ci：
  • 检查堆 ci 是否为空：
    • 如果为空，输出 -1。
    • 否则，取出堆顶的最小 xi，检查对应的宠物是否已被领养（需要一个标记数组 adopted）。
    • 如果未被领养，标记为已领养，输出 xi。
    • 如果已被领养，继续弹出堆顶直到找到一个未被领养的宠物或堆为空。
  • 注意：由于宠物可能同时满足多个毛色，因此需要从所有相关的堆中移除该宠物（或延迟删除）。

Python 实现代码：

import heapq
import sys

input = sys.stdin.read().split()
ptr = 0

n = int(input[ptr])
ptr += 1

x = list(map(int, input[ptr:ptr+n]))
ptr += n

a = list(map(int, input[ptr:ptr+n]))
ptr += n

b = list(map(int, input[ptr:ptr+n]))
ptr += n

m = int(input[ptr])
ptr += 1

c = list(map(int, input[ptr:ptr+m]))
ptr += m

# 初始化三个堆，分别对应毛色 1, 2, 3
heaps = [[] for _ in range(4)]  
adopted = [False] * n

# 构建特征维度特征
for idx in range(n):
    xi, ai, bi = x[idx], a[idx], b[idx]
    heapq.heappush(heaps[ai], (xi, idx))
    if bi != ai:
        heapq.heappush(heaps[bi], (xi, idx))

res = []
for ci in c:
    found = -1
    # 弹出已失效元素
    while heaps[ci]:
        xi, idx = heapq.heappop(heaps[ci])
        if not adopted[idx]:
            adopted[idx] = True
            found = xi
            break
    res.append(found if found != -1 else -1)

print(' '.join([str(i) for i in res]))

后记：

这题笔者在做的时候，第一时间没看见题目要求 “他会选择符合要求的宠物中领养编号最小的那一只宠物”，导致笔者一开始想得过于简单了，以为是顺序选取，结果发现自己想的和题目要求的不一样。最后随便写了几个迭代了事，发现 Python 超时了 35 ms，也挺难受的。

3. 第二题

问题描述：

在一个无向图 G 中，独立匹配是图中的一个边集 X，满足以下两个条件：X 中任意两条边不共享端点；任何一条不属于 X 的边，至多与 X 中的边共享一个顶点 。现在给出一个无向图和其中的一些边集，请你判断这些边集中哪一些是独立匹配。

输入格式：

第一行有两个正整数 n, m（1 < n ≤ 1000，1 ≤ m ≤ 2000），代表图中的点数和边数。 接下来的两行给出了一个 2×m 的矩阵，矩阵中的每一列都代表图中的一条边的两个端点。保证图中没有自环（即不存在一条边其两个端点相同）。 接下来的一行中有一个正整数 q（1 ≤ q ≤ 30），代表询问的边集个数。 接下来 q 行，每行开头有一个正整数 c（代表询问的边集大小），然后是 c 个 1 到 m 之间的正整数（含 1 和 m），代表询问的边集中边的编号。数字间两两有空格隔开。

输出格式：

对每个询问，输出一行一个字符串 YES 或 NO，表示该边集是否为独立匹配。

示例：

输入：

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

输出：

No
No
Yes

解题思路：

1. 将边存储为元组列表，方便后续访问。
2. 匹配性检查：用布尔数组记录每个顶点是否被边集中的边占用。
   • 遍历边集中的每条边 (u, v)
   • 检查两个端点是否都未被占用：if used[u] or used[v]
   • 如果任一端点已被占用，说明存在共享端点，违反匹配性
   • 否则标记这两个端点为已占用：used[u] = used[v] = True
3. 独立性检查：检查所有不在边集中的边是否违反独立性条件。
   • 遍历所有边（包括在边集和不在边集中的）
   • 对于不在边集中的边，检查其两个端点：
     • 如果两个端点都被边集占用（used[u] and used[v] 都为 True）
     • 说明这条边与边集中的两条边都共享端点，违反独立性

Python 实现代码：

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
edge_u = list(map(int, input().split()))
edge_v = list(map(int, input().split()))

# 存储所有边
edges = [(edge_u[i], edge_v[i]) for i in range(m)]

q = int(input())
for _ in range(q):
    data = list(map(int, input().split()))
    c = data[0]
    S = set(data[1:])  # 查询的边编号集合（1-based）

    used = [False] * (n + 1)  # 顶点占用标记

    ok = True
    # 匹配性检查：边集中的任意两条边不共享端点
    for idx in S:
        u, v = edges[idx - 1]
        if used[u] or used[v]:
            ok = False
            break
        used[u] = used[v] = True

    # 独立性检查：任何一条不属于边集的边，至多与边集中的边共享一个顶点
    if ok:
        for i in range(1, m + 1):
            if i in S:
                continue
            u, v = edges[i - 1]
            if used[u] and used[v]:
                ok = False
                break

    print("Yes" if ok else "No")

后记：

笔者在做这题时只剩 15 分钟了，导致没有能够及时做出来。这题并不是很难，主要是考察图，没有用到什么特殊的数据结构，挺遗憾的。