第4章 技术面试：数据结构与算法：排序、链表、二叉树、动态规划
本章节聚焦大厂高频算法考点：排序、链表、二叉树与动态规划。面试中不仅考察代码实现，更关注复杂度分析、边界处理和优化思路。请先掌握通用的算法回答框架：理解题意 → 分析复杂度 → 选择数据结构 → 编码实现 → 测试边界。
面试问答卡片
🔹 卡片1：手写快速排序并分析复杂度
面试问题：请手写快速排序算法，并分析时间/空间复杂度。
考察点：分治思想、递归实现、稳定性、最坏情况。
回答框架：①选择基准（最后一个元素）；②双指针分区；③递归左右子数组。
示例回答：“快速排序采用分治：选末元素为 pivot，left 指针找大于等于 pivot 的元素，right 指针找小于 pivot 的元素交换，递归排序左右部分。平均 O(nlogn)，最坏 O(n²)，可用随机基准优化。空间 O(logn) 递归栈，不稳定排序。”
可能追问：如何避免最坏情况？三数取中法、随机选择 pivot、小数组改用插入排序。
🔸 卡片2：反转单链表（迭代+递归）
面试问题：反转一个单链表，分别用迭代和递归实现。
考察点：指针操作、递归理解、边界处理。
回答框架：迭代：三指针 prev/curr/next；递归：假设后续已反转，当前节点指向前驱。
示例回答：“迭代：prev 初始 null，当前 curr=head，while 循环中保存 next，将 curr.next 指向前驱，依次后移。递归：base case head==null 或 head.next==null，否则递归反转 head.next，令 head.next.next=head，head.next=null。”
可能追问：反转前 m 到 n 个节点？检测环形链表？
🔹 卡片3：二叉树最大深度（递归+非递归）
面试问题：求二叉树的最大深度，要求递归和层序双解法。
考察点：树的遍历、递归栈深度、队列/栈应用。
回答框架：递归：depth = max(leftDepth, rightDepth) + 1；非递归：层序遍历统计层数。
示例回答：“递归：空树返回0，否则返回左右子树最大深度加1。非递归用队列：root 入队，每次处理整层节点，节点出队时子节点入队，层数+1，直到队列空。两种方法均 O(n) 时间，递归空间 O(h)，非递归 O(w) 其中 w 为最大宽度。”
可能追问：平衡二叉树判断？最近公共祖先？二叉树路径总和？
项目案例模板：动态规划实战
| 项目名称 | 智能物流路径规划系统 |
| 业务背景 | 电商配送中心为每日10万+订单规划最短配送路径，降低运输成本30% |
| 规模指标 | 覆盖500个配送点，日均请求量50万+，路径计算响应<200ms |
| 技术栈 | Python / Flask / 图数据库 / 动态规划 + 贪心混合策略 |
| 核心难点 | ①大规模组合优化下如何保证最优解；②实时新增订单的动态调整；③高并发下的计算性能 |
| 面试高频追问 | 动态规划与贪心区别？如何设计状态转移方程？空间换时间的具体做法？ |
| 可迁移回答话术 | “本项目将多目标配送问题抽象为最短路径DP模型，定义状态dp[i][j]为访问节点集合i后到达j的最小距离。通过位压缩优化状态表示，使用备忘录缓存中间结果，将复杂度从O(n!·n)降至O(2ⁿ·n²)。面对新增订单，采用增量式更新，仅重算受影响子路径。” |