第2章 高频算法面试题与回答框架
算法面试是深度学习实习生面试的核心关卡。本章围绕“暴力解→优化→最优”的答题结构，拆解常见分类、考察点及不同公司风格。掌握结构化的表达框架，能让你在短时间内展示清晰的解题思路和优化能力。
📝 面试问答卡片
面试问题：给定一个整数数组 nums 和一个整数 target，请找出和为目标值的两个整数，返回它们的下标。
面试官考察点：①能否快速想到暴力解；②是否理解空间换时间；③能否口头推导时间复杂度、空间复杂度。
回答框架：
- 暴力解：双层循环枚举 (i, j)，O(n²) 时间，O(1) 空间。
- 优化思路：瓶颈在内层搜索 target-nums[i]，可用哈希表将查找降为 O(1)。
- 最优解：一次遍历，check 哈希表 → 存入当前元素，O(n) 时间，O(n) 空间。
简短示例回答：“我先想到暴力两层循环，时间复杂度O(n²)。但注意到我们实际上在找 target-nums[i]，可以用哈希表存储已经遍历过的值和下标，边遍历边查，降到O(n)时间，空间O(n)。”
可能追问：“如果要求返回元素值而不是下标？” “数组有序时能否优化到O(1)空间？”
避坑提醒：不要直接说“用哈希表”，要说明为什么哈希表能解决“查找”瓶颈；注意处理重复值。
面试问题：实现二叉树的中序遍历，要求使用迭代方法（非递归）。
面试官考察点：① 递归与迭代的转换能力；② 对栈模拟递归过程的理解；③ 边界条件处理（空树、只有左/右子树）。
回答框架：
- 暴力解：递归实现，简单但可能栈溢出（深度大时）。
- 优化：用显式栈模拟递归，控制入栈顺序：左链入栈 → 出栈访问 → 处理右子树。
- 最优：Morris 遍历（线索二叉树），O(n) 时间，O(1) 空间；面试时可作为加分点提及。
简短示例回答：“递归是最直接的，但面试官要求迭代。我用栈模拟：当前节点不为空则入栈并走向左；为空则出栈访问，再转向右子树。这样空间复杂度从递归的O(h)变为显式栈O(h)。”
可能追问：“Morris遍历的工作原理是什么？” “前序/后序的迭代怎么写？”
避坑提醒：面试中不要直接默写代码，先讲清楚入栈/出栈的“指针移动”逻辑；给出Morris时可说明“面试时间有限就不详细展开了”。
面试问题：给定一个无序整数数组，找出最长严格递增子序列的长度。
面试官考察点：① 动态规划基础；② 能否从 O(n²) 优化到 O(n log n)；③ 是否理解“贪心 + 二分”的本质。
回答框架：
- 暴力解：枚举所有子序列（2n），不现实。
- 优化（DP）：dp[i] 表示以 i 结尾的 LIS 长度，每次向前遍历找比 nums[i] 小的最大值，O(n²)。
- 最优（贪心+二分）：维护一个数组 tails，tails[k] 表示长度为 k+1 的递增子序列的最小末尾值。二分查找插入位置，O(n log n)。
简短示例回答：“首先想到DP——对于每个位置，往前扫描更新dp，O(n²)。但注意到我们只关心每个长度下的最小末尾，可以用二分优化：遍历每个数，在tails里找第一个≥它的位置替换，找不到就追加，最终长度就是答案。”
可能追问：“怎么证明 tails 数组是单调递增的？” “输出具体序列怎么做？”
避坑提醒：很多人记不住 tails 的二分边界，最好口头说清楚“找第一个≥当前值的索引”；不要忘了处理相等情况（严格递增需替换）。
🚀 项目案例：图像分类模型端侧部署优化
| 项目名称 | 轻量化分类模型在手机端的部署与加速 |
|---|---|
| 业务背景 | 美图App需要实时识别100类物体，模型需在骁龙865上运行<30ms。 |
| 规模指标 | 训练集50万张，测试集2万张；参数量从MobileNetV2的3.5M压缩到1.2M，推理时间28ms，准确率下降<1.5% |
| 技术栈 | PyTorch → ONNX → TensorRT & NCNN；量化工具：Pytorch Quantization (QAT) + INT8校准 |
| 核心难点 | ① 结构化剪枝与BN融合对精度影响大；② INT8量化后分类层出现偏差；③ 不同Android机型CPU/GPU算子兼容性 |
| 面试高频追问 | “为什么选择结构化剪枝而非非结构化？”“QAT和PTQ的区别？”“如何验证量化后的精度满足业务指标？” |
| 可迁移回答话术 | “我们采用QAT + 逐通道量化来补偿精度损失，并在剪枝后对分类层进行微调。选择结构化剪枝是因为硬件支持更友好，虽然剪枝率有限但部署收益更高。” |
🏢 大厂模拟面试：反转链表
面试官提问：“请实现单链表的反转，要求写出代码并分析复杂度。”
“用头插法反转，遍历链表，依次把节点插入到头结点后面。时间复杂度O(n)，空间O(1)。” ❌ 未说清楚边界，无代码细节，面试官难以判断。
“我使用三个指针prev、cur、next。初始化prev=null，cur=head；循环中先保存next=cur.next，然后将cur.next指向prev，接着prev=cur, cur=next。循环结束prev成为新头。时间复杂度O(n)，空间O(1)。” ✅ 结构清晰，变量作用明确。
“我首先考虑递归解法：reverse(head)返回反转后的新头。递归过程中将head.next.next = head 实现反转，再设head.next=null。但递归有栈深度风险，面试中我倾向于迭代。边说边写伪代码：
prev = null; cur = head;
while(cur) { next = cur.next; cur.next = prev; prev = cur; cur = next; }
return prev;
面试官如果您愿意，我可以补充递归写法并对比两者优劣。” ⭐ 体现多种解法、可扩展性，主动展示沟通意愿。
面试官追问：“如果只让你反转链表的第m到第n个节点呢？”
“可以先定位到m-1位置，然后用反转链表的迭代法处理区间，注意连接前后的指针。先走m-1步，记录prevEnd；然后反转n-m+1个节点，将原头尾与前后连接。需要特别处理m=1的情况。” ✅ 思路正确，能处理边界。
“我采用哑结点统一边界。创建dummy.next=head。用指针pre=dummy，走m-1步到达反转区间前一个节点。然后定义cur=pre.next，用头插法反转n-m个节点：每次把cur.next插入到pre后面。最后返回dummy.next。这样代码简洁，m=1时也不需特殊处理。” ⭐ 利用哑结点工程化思维，面试官会印象深刻。