虾皮测试开发一面：两个项目深挖加三道算法题

《面试题目》

1. 请介绍简历上的两个项目，说明各自的背景和你负责的部分。
2. 这个项目有没有找过真实用户做查询？
3. 项目有没有真实运行数据？
4. 算法题：只出现一次的数字（力扣 136 变体）。
5. 算法题：相邻孤独数字。
6. 算法题：石子游戏 VII 的一种变体。

《参考解析》

只出现一次的数字（异或解法）：核心性质是 a ^ a = 0、a ^ 0 = a，而异或满足交换律与结合律，所以把整个数组异或一遍，成对出现的元素互相抵消，留下的就是落单的那个。时间 O(n)、空间 O(1)，是这类题的标准答案。

常见变体要一起准备：如果是恰好两个数字只出现一次，整体异或得到 x ^ y，取它最低位的 1 作为分组依据（low = diff & -diff），按这一位把数组分成两组分别异或，就还原出 x 和 y；如果其余数字都出现三次，改成逐位统计 1 的个数再对 3 取模，用位运算拼回答案；如果数组本身有序，也可以按「成对的下标奇偶性」二分，把线性做法压到 O(log n)。写的时候注意 diff & -diff 依赖补码，等价于 diff & (~diff + 1)；另外面试官常追问「为什么异或能抵消」——答「按位模 2 加法，两次相同就归零」，比只背结论更能证明你真的理解了。

石子游戏 VII 的区间 DP：题面是双方轮流从当前区间的左端或右端取走一颗石子，取走后的得分等于剩余石子的总和，两人都按最优策略走，求先手与后手的最大分差。关键观察是当前这一步能拿多少分只取决于剩下的区间，于是定义 dp[i][j] 为「面对区间 [i, j] 时当前行动者能取得的相对分差」，转移写成：

dp[i][j] = max(sum(i+1..j) - dp[i+1][j], sum(i..j-1) - dp[i][j-1])

含义是取左端拿到剩余区间和，之后对手在更小的区间上能建立 dp[i+1][j] 的相对优势，所以自己被反超这一部分。用前缀和把区间和做到 O(1)，状态 O(n²)、转移 O(1)，总时间 O(n²)、空间 O(n²)，可以按区间长度从小到大递推。边界是 dp[i][i] = 0（只剩一颗时取走不得分）。变体一般改的是计分口径，比如改成取走石子的值本身计分（石子游戏 I、II 那一类）、或者改成双方都取最大值，只要抓住「分数由剩余区间决定」这一点，重新写前缀和口径就能套同一套转移。手撕时先把状态定义讲清楚再落笔，比直接默写模板更容易拿分。

项目缺少真实业务数据时怎么答：这道追问考的不是数据有多少，而是你知不知道自己的验证边界在哪。第一步先坦率划清来源——哪些评测数据来自知识库与 AI 合成、哪些环节没有任何真实流量，含糊其辞反而会让面试官继续往死里追。第二步论证现有数据的有效性：合成用例覆盖了哪些意图分布与边界情况，是不是用它能区分出好坏两个版本（做 A/B 或消融对比），有没有人工抽检过的 golden set 兜底。第三步给出补齐路径：线上日志脱敏采样、公开数据集、灰度期小流量真实请求、人工标注难例回流。最后主动谈风险：AI 合成的用例容易和提示词同源、指标虚高，所以报告效果时要写清覆盖缺口和置信区间，而不是只给一个漂亮数字。测开面试官真正想听的是「你会不会怀疑自己的数据」。