BIGO 前端 9.19 笔试 三道算法题复盘

《面试题目》

1. 单选题：难度一般。
2. 多选题：有几个选项不太确定，还出现了一道没接触过的 WebGL 相关题目。
3. 编程题：求重复子串，至少重复一次。
4. 编程题：给定一个整数，求这个整数范围内能被 3 或 5 整除的数的前序和，数据范围较小。
5. 编程题：旋转打印数字，碰到边界就加 1。

《参考解析》

重复子串判定（KMP）：判断一个字符串里是否存在「至少出现两次」的子串，最简单的情形是判断「是否存在一个子串紧挨着重复出现」，那就等价于对字符串的 next 数组（最长相等前后缀）做判断：如果存在某个位置 i 使得 next[i] > 0 且 s[i] == s[next[i]]，说明有相邻重复的子串。更通用的「某子串出现至少两次（可重叠）」可以用后缀数组/后缀自动机求最长重复子串，笔试里一般不会要求。KMP 的关键是 next 数组（或 pi 数组）的递推：pi[i] 表示前缀 s[0..i] 的最长相等真前后缀长度，失配时用 j = pi[j-1] 回退而不是回到 0，整体 O(n)。手写不出 KMP 模板时，可以先用哈希 + 二分的思路顶上（对长度二分，用滚动哈希判断是否有重复），复杂度 O(n log n)，虽然不如 KMP 优雅但能过大多数笔试数据。所以这类题的正确备考姿势是把模板背到能默写：KMP 的 next、滚动哈希、二分答案这三个是高频工具。

能被 3 或 5 整除的数之和：数据范围小时直接循环累加也能过，但正确解法是 O(1) 的容斥 + 等差数列求和，写出来能加分。设 n 为上限，记 S(k) = k * (1 + n/k) * (n/k) / 2，表示 1~n 中所有 k 的倍数之和；答案是 S(3) + S(5) - S(15)，减去 15 的倍数是因为它们被算了两次。三个易错点：n/k 要用整除，S(k) 里的乘法要先转成 64 位避免溢出（n 到 10^9 时结果约为 3.3×10^17，超过 int 范围），以及边界 n < 3 时答案是 0。原帖提到的「筛算法」其实是埃氏筛的变体，用来标记哪些数能被整除，在范围小时可行，但 O(n) 复杂度不如公式法。

旋转打印数字（螺旋矩阵）：这是经典的模拟题。维护四个边界 top、bottom、left、right，按「从左到右、从上到下、从右到左、从下到上」四步循环走，每走完一条边就把对应边界收缩一格，并在收缩后检查是否越界以终止循环。细节有两处：从右到左和从下到上这两条边必须先判断 top <= bottom、left <= right，否则单行或单列时会把同一行重复打印；输出格式按题目要求可能是蛇形填充数组或直接打印序列，别搞混。复杂度 O(n²)，空间除输出外是 O(1)。如果题目要求「碰到边界就加 1」的变体，本质是同一套边界收缩逻辑，只是填入的值随方向变化，写的时候把「方向 → 边界 → 值」三张表列出来就不容易乱。