优必选 Java 开发工程师笔试 + B 站研发工程师笔经：八股问答与三道编程题

《面试题目》

优必选科技 Java 开发工程师（9.29 19:00）

1. 单选题 10 道，以 Java 相关基础为主
2. 多选题 4 道，也是 Java 相关
3. 问答题（基础八股）：ArrayList 底层、IoC、缓存雪崩/缓存穿透/缓存击穿是什么及如何解决、Java 的数据类型、HashMap 底层原理
4. 编程题一：最大的子矩阵和（与力扣上的不太一样，返回最大元素和即可）
5. 编程题二：判断能否走到出口并输出最短时间。用字符串表示地图，S 表示出口，. 表示空地，C 表示车，另有一个字母表示障碍物；开车 1 秒一格，不开车 2 秒一格，判断能否走到出口并计算最短时间
6. 编程题三：找出连续子序列和大于 0 的个数，数组长度为 10e6

B 站 研发工程师（笔试）

7. 没有编程题，只有单选、多选和问答，基本都是网络题，问答中有一道 TCP 三次握手

《参考解析》

1. 最大子矩阵和与力扣上的经典题不一样：力扣 53 是「最大子数组和」（一维），题目若说矩阵，标准做法是枚举行区间 [top, bottom]（O(n²)），把每列在该区间内的和压成一维数组，再对这一维跑 Kadane 求最大子段和，总复杂度 O(n³)；矩阵较小或行列可转置时，按较小维度枚举行区间更划算。题目特别说明「返回最大元素和即可」，意味着不需要输出子矩阵的位置，只要一个数，实现上少一层状态记录。如果允许全为负数，要注意初始化不能用 0，否则空子矩阵会顶掉正确答案——用第一个元素初始化即可。

2. 带车的迷宫最短时间，是边权为 1 和 2 的最短路，别直接套普通 BFS：普通 BFS 只适用于边权全为 1 的图，这里「走一格」的代价随状态变化，正确做法是让状态里带上「当前是否有车」这一个维度，即状态为 (位置, 是否在车上)，边权 1（开车移动）与 2（步行移动）。实现上用 Dijkstra（小根堆）最稳；由于边权只有 1 和 2，也可以用 0-1 BFS 的推广——1-2 BFS 双端队列（权 1 推前端、权 2 推后端），复杂度 O(V+E)。容易错的点：上车与下车的规则要先明确（是否只在 C 格才能上车、车能否离开 C 格），出口判断要在到达时立刻返回距离，以及把「不能走到障碍物」和「越界」一起处理。

3. 10e6 规模的「连续子序列和大于 0 的个数」，暴力必然超时：设前缀和 pre[i]，区间 (j, i] 的和大于 0 等价于 pre[i] > pre[j]，于是问题转成「对每个 i，统计它前面有多少个前缀和比它小」——也就是顺序对计数，用归并排序（在合并时统计）或树状数组/离散化后求反序数，复杂度 O(n log n)。10e6 的数据量再加 O(n log n) 是能过的，而 O(n²) 的暴力连样例都过不了（这位同学就是暴力只过 0%）。写这类题时先把「和大于 0」翻译成前缀和比较，是最关键的一步；另外大数组要注意用快读和 64 位整数，前缀和很容易溢出 int。

4. 缓存雪崩、穿透、击穿是同一道题的三张面孔，要分开答解决办法：雪崩是大量 key 同时过期或缓存集群整体不可用，方案是过期时间加随机抖动、多级缓存、集群高可用，再给回源链路加限流降级。穿透是查根本不存在的数据（常出现在恶意扫 ID），方案是布隆过滤器前置拦截、缓存空值并设短过期、接入层做参数校验。击穿是单个热点 key 过期瞬间大量并发一起回源，方案是互斥锁或 singleflight 保证只有一个请求重建、或者热点 key 不设过期由后台更新。答完现象和方案后，最好补一句「三者的区别在于失效的对象不同：一批 key、不存在的 key、一个热点 key」。

5. ArrayList 与 HashMap 的底层要能讲到扩容细节：ArrayList 底层是 Object 数组，默认容量 10（首次 add 时才分配），扩容按 1.5 倍增长（oldCapacity + (oldCapacity >> 1)）并整体复制，随机访问 O(1)、中间插入删除 O(n)；ensureCapacity 预分配可以减少多次扩容的拷贝。HashMap 在 JDK 8 是数组 + 链表 + 红黑树：hash 做了高 16 位与低 16 位异或降低冲突，下标用 (n-1) & hash，链表长度到 8 且数组容量到 64 才树化（容量不足先扩容），负载因子 0.75，扩容翻倍且节点要么留在原位要么移到原位加旧容量。Java 的数据类型这类小题记得把基本类型与包装类、自动装箱拆箱、以及 Integer 缓存的坑一起说。

6. IoC 要答成「控制权反转 + 依赖注入」：传统写法是对象自己 new 依赖，控制权在使用方；IoC 把对象的创建、装配、生命周期交给容器，使用方只声明需要什么。Spring 里落地成 DI，注入方式有构造器（推荐，能暴露循环依赖且便于测试）、setter、字段注入；Bean 默认单例，容器启动时按 @ComponentScan 扫描并注册 BeanDefinition，再通过反射实例化、填充属性、初始化（BeanPostProcessor 前后置，AOP 代理在这里生成）。被追问「IoC 有什么好处」时答：解耦、便于替换实现与写测试、统一管理生命周期和配置。

7. B 站这类「无编程题、全是网络题」的笔试，复习面很集中：TCP 三次握手（SYN、SYN+ACK、ACK，为什么三次而不是两次，序列号与半连接队列）、四次挥手与 TIME_WAIT、HTTP 与 HTTPS（TLS 握手、证书校验、对称与非对称加密的分工）、HTTP 常见状态码与缓存头、TCP 与 UDP 的区别、DNS 解析流程、以及网络分层与各层设备。这类卷子题量不大但覆盖面广，遇到不会的不要在单选题上纠缠，先把问答的主观题写满——问答题里能体现条理（先答机制、再答为什么这么设计）比多蒙对两道选择题更有分量。