写在前面

本次给大家带来2026年8月22日京东笔试题的2道题，本场机考题目可在咱们平台上在线刷题。

第一题：用校准集算 Conformal 阈值 ，对测试概率构造预测集并映射为 

第二题：用有序集合维护去重后的锚点位置，并动态维护相邻坐标间距的最大值，每次修改只更新受影响的前驱、后继间距，答案为最大间距除以2取整。

大厂笔试AI Coding练习:CodeFun2000.com/aicoder-gym

第1题-检索召回置信集映射

题目内容

制度问答检索侧在上线前，需要对二分类召回结果做置信集输出：模型不确定时允许拒识，以换取更稳的覆盖率。本题在仅使用 numpy / pandas / scikit-learn 的前提下，实现 Split Conformal（分类版）的确定性预测集构造，并将预测集映射为整数标签。

已知：

• 校准集真实标签 ；
• 校准集正类概率 ；
• 测试集正类概率 。

请按以下流程计算：

1) 非一致性分数

对校准集第  个样本，：

• 若 ：
• 若 ：

2) 计算阈值 

固定显著性水平 （目标覆盖率约 ）。

令校准集大小为 ，将  升序排序得 。

若 ，令 。阈值 。

3) 构造预测集 

对测试样本概率 ：

• 类别  纳入当且仅当 
• 类别  纳入当且仅当 

4) 映射为整数

•  → 
•  → 
•  → （不确定 / 拒识）
•  → 

输入描述

标准输入为单行 JSON：

{"cal_y": [0, 1, 0, ...],"cal_p1": [0.12, 0.83, 0.05, ...],"test_p1": [0.20, 0.70, 0.95, ...]}

• cal_y 与 cal_p1 长度相同，校准集长度 ，；
• cal_p1、test_p1 均为  内浮点数；
• test_p1 长度 ，。

输出描述

标准输出仅一行：长度等于 len(test_p1) 的 JSON 整数数组，例如 [0, -1, 1]。

样例1

输入

{"cal_y":[0,0,1,1,0,1,0,1],"cal_p1":[0.08,0.12,0.88,0.92,0.25,0.85,0.15,0.78],"test_p1":[0.0,1.0,0.5,0.18,0.82]}

输出

[0, 1, -2, 0, 1]

说明

校准集 ，，，排序后取 。测试  得 ； 得 ； 两端均不满足得 ； 得 ； 得 。

题解

检索召回置信集映射

解题思路

按 Split Conformal 分类流程：先在校准集上算非一致性分数并取阈值 ，再对测试概率构造预测集并映射整数。

1. 非一致性分数：正类样本 ，负类样本 。
2. **阈值 **：，，若  则 ，（升序后第  个）。
3. 预测集：类别  当 ；类别  当 。
4. 映射：仅 ，仅 ，，。

用 numpy 排序与向量化条件判断即可。

复杂度分析

• 时间复杂度：。
• 空间复杂度：。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

import jsonimport mathimport sysimport numpy as npdefsolve(cal_y, cal_p1, test_p1, alpha=0.2):  cal_y = np.asarray(cal_y, dtype=int)  cal_p1 = np.asarray(cal_p1, dtype=float)  test_p1 = np.asarray(test_p1, dtype=float)# 正类 1-p，负类 p  s = np.where(cal_y == 1, 1.0 - cal_p1, cal_p1)  s_sorted = np.sort(s)  n = len(cal_y)  k = math.ceil((n + 1) * (1 - alpha)) - 1if k >= n:    k = n - 1  q = float(s_sorted[k])  out = []for p in test_p1:    in0 = p <= q    in1 = p >= 1.0 - qif in0 and in1:      out.append(-1)elif in0:      out.append(0)elif in1:      out.append(1)else:      out.append(-2)return outdata = json.loads(sys.stdin.read())result = solve(data["cal_y"], data["cal_p1"], data["test_p1"])sys.stdout.write(json.dumps(result))

第2题-锚点最远盲区

题目内容

产线侧在整数坐标轴上布置了  个温感锚点，编号  到 。第  个锚点当前读数位置为 ，全体位置记为整数数组 。

为衡量锚点覆盖的「最远盲区」，对任意长度  的整数数组 ，定义：

1. 左端 ，右端 。

2. 对每个整数 ，其到最近锚点的距离为

3. 盲区半径定义为这些距离的最大值：

即只在  内的整点  上取最近锚点距离，再取最大。

对读数数组  进行  次修改：每次将  改为 。每次修改后输出当前的 。

输入描述

第一行两个整数 （），分别为锚点数量与修改次数。

第二行  个整数 （），初始位置。

接下来  行，每行两个整数 （，），表示将编号  的锚点位置改为 。

输出描述

输出  行，每行一个整数，为对应修改后的 。

样例1

输入

4 22 5 9 122 74 20

输出

25

说明

初始 distinct 位置 ，相邻半距最大为 ，故 。

第  次将  从  改为 ，相邻间距最大仍为 。

第  次将  改为 ，出现 ，答案为 。

题解

