标签题目
复杂度相关面试题
还有哪些 O(nlogn) 的排序算法，各自的原理和使用场景？
这题考察常见 O(nlogn) 比较排序的原理、复杂度、稳定性和场景选择，不能只列名字。
给定整数数组，如何求和为 m 且长度最短的子数组长度？
求和为 m 的最短连续子数组要先确认数组元素是否都为正，正数数组可用滑动窗口，含负数时要改用前缀和和哈希结构。
如何求字符串的最长重复子串长度？
最长重复子串可以从暴力比较、后缀数组、后缀自动机或二分长度加哈希回答，面试中重点讲清重复子串和复杂度取舍。
如何用 DP 解决高楼扔鸡蛋问题？
高楼扔鸡蛋问题可以用动态规划刻画鸡蛋数、楼层数和最坏次数，核心是在每个测试楼层上平衡碎和不碎两种结果。
给定输入 shape 为 (b, s, h)，如何估算 Multi-Head Attention 的计算量？
这题考给定输入 shape 为 (b, s, h) 时如何估算 MHA 计算量，回答重点是 QKV 投影、注意力矩阵、加权求和和输出投影，其中长序列瓶颈来自 O(b s^2 h)。
如何手写 Beam Search，并处理候选扩展、剪枝和停止条件？
这题考如何手写 Beam Search，回答重点是维护 beam 候选、逐步扩展、按累计分数 top-k 剪枝、处理 EOS 停止并返回最优序列。