京东9.19笔试复盘：图论题卡80分钟，两题没拿分

《面试题目》

1. 编程题一：图论题（作者耗时 80 分钟，未做对）
2. 编程题二：作者判断需要「类似埃氏筛」那种预处理技巧
3. AI coding 题（作者自述后两题基本没拿到分）

《参考解析》

二分查找一直返回 -1 的三个典型原因：一是区间写法混用——while (lo <= hi) 必须配 hi = mid - 1，while (lo < hi) 必须配 hi = mid，两者交叉写就会漏解或死循环；二是边界与返回值没对齐，例如查找「第一个 ≥ target 的位置」时最后返回的应该是 lo，直接返回 -1 的分支只该在数组为空或目标不在值域内时才走；三是忘了先确认输入有序（或对「旋转数组」「重复元素」这类变体套用了普通二分）。调试手段很土但有效：把每轮的 lo / hi / mid 打出来跑一遍小用例，或者直接用语言自带的 bisect / lower_bound 对照结果。

「列表初始化错地方了」意味着什么：这是笔试里最常见的低级失分点。典型情形有两种：结果容器（答案列表、访问标记数组、前缀和）声明在循环外却没在每组用例前清空，上一组数据污染下一组；或者声明在 for 内部，导致每轮都重新分配、累加结果被重置。多组输入的题目一定要写清「哪些状态是跨用例共享的、哪些必须每组重置」。Python 里还要小心可变默认参数 def f(a=[]) 这个经典陷阱。

埃氏筛类题目的识别与复杂度：当题目要求统计「区间内与某数互质」「每个数的倍数/约数贡献」「最小质因子」这类信息时，不要对每个数单独分解质因数（那是 O(n√n)），而是用筛法按质数倍数批量标记，复杂度 O(n log log n)；即便用最朴素的「对每个数枚举倍数」写法也只是 O(n log n)，在 n ≤ 1e7 时通常都能过。识别信号是数据范围大但值域有限。

AI coding 题怎么把分拿稳：这类题按通过测试点给分，策略是先把最小用例跑通再谈优化；每改一步就自测一次，不要攒一大段再提交；提交前专门过一遍边界（空输入、单元素、全相等、极大值、多组输入）；最后回头读一遍题目的输入输出格式与复杂度要求——很多「没分」不是算法错，而是 IO 格式或数据类型（int 溢出要换 long）不对。