京东后端笔试 10·24:相邻和为 2 的幂的最长子序列、m 个质数求和与 AI Coding
- 轮次
- 笔试
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
编程题
- (20 分)给出序列 a,找到最长的子序列 b,要求 b 中相邻两个元素之和是 2 的幂。数据范围:n ≤ 2×10⁵,aᵢ ≤ 10⁹。
- (30 分)给出 n、m,判断是否存在一种方案使 m 个质数相加等于 n;不存在输出 -1,存在输出方案(顺序无关)。数据范围:n ≤ 10⁶。
AI Coding
- (50 分)实现一个「链式提案系统」,需要用 AI 辅助完成,按测试点给分。
复盘
- A 题从 O(n²logn) 的 DP 怎么优化到 O(nlogn)?
- B 题这类「m 个质数之和」的题该往哪个方向想?
- AI Coding 题应该怎么安排时间与流程?
《参考解析》
A 题:DP + 枚举 2 的幂。 定义 f[i] 为「以第 i 个元素结尾的最长合法子序列长度」,转移是 f[i] = max(f[k] + 1),其中 k < i 且 a[i] + a[k] 是 2 的幂。朴素做法枚举 k 是 O(n²),每次判 2 的幂再花 O(log),总计 O(n²logn),只能过小数据。优化的关键是「2 的幂并不多」:a[i] + a[k] ≤ 2×10⁹ < 2³¹,所以可能的和只有 2⁰ 到 2³⁰ 共 31 个。于是反过来枚举这 31 个目标值 p,令 a[k] = p − a[i],用一个 map<值, 该值出现过的最大 f> 直接查到对应的最优 k,转移就是 f[i] = max(f[i], best[p − a[i]] + 1)。处理完第 i 个元素后再把 (a[i], f[i]) 更新进 map(取 max)。总复杂度 O(31n) = O(nlogn)(map 的 log 因子)。两个坑:一是值域到 1e9,和可能到 2e9,要用 64 位;二是子序列不要求连续、但要保持相对顺序,所以必须按 i 从前往后处理,map 里只能存「i 之前」的结果——先转移后更新,顺序不能反。
B 题:先用奇偶性把问题降维,再用哥德巴赫。 质数里只有 2 是偶数,其余都是奇数,所以「m 个质数之和为 n」的奇偶性完全由「用了几个奇质数」决定:m 个数里有 k 个奇数质数,则和的奇偶性与 k 相同。几个直接结论:① 最小可能的和是 2m(全用 2),所以 n < 2m 直接 -1;② m == 1 时 n 必须是质数;③ 让其中 m−1 个都取 2,最后一个是 n − 2(m−1):若它是质数(且 ≥2),方案就是「m−1 个 2 + 它」,这是最省事的一支;④ 若这一支不成立(n − 2(m−1) 是合数),说明需要更多奇质数:n 为偶数时,取 m−2 个 2、剩下 x = n − 2(m−2) 为偶数且 ≥4,用强哥德巴赫(偶数 = 两质数之和)在筛出的质数表里找一对 p + q = x;n 为奇数时,取 m−3 个 2、剩 y = n − 2(m−3) 为奇数且 ≥7,用弱哥德巴赫(奇数 ≥7 = 三质数之和)先枚举一个质数 p,再对 y − p 做偶数拆分。筛法预处理到 1e6 的质数表(欧拉筛 O(n)),查询时枚举的代价很小。这题的失分点在于「一上来就想构造、没有先用奇偶性把情况压到少数几支」。
AI Coding 题的正确节奏。 作者的复盘其实已经把要点说完了:① 别花时间逐字读懂题面 md,先让 AI 总结背景与输入输出,自己只确认关键约束;② 一开始就建 SPEC/需求文件(目标、接口、数据结构、验收样例、优先级),否则后面每次对话都要重新解释;③ 先让 AI 出一个能跑通最简样例的基础版本,再按测试点逐步加功能——「先跑起来再变强」,不要先做架构设计;④ 提交后能看到哪些测试点没过,就面向失败的测试点逐个修,而不是让 AI 自己排「难点顺序」;⑤ 一个功能一个功能地收敛,避免「积木越搭越高但一直跑不起来」。时间分配上建议:读题 5 分钟、基础版本 20 分钟、按测试点迭代 40 分钟、留 5 分钟检查边界。
关于「AI 写不出来」的判断。 如果某个测试点反复改都过不去,先缩小复现范围(把失败用例单独抽出来跑),再让 AI 只针对这个用例改,而不是继续在整份代码上打补丁。多数「AI 解决不了」的情况,其实是上下文太杂、约束没写清、或者失败信息没给全。