恒生电子Java开发笔试：散列查找长度、双端队列与red变位子串

轮次: 笔试
时间: 2026-09
来源: 牛客网

《面试题目》

单选题（约 15 到 20 道）：以数据结构为主，例如给一个散列函数求该散列表的平均查找长度；给一个进队序列，判断哪些出入队顺序在双端队列下不合理；计算机网络考协议分层判断（有一个选项是「TCP、IP 协议属于传输层」，这是错的，IP 属于网络层）；以及若干多线程相关的题目。
多选题（5 道）：给了冒泡排序、归并排序、快速排序、希尔排序四种排序，找出空间复杂度不是 O(1) 的那些。
填空题（SQL 查询）：在 sales 表中筛选出所有销售组别的销售额大于 5000 的组别信息。
编程题一：一道复杂度很高的 SQL 题。
编程题二：键盘输入一段字符串，输出其中「red」子串的个数，子串可以经过顺序变换（例如 der 也算）。
编程题三：一道动态规划题。

《参考解析》

散列表的平均查找长度：ASL 分「查找成功」与「查找失败」两种，都要按等概率加权。查找成功的 ASL = 每个关键字的比较次数之和 ÷ 关键字个数；查找失败的 ASL = 每个可能落空位置（或每个哈希地址）比较次数之和 ÷ 地址个数（不同教材对失败情形的划分口径不同，做题要先确认是「按哈希地址」还是「按除余数的模」来统计）。计算方法固定：把每个关键字按给定哈希函数算地址，再按冲突解决策略（线性探测、二次探测、链地址）确定它最终落的位置，比较次数就是从初始地址到最终位置的探测步数。链地址法下，成功时的比较次数等于该链表中的位置序号，失败时等于对应链表的长度（有的教材算成「空指针也算一次比较」）。这类题的得分点全在「不跳步」：把哈希表画出来、逐个标探测次数，再求和，比直接套公式可靠。

双端队列的合法出入队序列：双端队列允许在两端插入和删除，所以它的合法序列集合比栈和普通队列都大。判断方法有两种。稳妥的是模拟：拿题目给的输出序列，从第一个元素开始反推——若某元素既不在当前队首也不在队尾，那它只能尚未入队，于是把输入序列里在它之前的元素按顺序补入，再看是否满足；任何一步无法在两端找到可弹出的元素，该序列即不合法。另一种是记结论：输入序列固定为 1..n 时，栈的合法输出必须避免「3-1-2」这类模式，而双端队列的限制宽松得多，只有形如「先输出中间的元素，而两端元素尚未入队且中间元素被夹住」的情况才会矛盾。考场上建议直接用栈或双端队列跑一遍模拟，比记模式更不容易错。

空间复杂度不是 O(1) 的排序：四种里只有归并排序不是——标准归并需要一个与原数组等长的辅助数组，空间复杂度 O(n)（递归栈是 O(log n)，被 O(n) 盖过）。冒泡、希尔都是原地交换，O(1)；快速排序平均递归深度 O(log n)、最坏 O(n)，属于「辅助空间 O(log n)」，通常也归入不是严格 O(1) 的一类，所以这道多选如果严格按「O(1)」判定，答案应当是归并排序（以及视出题口径而定的快速排序）；如果题目只问「不是原地」，那只有归并。作答时把自己采用的口径写一句，选择题里这能避免因出题人定义不同而丢分。

SQL 填空（按销售组别筛销售额）：

SELECT sales_group, SUM(amount) AS total_amount
FROM sales
GROUP BY sales_group
HAVING SUM(amount) > 5000;

要点是区分 WHERE 与 HAVING：过滤的是聚合结果（SUM），只能用 HAVING，WHERE 在分组之前执行、拿不到聚合值。如果还需要组别的其他信息（名称、负责人），要么在 GROUP BY 里把字段列全（MySQL 在关闭 ONLY_FULL_GROUP_BY 时能放宽，但不该依赖），要么先聚合出组别列表再 join 回维表。另外要注意 NULL 的处理：SUM 会忽略 NULL，但 COUNT(*) 不会，如果题目要求「组内所有记录都必须有效」，还得加 COUNT(amount) = COUNT(*)。

编程题二：统计「red」的变位子串个数：题意是长度为 3 且字符多重集等于 {r, e, d} 的子串数量（顺序无所谓）。用固定窗口滑动，维护窗口内三个字符的计数即可，O(n) 时间、O(1) 空间：

def count_red(s: str) -> int:
    target = {'r': 1, 'e': 1, 'd': 1}
    n, cnt = len(s), 0
    window = {}
    for i, ch in enumerate(s):
        c = ch.lower()                     # 若题目区分大小写就去掉这一行
        window[c] = window.get(c, 0) + 1
        if i >= 3:                         # 移出窗口左侧的字符
            left = s[i - 3].lower()
            window[left] -= 1
            if window[left] == 0:
                del window[left]
        if window == target:               # 长度恰为 3 且三字符各 1 个
            cnt += 1
    return cnt

三个易错点：窗口只在长度达到 3 之后才参与判定（否则会把长度 1、2 的窗口误判）；字符出现重复时必须靠「计数相等」判断，不能靠集合（set 会把 rreedd 判为合法）；如果题目不区分大小写要显式做归一化——但这样 R、D 也会被算进来，反过来若题目要求严格匹配小写，就不该做 lower()，读题时务必确认。

编程题三：动态规划：题面未给出具体内容，但笔试里的 DP 题几乎都能用同一套流程拆解：第一步定状态——想清楚「前 i 个元素的最优解」需要知道哪些额外信息（往往是「以 i 结尾」或「用了多少容量」），把这些信息作为状态的维度；第二步写转移方程——枚举最后一个决策（选或不选、切在哪、从哪个前驱转移），把问题化归到规模更小的子问题；第三步定边界与初始化，把「空集」「长度为 1」这类退化情形单独写好；第四步确定遍历顺序（保证用到的子问题已经算过）并做空间优化（滚动数组/一维化）。常见的题型有背包、最长上升子序列、编辑距离、区间 DP、状态压缩 DP——复习时按类型各刷几道并记住「状态定义」的写法，比散着刷题效率高得多。写代码前先把状态定义用一句话写进注释，能显著降低写错转移的概率。

《面试题目》

《参考解析》

相关面经