数据结构与算法 面试题

这个方向在考什么

• 复杂度分析：均摊分析、空间换时间、哈希查询在什么情况下退化
• 结构选型：堆 / 有序表 / 并查集 / 前缀树，各自解决哪类问题
• 动态规划：状态怎么设计、边界怎么定、能不能滚动数组
• 工程场景：海量数据 Top-K、去重、限流、缓存淘汰分别用什么结构

最常见的几个坑

• 上来就写代码，不说思路和复杂度，面试官无法判断你的思考过程
• 忽略边界：空输入、单元素、重复元素、整数溢出
• 复杂度算错：嵌套循环里哈希查询是 O(1)，但哈希冲突时不是

七天准备路线

1. 第 1-3 天按类型刷高频题（数组/链表/树/图/DP），每题写复杂度
2. 第 4 天结构选型专题：把"什么场景用什么结构"整理成一张表
3. 第 5 天练手写：白板写代码，边说边写，控制在 15 分钟内
4. 第 6-7 天模拟面试：让朋友随机出题，重点练"先讲思路再写"

数据结构与算法高频面试题

• 有个排行榜模块：N=10^6 个用户按分数从高到低存在一个容器里，读取非常频繁（每秒约 10^5 次「取第 k 名」和「取某用户的排名」），写入很少（每秒约 10 次插入/删除，插入位置随机分布在容器中部）。同事建议用双向链表，理由是插入删除 O(1)；你倾向用哪一种？请从内存布局、常数开销和这两类操作的实际耗时量级给出判断依据。 · 1-3 年
• 内存里要维护 50 万条按时间排序的订单快照，需要支持三种操作：① 按下标随机读取（约 5000 QPS，要拿到第 k 早的订单）；② 在任意位置插入新订单（约 200 次/秒，插入位置在 [0, 50万] 上近似均匀分布）；③ 按订单号删除（约 200 次/秒，位置同样近似均匀分布）。你会选动态数组还是双向链表？请给出量化判断依据：涉及哪些开销、量级差多少。如果业务要求三种操作都不能慢，你会怎么改造这个结构？ · 3-5 年
• 某服务在内存里维护一份“最近 N 条记录”的有序表（N=100 万，单条记录 64B），线上埋点统计的操作占比是：尾部追加 90%，按序号随机读取 9%，在中间指定位置插入或删除 1%。现有实现是动态数组，中间插入需要 memmove 平均约 50 万条记录（约 32MB）。有同学提议整体换成双向链表，理由是“链表插入删除是 O(1)”。作为技术负责人，你怎么做这个决策？请给出你的判断依据、你要补测的数据，以及最终方案。 · 5 年以上
• 在一个长度为 100 万的整型序列上，需要执行 10 万次操作。其中 90% 是在序列头部插入一个元素，10% 是按索引随机读取一个元素。你会选择数组还是单链表？请分别估算两种选择下这 10 万次操作的相对代价（不需要精确时间，说明量级即可）。如果把比例改成 90% 随机读取、10% 头部插入，你的选择会变吗？为什么？ · 校招
• 给你一个长度 n=10^7 的整数数组和一个固定窗口大小 k=1000，要求输出每个窗口内的最大值，总时间必须是 O(n)。你会用什么结构？请具体说明：队列里存元素值还是下标、什么时候从队尾弹出、队首元素什么时候失效、以及为什么这套操作合起来是 O(n) 而不是 O(nk)。 · 1-3 年
• 一个下单服务每秒产生约 8 万条事件，由一个后台线程批量拉取（每 50ms 一次）后写下游消息队列。缓冲放在进程内存里，消费者偶发卡顿 2~3 秒。请给出你选的有界队列实现和容量参数：为什么不用无界的 LinkedBlockingQueue？容量大概设多少、内存占多少？消费者卡顿 3 秒导致队列满时，你的策略是阻塞生产者、丢弃、还是落盘？如果改成单生产者单消费者的无锁环形缓冲区，生产者和消费者各需要维护什么状态，怎么判断'空'和'满'？ · 3-5 年
• 某异步任务系统在流水线各阶段之间用内存队列做缓冲，当前是无界队列。压测显示上游峰值 QPS 是下游消费能力的 3 倍，大促期间进程被 OOM kill。现在要改成有界队列；同时，流水线的回滚补偿模块需要严格按与执行相反的顺序触发补偿动作。请你说明：队列容量与拒绝策略怎么定（给出你要看的指标和大致算法），回滚补偿用什么结构，以及这件事怎么推动上游团队配合改。 · 5 年以上
• 用两个栈实现一个队列，要求 push 和 pop 的均摊时间复杂度为 O(1)。请描述入队和出队的具体过程。假设初始队列为空，连续执行 5 次入队操作（依次放入 1、2、3、4、5），然后执行 1 次出队，再连续执行 5 次入队（依次放入 6、7、8、9、10），再执行 1 次出队。请写出两个栈在每一步后的状态，以及两次出队分别返回什么元素。 · 校招
• 给你一棵二叉树的节点值序列（节点值有重复）：前序遍历 pr = [3, 9, 3, 1, 20, 15, 7]，中序遍历 in = [3, 9, 1, 3, 15, 20, 7]。请问：只用这两组序列，能否唯一确定这棵树？说明你的判断过程，并给出一个能构造出来的具体反例；如果要让代码支持这种情况，你会怎么改。 · 1-3 年
• 线上有一棵组织关系树，约 2000 万个节点，每个节点子节点数最多 50，深度最深可能上万层。现在要把整棵树按'层级顺序'导出成文件（同一层的节点写在一起），进程可用堆内存 4GB。你会选 BFS 还是 DFS？BFS 队列的峰值会到多大、4GB 放不放得下？如果业务改成'每个节点必须先输出它的所有子节点、再输出自己'，你的方案要怎么变？ · 3-5 年
• 某规则引擎把业务方配置的表达式解析成二叉树，用递归做后序遍历求值。线上出现一个极深（几十万层嵌套）的表达式，递归导致栈溢出把整个服务打挂；同时业务方要求报错时能看到从根到出错节点的完整路径。请说明：遍历实现怎么改，深度防护怎么设计，以及“表达式不能超过 N 层”这条约束你怎么和业务方谈。 · 5 年以上
• 给定一棵二叉树的先序遍历序列为 A B D E C F G，中序遍历序列为 D B E A F C G。请还原这棵二叉树，并写出它的后序遍历序列。要求写出递归划分的过程：每一步先序的根是谁，中序中哪些元素属于左子树、哪些属于右子树，而不是只给最终答案。 · 校招
• 从 n = 10^8 个 int（约 400MB，内存装不下全部）的数据流里找出最大的 K = 100 个数，数据只能流式读取。说说你的方案、时间复杂度和空间复杂度，并解释：为什么这里要用最小堆而不是最大堆？ · 1-3 年
• 一个定时任务系统常驻 100 万个待触发任务，按触发时间排序，每秒新增 2000 个、触发 2000 个。业务还要求能按 taskId 取消任务，取消率约 5%，且被取消的任务大多还没到期。你用二叉堆怎么实现？直接遍历堆去找 taskId 的代价是多少？如果不想付这个代价，你会怎么设计？ · 3-5 年
• 某延时消息系统用单个最小堆（优先队列）管理约 5000 万条待触发消息，支持按消息 ID 取消。运营反馈三个问题：常驻内存 8GB 以上；大量取消后堆里堆着已失效的节点，pop 出来还要丢弃；高峰期定时线程 push 和 pop 抢同一把锁。让你定这条线未来两个季度的演进路线：是继续优化这个堆，还是换成时间轮？给出判断依据、分阶段方案，并说明怎么在不重写的前提下演进。 · 5 年以上
• 有一个小顶堆，用数组存储为 [3, 8, 10, 15, 20, 18, 12]。现在执行一次 pop（取出堆顶元素）。请写出取出堆顶后堆的调整过程，并给出调整后的数组。要求说明：小顶堆的堆序性质是什么？调整时每次和哪个孩子交换？为什么？ · 校招
• 维护一张只有加边、没有删边的无向图：节点数 10^6，边会分 10^7 次陆续加入，加入过程中随时可能被问「u 和 v 是否连通」。你选什么数据结构？请写出 find 的核心实现（含路径压缩），并回答：只做路径压缩、不做按秩合并，够不够用？为什么？ · 1-3 年
• 有一个每天批量导入的账户关联数据：约 1000 万个账户，每天新增 200 万条'这两个账户属于同一个人'的边，导入完成后要在线回答'这两个账户是不是同一个人'，查询约 5000 QPS。你会用并查集，还是每次查询做一次图搜索？如果用并查集，路径压缩和按秩合并分别解决什么问题？如果业务后来要求支持'撤销某条关联'，这个结构还能用吗？ · 3-5 年
• 某数据平台做跨数据源的实体归一：把判定为同一实体的记录合并成连通分量，规模约 10 亿实体，日均新增约 1 亿条“合并”边。新需求是：随时回答任意两个 ID 是否属于同一实体；运营发现误判时能撤销某一条历史合并；每天还要全量重算一次。现有实现是并查集加路径压缩。你怎么设计这套存储与查询，怎么支持撤销，以及为什么保留或不保留全量重算？ · 5 年以上
• 有 6 个元素 {0,1,2,3,4,5}，初始每个元素单独一个集合，parent[i]=i，rank[i]=0。依次执行：union(0,1)、union(2,3)、union(1,3)、union(4,5)。采用按秩合并（rank 相同时把后一个根挂到前一个根）和路径压缩。请写出每次 union 操作后的 parent 数组。然后执行 find(3)，写出路径压缩后的 parent 数组。 · 校招

共 80 道，这里列出前 20 道。 去题库检索