京东技术岗笔试：模拟题与四因数子数组

《面试题目》

1. 编程题一：纯模拟题（原帖未保留完整题面），作者用队列实现
2. 编程题二：给定一个数组，找两个元素 ai 和 aj，其中 i < j 且 ai × aj 有四个因子，输出符合这种组合的子数组
3. AI Coding：题目 8811，最后几个用例的复杂逻辑判别处理不好

《参考解析》

模拟题挂在哪：输入输出没有防御性

作者自己的判断是「本地用例能过、提交提示读取有问题」，很可能是输入输出语句没做防御。多组数据的题目要按 EOF 或给定的组数循环读入，不能只读一组；每行数据的分隔符要容错（多空格、制表符、行尾空格、换行符差异），用 split() 而不是手工按单个空格切；读大输入时别用逐字符读取，会慢。还要处理空行、行数不足、以及数组长度字段和实际数据不一致的情况。

另一类隐性问题是数据规模：队列版本在数据量小时没问题，但如果题目存在多次删除或头部操作的场景，list 或 deque 的选型、以及每轮重建队列的写法都会让常数爆炸。先在本地按上限规模造一组随机数据压测，再看是超时还是运行错误。

四因数子数组：先化简数论条件

一个数的因数个数公式是 ∏(eᵢ + 1)，要等于 4 只有两种质因数形态：p³ 或者 p × q（p、q 为不同素数）。所以判断 ai × aj 是否满足条件，等价于把两个数的质因数分解合并后看签名是不是 {3} 或 {1,1}，不需要真的算出乘积（乘积可能超过 64 位中间范围，而且直接试除乘积代价极高）。

实现上先用最小质因子筛预处理到数值上界，对每个数求出签名；再从左往右扫，用一个哈希表记录已经出现过的签名出现次数，扫到每个元素时查询能与它凑成 {3} 或 {1,1} 的互补签名个数并累加，然后把当前签名计入哈希表。这样是 O(n log V)。要特别注意两个边界：相同素数的一次方相乘得到 p²，只有 3 个因数，所以「凑 p×q」时必须排除同素数；数值 1 的签名是空集，它和「本身已经有四个因数」的数相乘仍然满足条件。

题目要求输出的是符合组合的子数组（而不是个数），那就要在计数的同时把下标对或子数组按题目规定的顺序存下来，注意输出格式（下标从 0 还是 1 开始、是否要求去重、每组之间如何分隔）——只看样例很容易把格式写错，最好把题面里关于输出的每句话都对照一遍。

AI Coding 的复杂用例

作者说这类题「最后几个用例的复杂逻辑判别感觉还是差点火候」。对策是把复杂逻辑拆成可验证的小步骤：先把需求写成一份判定规则清单（哪些输入走哪个分支），针对每条规则各写一组用例，让生成的代码逐条过关，而不是指望一个大函数一次覆盖所有分支。遇到多条件组合的场景（多个标志位、优先级、边界互斥），先用真值表把分支穷举出来，再对照代码逐行检查有没有漏项或顺序错误。提交前至少回归一遍自己写的全部用例。