恒生电子 Java 笔试记录：SQL 填空加两道算法编程题

《面试题目》

1. 单选题 10 道、多选题 5 道。
2. SQL 填空题 1 道。
3. 编程题：SQL 题，输入数据量很大。
4. 编程题：给定一个字符串，输出长度为 3 的子序列中可以重排序为 red 的数量。
5. 编程题：给 n 个正整数和目标 m，选若干数字求和，最多可以把其中一个被选中的数除以 2（向下取整），问能否凑出等于 m。

《参考解析》

「red」子序列计数怎么写：题目要的是长度 3 的子序列（不要求连续）三个字符恰好组成 red，等价于统计所有下标三元组 i<j<k 满足 {s[i],s[j],s[k]} = {r,e,d}。暴力枚举是 O(n³)，n 到 1e5 必然超时。O(n) 的做法是枚举中间位置：对每个下标 j，统计它左边各字符出现次数 left[c]、右边各字符出现次数 right[c]，则以 j 为中间元素的合法三元组数是 Σ left[a] * right[b]（a、b 取除 s[j] 之外的另外两个字母），用两个长度 3 的计数数组边走边维护即可——先扫一遍得到总计数，遍历到 j 时先把 s[j] 从 right 里减掉，算完答案再加进 left。整体 O(n)、O(1) 额外空间，答案要用 long long（组合数会超过 int）。面试时值得主动说清三件事：子序列和子串的区别、字符重复时靠乘法组合来计数（而不是判重）、以及这个「枚举中间元素 + 前后缀计数」的套路可以推广到任意长度和任意模式串。

最多一个数除以 2 的凑和问题：这是一道带额外状态的可行性背包。把「折半机会有没有用过」当成第二维：dp[k][0] 表示没用过折半能凑出和 k，dp[k][1] 表示已经用过一次能凑出和 k。逐个处理数字 x，和维度倒序枚举（保证每个数只用一次），转移为 dp'[k][0] |= dp[k-x][0]、dp'[k][1] |= dp[k-x][1] | dp[k - x/2][0]（x/2 向下取整）。答案就是 dp[m][0] | dp[m][1]。n、m 到 1e5 量级时用位运算加速最划算，例如 std::bitset 或 Python 大整数：dp0 |= dp0 << x; dp1 |= (dp1 << x) | (dp0_old << (x>>1))——注意第二个式子里必须是更新前的 dp0，因为折半要算作「在使用 x 的这一步」生效，否则同一个数会被既完整使用又折半使用。边界情况：m 为 0 恒可行、x = 1 时折半得 0（看题目是否允许）、以及「最多一个」意味着可以一次都不用。

这套笔试卷面透露的备考重点：恒生把 SQL 的权重放得很高（一道填空 + 一道大体量编程题），说明业务里数据库操作占比大，只刷 LeetCode 是不够的，多表 join、聚合、窗口函数、以及读得懂「输入一大堆数据」的建表和查询需求都要练。选择/填空偏 Java 基础八股（集合、并发、JVM、数据库范式），判断题最常见的陷阱是把结论写成绝对化表述（「一定」「绝不会」），遇到这类措辞基本可以先怀疑它。两道编程题本身不难、但都埋了坑——组合计数要用 64 位、背包要多加一维状态；稳妥的做题顺序是先写暴力对拍验证小样例，再上正解，比一上来追最优写法更不容易翻车。