2026-10-14算法+面经总结

Source

1.软件测试实验和作业
2.
数组中的第K个最大元素
要求：时间复杂度O(n)，直接sort是O(nlogn)
思路：用快速选择算法，先随机取一个值，然后每排一次，左边小，右边的大

快速选择 = 快速排序 + 剪枝

快速排序会递归处理左右两边，但快速选择只处理一边：

  • 每次 partition 后，pivot 的位置就确定了

  • 如果 pivot 正好是第 k 个位置，直接返回

  • 如果 k 在左边，只递归左边

  • 如果 k 在右边，只递归右边

变量 含义
i 分界线：[left, i-1] 是小于 pivot 的区域，i 是下一个要放的位置
j 扫描员：从左到右检查每个元素
pivot 基准值，选最右边的元素

小的 i 大的 未判断的 temp值 五部分

class Solution {

Random ran=new Random();

public int findKthLargest(int[] nums, int k) {

int tar=nums.length-k;

return quicksort(nums,0,nums.length-1,tar);

}

private int quicksort(int[] nums,int left,int right,int tar){

int temp=left+ran.nextInt(right-left+1);

int tempvalue=nums[temp];

int i=left;

swap(nums,temp,right);

for(int j=left;j<right;j++){

if(nums[j]<tempvalue){

swap(nums,j,i);

i++;

}

}

swap(nums,i,right);

if(i==tar)return nums[i];

else if(i<tar){return quicksort(nums,i+1,right,tar);}

else {return quicksort(nums,left,i-1,tar);}

}

private void swap(int[] nums, int i, int j) {

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

}

}

单词拆分

给一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

思路：动态规划
dp[i]表示前i个字符可以由字典中的字符串拼成
方程：dp[i]=dp[j]&&s.substring[j,i]在字典中

细节：1.直接将字典转哈希->O（1）内contains判断是否存在
2.dp开n+1，不是n， 0占一位 ，字符串长度n 占 n位 所以是n+1
3.dp[0]=true->空字符串可拼成 dp从1取到n

class Solution {

public boolean wordBreak(String s, List wordDict) {

Set set=new HashSet<>(wordDict);

int n=s.length();

boolean[] dp=new boolean[n+1];

dp[0]=true;

for(int i=1;i<=n;i++)

for(int j=0;j<i-1;j++){

if(dp[j]&&set.contains(s.substring(j,i))){

dp[i]=true;

break;

}

}

return dp[n];

}

}

10. 如果系统流量突增10倍，你会如何保障系统稳定？
我会从入口、应用、缓存、数据库四层防护。入口限流熔断，应用扩容隔离，缓存多级抗热，数据库读写分离加异步削峰。最后有降级预案兜底，保证核心业务可用。

11. 请讲一下线程池的核心参数和执行流程。
corePoolSize, // 核心线程数
maximumPoolSize, // 最大线程数
keepAliveTime, // 空闲线程存活时间
unit, // 时间单位
workQueue, // 任务队列
threadFactory, // 线程工厂
handler // 拒绝策略

新任务提交
│
▼
核心线程数满了吗？
│
├─ 没满 → 创建核心线程执行
│
└─ 满了 → 任务队列满了吗？
│
├─ 没满 → 放入队列等待
│
└─ 满了 → 最大线程数满了吗？
│
├─ 没满 → 创建非核心线程执行
│
└─ 满了 → 执行拒绝策略

四种拒绝策略

策略 行为
AbortPolicy 抛异常（默认）
CallerRunsPolicy 调用者线程执行
DiscardPolicy 直接丢弃
DiscardOldestPolicy 丢弃队列最老的任务

12. volatile保证什么？为什么无法保证i++线程安全？

保证 说明
可见性 一个线程修改后，其他线程立即能看到
有序性 禁止指令重排
线程A：读 i=0
线程B：读 i=0
线程A：写 i=1
线程B：写 i=1
结果：i=1，而不是 2
volatile 只保证"读到的值是最新的"，但不保证"读-改-写"这个复合操作原子。

不保证原子性。

解决方案：

  • AtomicInteger（CAS）

  • synchronized

13. ConcurrentHashMap线程安全的原理是什么？JDK1.7与1.8有哪些差异？

JDK 1.7：分段锁

  • 分成多个 Segment，每个 Segment 独立加锁

  • 不同 Segment 可以并发访问

  • 锁粒度：Segment

