大厂真题 / 京东
京东 2026-9-26 笔试真题 - 算法岗
本场考试概述
考试时间：2026年9月26日
考试岗位：算法岗
难度评级：中等
本页收录两道具有完整题意、约束和样例的编程题。另有一道“毕业资格复核”AI Coding 工程题，但缺少完整接口契约、实体字段和配套工程，本页不将其补写成可提交题目，也不虚构接口或测试数据。
考点分析：
- 第一题：DBSCAN 核心点、边界点与噪声点的区别；NumPy 广播和布尔矩阵。
- 第二题：镜面反射、状态图的唯一前驱、从边界入口遍历互不相交的链。
建议策略：先完成规则明确的第一题，注意邻域包含自身与半径边界；第二题先证明轨迹结构，再写模拟，避免对每个起点重复遍历。
第 1 题：DBSCAN 点类型判定
题目描述
给定 $n$ 个 $d$ 维样本，邻域半径 eps 和最小样本数 min_samples。不需要求聚类簇编号，只需输出每个点的类型：核心点为 2，边界点为 1，噪声点为 0。
点 $i$ 的邻域包含所有与它的欧氏距离不超过 eps 的点，包含点自身。若邻域点数不少于 min_samples，该点是核心点；否则，如果它位于至少一个核心点的邻域内，就是边界点；剩余点为噪声点。边界点不能像核心点一样继续扩张邻域。
输入一行 JSON，字段 X 为样本矩阵，eps 为正浮点数，min_samples 为不小于 $1$ 的整数。约束为 $1<n<20$、$0<d<10$。
输出一行长度为 $n$ 的 JSON 整数数组，元素间保留空格。数值计算只允许使用 NumPy、pandas 或 scikit-learn；下面使用 NumPy，标准库负责输入输出与 JSON 解析。
样例
输入
{"X":[[0,0],[0,0.1],[0.1,0],[5,5]],"eps":0.2,"min_samples":3}
输出
[2, 2, 2, 0]
思路分析
第一步：把邻域关系表示成矩阵。
类型判定只依赖两点是否相邻，无须执行完整的 DBSCAN 聚类。计算
\[D_{ij}=\sum_{k=1}^{d}(X_{ik}-X_{jk})^2,\]再令 $A_{ij}$ 表示 $D_{ij}\le\mathrm{eps}^2$。比较平方距离可避免开平方，不能把 <= 改成 <，也不应擅自引入容差改变题目规则。矩阵对角线为真，自身已经计算在邻域内，不要额外加一。
第二步：先确定全部核心点。
矩阵每行的真值数量就是对应点的邻域大小。把行和与 min_samples 比较，得到核心点掩码。样例的前三个点互相相邻，每个都有三个邻居，因此均为核心点。
第三步：只检查核心点对应的列。
对于非核心点，如果它所在行在某个核心点列上为真，就应输出边界点。欧氏距离对称，因此“它靠近某个核心点”与“它落在核心点邻域里”等价。必须先判核心，再判边界，不能把同时邻近其他核心点的核心点降级。
当没有核心点时，取出的矩阵有零列，NumPy 的 any(axis=1) 为每一行返回假，因此自然全部输出噪声点。当 min_samples=1 时，所有点都因自身而成为核心点。最终用 tolist() 转为 Python 整数列表，再由 json.dumps 生成规定格式。
题解代码
import sys
import json
import numpy as np
def classify_points(x, eps, min_samples):
diff = x[:, None, :] - x[None, :, :]
adjacent = np.sum(diff * diff, axis=2) <= eps * eps
core = adjacent.sum(axis=1) >= min_samples
near_core = adjacent[:, core].any(axis=1)
types = np.zeros(len(x), dtype=int)
types[near_core & ~core] = 1
types[core] = 2
return types.tolist()
def solve():
data = json.loads(sys.stdin.readline())
x = np.asarray(data["X"], dtype=float)
result = classify_points(x, float(data["eps"]), int(data["min_samples"]))
print(json.dumps(result))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(n^2d)$，枚举所有点对并计算各维度差值，后续布尔运算不超过 $O(n^2)$。
空间复杂度：$O(n^2d)$，主要为广播得到的三维差值张量。
第 2 题：镜子实验室
题目描述
实验室是 $n$ 行 $m$ 列的网格，每格为 .、/ 或 \。从每个格子分别向上、右、下、左发射光线，共有 $4nm$ 种起始条件。
每一步，光线先在当前格子反射，再沿新方向移动一格：
.：方向不变。/：上与右互换，下与左互换。\：上与左互换，下与右互换。
离开网格即成功逃离；光线也可能永远在网格中循环。起始位置或起始方向不同就视为不同光线，求最终能逃离的光线数量。
第一行是测试组数 $T$，满足 $1\le T\le100$。每组先输入 $n,m$，再输入 $n$ 行长度为 $m$ 的网格。满足 $n,m\ge1$、$nm\le10^6$，所有测试组的 $nm$ 之和不超过 $10^6$。每组输出一个整数。
样例
输入
2
2 3
...
...
2 2
/\
\/
输出
24
8
思路分析
第一步：把格子和方向一起作为状态。
一个状态是“位于某格、尚未处理该格镜子的运动方向”。这恰好对应一种起始光线，共 $4nm$ 个状态。每个状态的后继唯一；逐束模拟虽然直接，但会反复走过相同路径，最坏达到平方级工作量。
第二步：证明前驱也至多一个。
如果光线以方向 $d$ 进入某格，那么前一格只能是沿 $d$ 反方向退一格的位置。在前一格中，空地及两种镜面的方向映射都是双射，所以反射前方向也唯一。若前一格位于网格外，该状态没有内部前驱。
因此状态图中，每个点的入度和出度都不超过一。有限图的每个连通部分只能是链或环：环上的光线永不逃离；链的末端一定离开网格。链不可能汇入环，否则汇入点会有两个前驱。
第三步：从没有前驱的状态开始走。
所有链的起点恰好是边界入口：第一行向下、最后一行向上、第一列向右、最后一列向左。枚举这些入口，沿反射规则一直走到出口。每访问一个状态，就找到一种能够逃离的起始条件，累加访问次数即可。
各条链不共享状态，也不会进入环，所以不需要访问标记或判环集合。注意统计的是链上的状态数，不是入口数量。单行、单列或角上的同一个格子会出现多个入口，但方向不同，对应不同状态，不重复计数。
第四步：用一圈哨兵简化边界。
将方向依次编码为 $0,1,2,3$（上、右、下、左），反射用查表完成。把网格存为一维字节数组，四周补值为 3 的哨兵；走到哨兵就结束。实际格子的编码为 0、1、2。入口用生成器逐个产生，不额外保存整个入口列表。
样例第一组没有镜子，所有状态均逃离。第二组既有外侧链，也有内部循环；只遍历边界链便会得到答案 8，不会陷入内部循环。
题解代码
import sys
TURN = ((0, 1, 2, 3), (1, 0, 3, 2), (3, 2, 1, 0))
TRANS = bytes.maketrans(b"./\\", bytes((0, 1, 2)))
def boundary_starts(n, m, width):
for col in range(1, m + 1):
yield width + col, 2
yield n * width + col, 0
for row in range(1, n + 1):
yield row * width + 1, 1
yield row * width + m, 3
def count_escape(n, m, rows):
width = m + 2
grid = bytearray([3]) * width
for row in rows:
grid.append(3)
grid.extend(row.translate(TRANS))
grid.append(3)
grid.extend(bytearray([3]) * width)
steps = (-width, 1, width, -1)
total = 0
for pos, direction in boundary_starts(n, m, width):
while grid[pos] != 3:
direction = TURN[grid[pos]][direction]
pos += steps[direction]
total += 1
return total
def solve():
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
rows = (input().strip() for _ in range(n))
print(count_escape(n, m, rows))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(nm)$，各条链互不相交，总访问次数不超过 $4nm$，建立网格也为线性开销。
空间复杂度：$O(nm)$，保存带边框的网格；入口和输入行均逐个产生。
小结
- DBSCAN 点类型判定不需要构造完整聚类；邻域矩阵、核心掩码和邻近核心的判断已经足够。
- 镜面网格不能只看“后继唯一”，还要利用“前驱唯一”，才能证明从边界入口出发的路径互不相交且不会进入环。
- 工程题只有业务概述而缺少完整契约时，不应自行填补字段或接口，把猜测包装成完整真题。