第三章 常见面试算法与手撕代码题
手撕代码是深度学习模型训练工程师面试的“硬门槛”——面试官通过现场写代码考察你的算法基础、代码风格和工程思维。本章聚焦三大高频题型，附带通用解题框架，帮你形成肌肉记忆。
📌 面试问答卡片
问题1：实现二叉树的中序遍历（递归+迭代）
面试官考察点：递归与迭代的转换能力、栈的使用、对树遍历的熟练度、代码简洁性。
回答框架：先明确中序顺序（左→根→右）；递归版本直接调用左子树、输出根、再调用右子树；迭代版本使用栈模拟，左子节点一直入栈到底，弹出节点访问，再处理右子树。
简短示例回答：
递归：def inorder(root): if not root: return; inorder(root.left); print(root.val); inorder(root.right)。
迭代：用stack=[]，cur=root；while cur or stack: while cur: stack.append(cur); cur=cur.left; cur=stack.pop(); print(cur.val); cur=cur.right。
可能追问：如何用O(1)空间实现中序遍历？如果是线索二叉树呢？如何实现前序或后序的迭代版本？
问题2：实现快速排序
面试官考察点：分治思想、基准选择、递归与原地排序理解、最坏情况处理、代码鲁棒性。
回答框架：选定基准（一般取中间或随机）；双指针或分区函数将小于基准的放左边，大于的放右边；递归排序左右子区域；注意边界条件low>=high时返回。
简短示例回答：
def quicksort(arr, low, high): if low >= high: return; pivot = arr[(low+high)//2]; i, j = low, high; while i <= j: while arr[i] < pivot: i += 1; while arr[j] > pivot: j -= 1; if i <= j: arr[i], arr[j] = arr[j], arr[i]; i+=1; j-=1; quicksort(arr, low, j); quicksort(arr, i, high)。
可能追问：如何优化随机基准？为什么快排是不稳定的？如果数组已有序会怎样？如何改成链表排序？
问题3：实现softmax + 交叉熵损失的前向与反向
面试官考察点：深度学习基础从理论到代码的落地能力、数值稳定性、链式法则推导、代码风格。
回答框架：前向：输入logits，减去最大值避溢出，exp后除以sum得到softmax prob；交叉熵 = - sum(target * log(prob+1e-8))。反向：梯度 = prob - target（对单个样本），批处理取平均。
简短示例回答：
class SoftmaxCrossEntropy:
def forward(self, logits, targets):
shifted = logits - np.max(logits, axis=1, keepdims=True); exp = np.exp(shifted); probs = exp / np.sum(exp, axis=1, keepdims=True); loss = -np.mean(np.sum(targets * np.log(probs + 1e-8), axis=1)); return loss, probs
def backward(self, probs, targets):
grad = (probs - targets) / probs.shape[0]
可能追问：为什么减最大值能解决数值稳定性？反向传播推导过程？batch_size对梯度的影响？如何实现Label Smoothing？