维护一张只有加边、没有删边的无向图：节点数 10^6，边会分 10^7 次陆续加入，加入过程中随时可能被问「u 和 v 是否连通」。你选什么数据结构？请写出 find 的核心实现（含路径压缩），并回答：只做路径压缩、不做按秩合并，够不够用？为什么？

面试官在考什么

判断候选人是否真正写过并查集，是否理解路径压缩与按秩合并各自解决什么问题，以及递归实现的风险。

并查集

回答框架 · 前两步

1. 并查集：parent 数组初始化为 parent[i] = i；find(x) 沿父指针上溯到根；union(a,b) 先各自找根，再把一个根挂到另一个根下面；查询连通性就是比较两个根是否相同。
2. 路径压缩：find 的过程中把路径上所有节点直接挂到根上（迭代写法或两趟循环），使后续查找几乎一步到位。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 有个排行榜模块：N=10^6 个用户按分数从高到低存在一个容器里，读取非常频繁（每秒约 10^5 次「取第 k 名」和「取某用户的排名」），写入很少（每秒约 10 次插入/删除，插入位置随机分布在容器中部）。同事建议用双向链表，理由是插入删除 O(1)；你倾向用哪一种？请从内存布局、常数开销和这两类操作的实际耗时量级给出判断依据。
• 内存里要维护 50 万条按时间排序的订单快照，需要支持三种操作：① 按下标随机读取（约 5000 QPS，要拿到第 k 早的订单）；② 在任意位置插入新订单（约 200 次/秒，插入位置在 [0, 50万] 上近似均匀分布）；③ 按订单号删除（约 200 次/秒，位置同样近似均匀分布）。你会选动态数组还是双向链表？请给出量化判断依据：涉及哪些开销、量级差多少。如果业务要求三种操作都不能慢，你会怎么改造这个结构？
• 某服务在内存里维护一份“最近 N 条记录”的有序表（N=100 万，单条记录 64B），线上埋点统计的操作占比是：尾部追加 90%，按序号随机读取 9%，在中间指定位置插入或删除 1%。现有实现是动态数组，中间插入需要 memmove 平均约 50 万条记录（约 32MB）。有同学提议整体换成双向链表，理由是“链表插入删除是 O(1)”。作为技术负责人，你怎么做这个决策？请给出你的判断依据、你要补测的数据，以及最终方案。
• 在一个长度为 100 万的整型序列上，需要执行 10 万次操作。其中 90% 是在序列头部插入一个元素，10% 是按索引随机读取一个元素。你会选择数组还是单链表？请分别估算两种选择下这 10 万次操作的相对代价（不需要精确时间，说明量级即可）。如果把比例改成 90% 随机读取、10% 头部插入，你的选择会变吗？为什么？
• 给你一个长度 n=10^7 的整数数组和一个固定窗口大小 k=1000，要求输出每个窗口内的最大值，总时间必须是 O(n)。你会用什么结构？请具体说明：队列里存元素值还是下标、什么时候从队尾弹出、队首元素什么时候失效、以及为什么这套操作合起来是 O(n) 而不是 O(nk)。
• 一个下单服务每秒产生约 8 万条事件，由一个后台线程批量拉取（每 50ms 一次）后写下游消息队列。缓冲放在进程内存里，消费者偶发卡顿 2~3 秒。请给出你选的有界队列实现和容量参数：为什么不用无界的 LinkedBlockingQueue？容量大概设多少、内存占多少？消费者卡顿 3 秒导致队列满时，你的策略是阻塞生产者、丢弃、还是落盘？如果改成单生产者单消费者的无锁环形缓冲区，生产者和消费者各需要维护什么状态，怎么判断'空'和'满'？