大厂真题 / 京东

京东 2026-8-8 笔试真题 - 数据分析岗

本场考试概述

考试时间：2026 年 8 月 8 日

考试岗位：数据分析岗

难度评级：中等

考点分析：

• 第 1 题：分界值判定与贪心构造（中等）
• 第 2 题：单败淘汰树、重排论证与快速幂（中等偏难）
• 第 3 题：SQL 条件聚合与分组过滤（中等）

建议策略：

• 第 1 题先把“剔除最高的 $k$ 件”转化成两组数之间的分界约束，再构造答案。
• 第 2 题只要求达到最大概率的编排数量，不必计算最大概率本身。
• 第 3 题要区分“异常任务数量”和“少检数量”两个统计口径。

第 1 题：等级序列还原

题目描述

产线质检得到 $n$ 件工件的质量评级序列 $v_1,v_2,\ldots,v_n$，每件评级为 $1$ 至 $6$ 之间的整数，评级总和为 $S$。

随后，评级最高的 $k$ 件工件被召回重测；若边界处存在相同评级，可从中任取，使召回数量恰为 $k$。召回后剩余 $n-k$ 件工件的评级总和为 $R$。

已知 $1\le k<n$。请根据 $n,k,S,R$ 还原任意一组合法的原始评级序列；若无解，输出 -1。

输入描述

一行输入四个整数 $n,k,S,R$：

• $2\le n\le 2\times10^5$；
• $1\le k<n$；
• $1\le R<S\le1.2\times10^6$。

输出描述

若有解，输出一行 $n$ 个整数，表示任意一组合法评级序列；否则输出 -1。

样例 1

输入

4 2 15 5

输出

1 4 4 6

总和为 $15$，剔除最高的 $4$ 和 $6$ 后，剩余评级之和为 $1+4=5$。

样例 2

输入

3 1 10 2

输出

-1

被召回工件的评级之和应为 $10-2=8$，但单件评级最多为 $6$，因此无解。

思路分析

记召回部分的评级和为

留下的工件数为 $m=n-k$。

将完整序列升序排列，前 $m$ 件留下，后 $k$ 件召回。设召回部分的最小评级为 $b$，则所有留下的评级都不能超过 $b$，否则该工件也应进入最高的 $k$ 件。

召回部分由 $k$ 个 $[b,6]$ 内的整数构成，因此必须满足

留下部分由 $m$ 个 $[1,b]$ 内的整数构成，因此必须满足

$b$ 越大，留下部分越容易容纳总和 $R$。召回部分允许的最大分界值为

所以直接检查这个最大的 $b$ 即可：

1. 若 $T<k$、$T>6k$ 或 $R<m$，无解；
2. 计算 $b$，若 $R>bm$，无解；
3. 构造 $m$ 个 $[1,b]$ 内、和为 $R$ 的数；
4. 设留下部分最大值为 $M$，再构造 $k$ 个 $[M,6]$ 内、和为 $T$ 的数。

构造一组定长、定和且每项位于 $[lo,hi]$ 的整数时，可以从左到右决定每一项。若当前项之后还剩 rest 项，则后面最多承载 rest * hi，当前项至少要取

正确性证明

引理 1：若存在合法序列，则 $k\le T\le6k$、$m\le R$ 且 $R\le m\lfloor T/k\rfloor$。

证明：召回的 $k$ 件评级均在 $[1,6]$，故 $k\le T\le6k$；留下的 $m$ 件评级至少为 $1$，故 $R\ge m$。设留下部分最大评级为 $M$。召回部分每件评级都不小于 $M$，所以 $kM\le T$，即 $M\le\lfloor T/k\rfloor$。留下部分总和不超过 $mM$，因此 $R\le m\lfloor T/k\rfloor$。引理得证。

引理 2：若算法通过所有可行性检查，则能构造出合法序列。

证明：由 $m\le R\le bm$，可构造 $m$ 个 $[1,b]$ 内、和为 $R$ 的整数。设其最大值为 $M$，则 $M\le b\le\lfloor T/k\rfloor$，所以 $kM\le T$；又有 $T\le6k$，因此可构造 $k$ 个 $[M,6]$ 内、和为 $T$ 的整数。召回部分每个数都不小于留下部分任意一个数，故它们可以作为最高的 $k$ 件；两部分总和分别为 $R$ 与 $T$，完整序列总和为 $S$。引理得证。

定理：算法输出 -1 当且仅当无解；否则输出合法评级序列。

证明：引理 1 说明算法拒绝的条件均为必要条件；引理 2 说明通过检查时一定能完成构造。因此算法正确。定理得证。

ACM Python 代码

import sys


MAX_RATING = 6


def append_values(answer, count, total, lower, upper):
    for index in range(count):
        remaining_count = count - index - 1
        value = max(lower, total - remaining_count * upper)
        answer.append(value)
        total -= value