JDK 1.8：CAS + synchronized

ConcurrentHashMap
└─ Node 数组
├─ 空节点 → CAS 插入
└─ 非空节点 → synchronized 锁头节点

  • 取消 Segment，直接用 Node 数组

  • 空节点用 CAS

  • 非空节点用 synchronized 锁头节点

  • 锁粒度：单个桶

14. Redis为什么快？单线程模型与IO多路复用原理是什么？

原因 说明
纯内存 纳秒级读写
单线程 无锁、无上下文切换
IO 多路复用 一个线程管理万级连接
高效数据结构 跳表、压缩列表

IO 多路复用

核心：一个线程，一个 epoll，管理所有连接，只处理就绪的。

15. 缓存穿透、击穿、雪崩分别是什么？解决方案有哪些？

问题 含义 解决方案
穿透 查不存在的数据，绕过缓存直击数据库 布隆过滤器、空值缓存
击穿 热点 key 过期，大量请求直击数据库 互斥锁、逻辑过期
雪崩 大量 key 同时过期，数据库压力暴增 过期时间加随机、多级缓存、熔断降级

  • 互斥锁：只让一个请求查数据库，其他等待

  • 逻辑过期：不设 TTL，用逻辑判断是否过期

16. MySQL为什么选用B+树？什么是聚簇索引、回表、覆盖索引？
B+ 树优势：

  • 非叶子节点只存索引，不存数据，一个节点能存更多索引，树更矮

  • 叶子节点用链表连接，范围查询快

  • 所有查询都到叶子节点，性能稳定

17. 线上SQL耗时从20ms突增到2s，排查思路是什么？

  1. 确认问题
    ├─ 慢查询日志：找到具体 SQL
    └─ EXPLAIN：看执行计划

  2. 检查索引
    ├─ 是否走索引？
    ├─ 索引是否失效？
    └─ 是否有新 SQL 没建索引？

  3. 检查数据量
    ├─ 表数据是否突增？
    └─ 是否有大量写入？

  4. 检查锁
    ├─ 是否有锁等待？
    └─ SHOW PROCESSLIST 看阻塞

  5. 检查数据库负载
    ├─ CPU、内存、磁盘 IO
    └─ 连接数是否打满

  6. 检查外部因素
    ├─ 网络延迟？
    ├─ 从库延迟？
    └─ 是否有大事务？

  7. 解决方案
    ├─ 加索引
    ├─ 优化 SQL
    ├─ 分库分表
    └─ 读写分离

18. 请设计一个TikTok直播间点赞系统。

┌─────────────────────────────────────────────────────────────┐
│ 客户端 │
│ （点赞按钮） │
└───────────────────────────┬─────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────┐
│ API 网关 │
│ 限流、鉴权、防刷 │
└───────────────────────────┬─────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────┐
│ 点赞服务 │
│ │
│ 1. 用户点赞 → Redis 计数 +1 │
│ 2. 异步写 MQ │
│ 3. 返回成功 │
│ │
└───────────────────────────┬─────────────────────────────────┘
│
┌─────────────┼─────────────┐
│ │ │
▼ ▼ ▼
┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐
│ Redis │ │ MQ │ │ 数据库 │
│ │ │ │ │ │
│ 点赞计数 │ │ 异步削峰 │ │ 持久化 │
│ INCR key │ │ 批量写入 │ │ 点赞记录 │
│ │ │ │ │ │
└─────────────────┘ └─────────────────┘ └─────────────────┘

需求分析

  • 高并发：一个直播间可能百万级点赞

  • 低延迟：点赞要实时反馈

  • 数据一致性：最终一致即可

  • 防刷：防止恶意刷赞

核心设计

1. 点赞计数用 Redis

INCR like:room:123

  • 原子操作，高并发安全

  • 内存操作，纳秒级

2. 防刷

  • 用户 ID + 直播间 ID 做去重

  • 用 Redis Set 记录已点赞用户

  • 限流：每个用户每秒最多点 10 次

3. 异步持久化

  • 点赞后发 MQ

  • 消费者批量写入数据库

  • 最终一致

4. 实时展示

  • 前端轮询或 WebSocket

  • 从 Redis 读计数

5. 热点问题

  • 单个直播间点赞量极大

  • 可以分片：like:room:123:shard1、shard2

  • 汇总时相加