解题思路

将当前所有锚点的位置去重并从小到大排列为

考虑两个相邻锚点 。在它们之间，距离最近锚点最远的整数点位于中间，因此这一段产生的最大距离为

区间的左右端点本身就是锚点，所以不会产生额外距离。因此

也就是说，只需要动态维护所有不同位置之间的最大相邻间距 ，答案就是

注意同一个位置可能存在多个锚点，因此还需要维护每个坐标的出现次数。只有一个坐标的计数从  变为 ，或者从  变为  时，不同坐标集合才真正发生变化。

删除一个不同坐标  时，设它的前驱和后继分别为 ：

• 删除间距 ；
• 删除间距 ；
• 如果  都存在，加入新间距 。

插入一个新坐标  时操作相反：

• 若前驱  和后继  都存在，删除原间距 ；
• 加入  和 。

这就是典型的有序集合加间距多重集合动态维护问题。

 可以直接使用 set 和 multiset，Java 使用 TreeSet 和 TreeMap。

Python 标准库没有平衡树，而所有修改坐标可以提前读入，所以先进行坐标离散化，再用树状数组维护哪些坐标当前存在。通过树状数组的前缀和与第  小查询，可以在  时间找到某个坐标的前驱和后继，其中 。间距最大值使用大根堆，并通过检查两个端点当前是否仍然相邻进行懒删除。

复杂度分析

设所有可能出现的不同坐标数量为 ，有

每次修改只会进行常数次插入、删除、前驱后继查询。

• Python：每次修改时间复杂度为 ，总时间复杂度为 ，空间复杂度为 。
• Java：每次修改时间复杂度为 ，总时间复杂度为 ，空间复杂度为 。
• C++：每次修改时间复杂度为 ，总时间复杂度为 ，空间复杂度为 。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

import sysimport heapq# 树状数组单点修改defadd(bit, x, v):    n = len(bit) - 1while x <= n:        bit[x] += v        x += x & -x# 树状数组前缀和defquery(bit, x):    s = 0while x > 0:        s += bit[x]        x -= x & -xreturn s# 找到树状数组中第 k 个存在的坐标下标defkth(bit, k):    x = 0    step = 1 << (len(bit).bit_length() - 1)while step:        y = x + stepif y < len(bit) and bit[y] < k:            x = y            k -= bit[y]        step >>= 1return x + 1# 求当前坐标下标 p 的前驱和后继defneighbors(bit, p, total):    left_count = query(bit, p - 1)    before_or_equal = query(bit, p)    left = kth(bit, left_count) if left_count > 0else0    right = kth(bit, before_or_equal + 1) if before_or_equal < total else0return left, right# 处理所有修改defsolve(n, u, operations):# 所有可能出现的坐标一起离散化    values = list(u)for _, z in operations:        values.append(z)    coords = sorted(set(values))    mp = {x: i + 1for i, x in enumerate(coords)}    m = len(coords)    cnt = [0] * (m + 1)    bit = [0] * (m + 1)# 大根堆：(-间距, 左端下标, 右端下标)    heap = []# 初始化每个位置的出现次数for x in u:        p = mp[x]        cnt[p] += 1# 初始化树状数组    active = []for i in range(1, m + 1):if cnt[i] > 0:            add(bit, i, 1)            active.append(i)# 初始化相邻间距for i in range(1, len(active)):        l = active[i - 1]        r = active[i]        heapq.heappush(heap, (-(coords[r - 1] - coords[l - 1]), l, r))    total = len(active)defpush_gap(l, r):if l and r:            gap = coords[r - 1] - coords[l - 1]            heapq.heappush(heap, (-gap, l, r))defvalid(l, r):# 两个端点必须存在，并且中间不能还有其他存在坐标if cnt[l] == 0or cnt[r] == 0:returnFalsereturn query(bit, r - 1) - query(bit, l) == 0    ans = []for idx, z in operations:        old = u[idx - 1]if old != z:            p = mp[old]            cnt[p] -= 1# 该坐标彻底消失if cnt[p] == 0:                left, right = neighbors(bit, p, total)                add(bit, p, -1)                total -= 1# 删除 p 后，前驱和后继成为新的相邻点                push_gap(left, right)            q = mp[z]# 新坐标原本不存在if cnt[q] == 0:                left, right = neighbors(bit, q, total)                add(bit, q, 1)                total += 1# 插入后产生两个新的相邻间距                push_gap(left, q)                push_gap(q, right)            cnt[q] += 1            u[idx - 1] = z# 懒删除已经失效的间距while heap:            neg_gap, l, r = heap[0]if valid(l, r):break            heapq.heappop(heap)        max_gap = -heap[0][0] if heap else0        ans.append(str(max_gap // 2))return ansdefmain():    input = sys.stdin.readline    n, t = map(int, input().split())    u = list(map(int, input().split()))    operations = []for _ in range(t):        r, z = map(int, input().split())        operations.append((r, z))    ans = solve(n, u, operations)    sys.stdout.write("\n".join(ans))if __name__ == "__main__":    main()