def solve():
    n, k, total_sum, remaining_sum = map(int, sys.stdin.buffer.readline().split())
    removed_sum = total_sum - remaining_sum
    remaining_count = n - k

    if (
        removed_sum < k
        or removed_sum > MAX_RATING * k
        or remaining_sum < remaining_count
    ):
        print(-1)
        return

    boundary = min(MAX_RATING, removed_sum // k)
    if remaining_sum > boundary * remaining_count:
        print(-1)
        return

    answer = []
    append_values(answer, remaining_count, remaining_sum, 1, boundary)
    append_values(answer, k, removed_sum, answer[-1], MAX_RATING)
    print(*answer)


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(n)$，构造并输出 $n$ 个评级。

空间复杂度：$O(n)$，用于保存答案序列。

易错点

• 分界处允许相等，不需要强制“召回部分严格大于留下部分”。
• 仅检查两部分各自能否凑出总和还不够，还要保证召回部分不低于留下部分。
• 题目保证 $1\le k<n$，因此留下部分非空，代码中的 answer[-1] 安全。

第 2 题：单败淘汰赛概率

题目描述

有 $2^m$ 个候选方案参加单败淘汰评审，编号为 $1$ 到 $2^m$。若编号为 $i$ 的方案与编号为 $j$ 的方案对比，则方案 $i$ 胜出的概率为

所有方案按初始编排顺序放入一棵完整的单败淘汰树。首轮相邻两个位置配对，之后每轮将上一轮胜者按所在对局顺序继续两两配对，直到产生冠军。

不同的初始编排是 $1$ 到 $2^m$ 的不同排列。求有多少种初始编排能使方案 $1$ 最终夺冠的概率达到最大值，答案对 $998244353$ 取模。

输入描述

一行输入整数 $m$，满足 $1\le m\le12$。

输出描述

输出达到最大夺冠概率的初始编排数量，对 $998244353$ 取模。

样例 1

输入

2

输出

8

样例 2

输入

3

输出

128

思路分析

方案 $1$ 要连续赢下 $m$ 轮。它在第 $r$ 轮面对的对手，来自一棵包含 $2^{r-1}$ 个方案的兄弟子树。因此除方案 $1$ 外的方案被分成大小为

的互不相交块。

这些兄弟子树的比赛相互独立。若第 $r$ 块最终胜者为随机变量 $W_r$，则方案 $1$ 夺冠概率可写为

对淘汰树进行标准的交换论证：若两个子树所含编号交错，把较小编号集中到较早、规模较小的兄弟块，并在每个子树中递归地把较小一半与较大一半分开，不会降低上式；由于编号互不相同，存在交错时会严格改善。不断消除交错后，唯一的无序最优结构为：

并且每个块内部都按连续区间的左右两半递归划分。也就是说，忽略每场比赛左右位置的区别，最优淘汰树唯一。

下面只需统计这棵树能对应多少个叶子排列。一棵有 $2^m$ 个叶子的满二叉树共有

个内部结点。每个内部结点的左右子树都可以独立交换，交换不会改变任何一场对局及其概率，只会改变初始排列。不同交换组合产生不同排列，因此答案为

指数最大为 $4095$，使用快速幂即可。

正确性证明

引理 1：忽略左右顺序后，最优淘汰树唯一，且每个结点都把其连续编号集合划分为较小一半和较大一半。

证明：方案 $1$ 的夺冠概率可分解为各兄弟子树贡献的乘积。对任意两个交错子树，将较小编号向更早、规模更小的子树集中，再递归地消除子树内部交错。将两种安排的概率通分后，其差可以分解为编号差与正数项的乘积，因此消除交错不会降低概率；编号均不同，存在交错时差值严格为正。反复交换直至无法改进，只能得到按连续区间分块、每块递归二分的结构，故该无序结构唯一。引理得证。

引理 2：这棵唯一的无序最优树对应 $2^{2^m-1}$ 个不同初始排列。

证明：满二叉树有 $2^m-1$ 个内部结点，每个内部结点均可独立交换左右子树。交换不改变对局关系，所以仍然最优。左右子树含有互不相同且非空的编号集合，因此任意两个不同的交换方案都会产生不同叶序。故排列数为 $2^{2^m-1}$。引理得证。

定理：算法输出达到最大夺冠概率的初始编排数量。

证明：由引理 1，所有最优编排都来自唯一无序最优树；由引理 2，该树恰好对应 $2^{2^m-1}$ 个编排。算法计算该值对模数的余数，因此正确。定理得证。

ACM Python 代码

import sys


MOD = 998244353


def solve():
    m = int(sys.stdin.buffer.readline())
    internal_nodes = (1 << m) - 1
    print(pow(2, internal_nodes, MOD))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(m)$，快速幂执行 $O(\log(2^m-1))=O(m)$ 次迭代。

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

易错点

• 答案统计的是初始排列，不是忽略左右顺序后的淘汰树数量。
• 指数是 $2^m-1$，不是 $m-1$ 或 $2^m$。
• 应使用模意义下的快速幂，不能先计算完整的指数幂。

第 3 题：产线质检异常批次统计

题目描述

产线质检系统记录了生产批次和对应的抽检任务。请统计 2026 年 10 月 1 日存在质检异常的生产批次，只输出至少包含一项异常任务的批次。

异常任务满足以下任一条件：

• 抽检状态不是 PASS；
• 实际抽检数量少于计划抽检数量。

返回字段及顺序固定为：

• prod_line：产线编码；
• batch_id：批次 ID；
• task_cnt：该批次任务总数；
• abnormal_cnt：异常任务数量；
• shortfall：所有少检任务的缺少数量之和。

排序规则依次为：abnormal_cnt 降序、shortfall 降序、prod_line 升序、batch_id 升序。

表结构

c21_jd_inspection_batches：

c21_jd_inspection_tasks：

样例

输入

c21_jd_inspection_batches:
(201, A01, 2026-10-01)
(202, A01, 2026-10-01)
(203, B01, 2026-10-01)
(204, A01, 2026-09-30)

c21_jd_inspection_tasks:
(1, 201, 12, 12, PASS)
(2, 201, 9, 4, PASS)
(3, 201, 7, 7, TODO)
(4, 202, 6, 6, PASS)
(5, 202, 5, 5, PASS)
(6, 203, 10, 2, TODO)
(7, 203, 8, 8, PASS)

输出

prod_line batch_id task_cnt abnormal_cnt shortfall
A01       201      3        2            5
B01       203      2        1            8

思路分析

先按 batch_id 关联批次表和任务表，再在 WHERE 中筛选目标日期。三个统计指标分别处理：

• task_cnt 使用 COUNT(*)；
• abnormal_cnt 对“状态不是 PASS 或发生少检”做条件求和；
• shortfall 仅在 actual_cnt < plan_cnt 时累加差值，否则贡献 0。

注意，状态异常但数量达标的任务会增加 abnormal_cnt，但不会增加 shortfall；状态为 PASS 但发生少检的任务则会同时影响两个指标。因此两个 CASE WHEN 不能共用同一个条件。

聚合后用 HAVING 过滤 abnormal_cnt >= 1 的批次，最后按题目给出的四级规则排序。

正确性证明

引理 1：查询计算的 abnormal_cnt 等于每个批次的异常任务数量。

证明：对每项任务，当且仅当状态不是 PASS 或实际数量少于计划数量时，第一条 CASE 返回 1，否则返回 0。对批次内所有任务求和，恰好得到异常任务数量。引理得证。

引理 2：查询计算的 shortfall 等于批次的总少检数量。

证明：实际数量少于计划数量时，第二条 CASE 返回 plan_cnt - actual_cnt；其余任务返回 0。求和后只累计正的少检差值，符合定义。引理得证。

定理：查询返回且仅返回目标日期内存在异常任务的批次，并正确计算字段与排序。

证明：WHERE 保留目标日期任务，GROUP BY 按产线和批次聚合。由引理 1、2，各统计值正确；HAVING abnormal_cnt >= 1 恰好过滤出存在异常的批次，ORDER BY 与题目要求一致。定理得证。

SQL 代码

SELECT b.prod_line,
       b.batch_id,
       COUNT(*) AS task_cnt,
       SUM(
           CASE
               WHEN t.inspect_status <> 'PASS'
                    OR t.actual_cnt < t.plan_cnt
               THEN 1
               ELSE 0
           END
       ) AS abnormal_cnt,
       SUM(
           CASE
               WHEN t.actual_cnt < t.plan_cnt
               THEN t.plan_cnt - t.actual_cnt
               ELSE 0
           END
       ) AS shortfall
FROM c21_jd_inspection_batches AS b
JOIN c21_jd_inspection_tasks AS t
  ON t.batch_id = b.batch_id
WHERE b.batch_date = '2026-10-01'
GROUP BY b.prod_line, b.batch_id
HAVING abnormal_cnt >= 1
ORDER BY abnormal_cnt DESC,
         shortfall DESC,
         b.prod_line ASC,
         b.batch_id ASC;

复杂度分析

时间复杂度：设目标日期关联后的任务数为 $N$，典型哈希聚合为 $O(N)$；最终对 $G$ 个异常批次排序为 $O(G\log G)$。

空间复杂度：$O(G)$，用于保存分组聚合结果；具体执行计划还取决于索引和数据库实现。

易错点

• “状态异常”和“少检”是不同口径，必须分别编写条件。
• shortfall 不能直接累加 plan_cnt - actual_cnt，否则超额抽检会产生负数。
• 日期属于行级过滤条件，应写在 WHERE 中；是否存在异常属于组级条件，应写在 HAVING 中。
• GROUP BY 同时包含 prod_line 和 batch_id，兼容 MySQL 的 ONLY_FULL_GROUP_BY 模式。

小结

• 等级序列还原的核心是找到召回部分与留下部分之间的评级分界值，再分别构造定长定和序列。
• 单败淘汰赛中，最优无序对阵树唯一；每个内部结点都可交换左右子树，因此答案为 $2^{2^m-1}$。
• SQL 题需要分别统计异常任务数和少检总量，并在聚合后过滤无异常批次。