虾皮算法笔试回忆：单选多选与三道编程

《面试题目》

1. 单选题：概率论、排序算法比较、Linux 进程、深度学习相关考点
2. 多选题：SQL、激活函数相关考点
3. 编程题一：字符串处理加模拟，题目要求比较多
4. 编程题二：用 DFS 求解迷宫问题
5. 编程题三：螺旋矩阵

《参考解析》

排序算法比较的常考维度

要比三样：平均与最坏时间复杂度、额外空间、稳定性。冒泡、插入、选择都是 O(n^2)，其中插入排序在近乎有序时接近 O(n)；快排平均 O(n log n)、最坏 O(n^2)（有序数组取首元素做基准时），不稳定，递归栈 O(log n)；归并稳定、稳定 O(n log n)，但要 O(n) 辅助空间；堆排 O(n log n)、不稳定、O(1) 空间。比较类排序的下界是 O(n log n)，计数排序、基数排序靠额外空间换到线性。选择题常问「哪个不稳定」「哪个最坏是 O(n^2)」「哪个需要额外空间」，把这张表背熟即可。

Linux 进程相关

高频点是 fork 的返回值：父进程拿到子进程 pid，子进程拿到 0，失败返回 -1。僵尸进程是子进程先退出而父进程没 wait，进程表项还占着；孤儿进程是父进程先退出，被 init 收养。进程状态 R 运行、S 可中断睡眠、D 不可中断睡眠、Z 僵尸、T 停止。还有进程和线程的区别（资源分配与调度单位）、进程组与会话、ps/top/nice 的用法，以及信号与 kill 的语义。

概率论

选择题常见古典概型（组合计数，注意分子分母用同一种「有序/无序」口径）、条件概率与贝叶斯、期望的线性性（不必独立就能相加）、几何概型（会面、投针，把连续量写成面积比）、独立与互斥的区别（互斥且概率非零时必不独立）。独立重复试验直接上二项分布。

激活函数

Sigmoid 输出落在 (0,1) 但非零均值、两端饱和梯度趋零，深层网络容易梯度消失；Tanh 零均值、饱和问题依旧；ReLU 计算便宜、正半轴不饱和，但负半轴梯度为零，学习率过大可能出现死亡神经元；LeakyReLU、PReLU、ELU 给负半轴留一条小梯度；GELU、Swish 是平滑版本，Transformer 和现代 CNN 常用。多选题常绕着「是否零中心」「能否缓解梯度消失」「是否可导、是否单调」出选项。

DFS 迷宫

递归或显式栈都可以，关键是 visited 标记和边界判断，防止来回横跳导致栈溢出死循环。只要判断可达性，DFS 够用；要最短路就必须换 BFS，因为 DFS 找到的路径不一定最短。网格题注意坐标越界、起点终点重合、障碍格判断，以及是否需要「转向次数」「钥匙门」之类的附加状态——一旦有附加维度，就要把方向、钥匙集合并进状态里，用多维 visited 去重。

螺旋矩阵

标准做法是按层模拟，维护 top、bottom、left、right 四条边界，每层依次向右、向下、向左、向上遍历，遍历完收缩边界。最容易错的是只剩一行或一列时的重复遍历，需要在每段结束后加判断。也可以开方向数组，遇到越界或已访问就右转，用改值或 visited 记录，空间 O(1)。输出规模是 n×m，边界条件按「先判断再遍历」写比事后去重更稳。

字符串处理加模拟

这类题的失分点几乎都在边界：前导零、正负号、空串、连续分隔符、超长输入、大小写与全角半角。动手前先把规则写成状态机（当前处在什么状态、遇到什么字符往哪转），再落代码；用正则时要格外小心回溯和贪婪匹配。题目规则多时宁可先写一版纯模拟拿分，再回头优化常数，别一上来就想贪心。