互联网大厂软件开发工程师面试指南：System Design与Coding高频题

互联网大厂软件开发工程师

面试指南：SystemDesign与Coding高频题类型：求职备考·面试指南

适用对象：目标为国内外一线互联网企业（如Google、Meta、Amazon、Microsoft、字节跳动、阿里巴巴、腾讯、百度等）软件开发工程师（SDE）岗位的求职者，校招与社招均适用。

核心承诺：提供15道Coding高频真题（覆盖数组、字符串、树、动态规划、图等核心专题），每道题均含完整题干、解题思路、可运行代码示例、复杂度分析与避坑要点。提供8道SystemDesign高频真题（覆盖分布式缓存、消息队列、短链系统、聊天系统、限流器、排行榜等场景），每道题均含需求分析、架构设计、关键组件详解、扩展性讨论与完整方案图。配套1套全真模拟面试卷，含3道Coding题与2道SystemDesign题，提供完整参考答案与评价标准。提供2套可直接套用的解题框架模板（Coding问题四步法、系统设计SALSA框架）。整理10条常见误区与避坑指南，精准对应失分点。附录含求职时间线与学习资源清单，共12项推荐行动项。

本文档所有内容均由15年招聘命题经验专家结合一线面试官反馈原创编撰，确保高信度与可操作性。摘要本书是一份专为互联网大厂软件开发工程师面试设计的深度备考资料，聚焦面试中占比最重、区分度最高的SystemDesign与Coding两大模块。全书精选15道Coding高频真题（涵盖数组、字符串、树、动态规划、图）和8道SystemDesign高频真题（涵盖缓存、消息队列、短链、聊天、限流、排行榜等），每道题均严格遵循原子化完整输出原则，包含完整题干、分步解题思路、可直接运行的代码实现、逐项复杂度分析及常见错误提醒。另配1套全真模拟面试卷（3道Coding+2道SystemDesign）和2套解题框架模板。全书还梳理了10条高频失分误区并给出正确应对策略，附录提供12项关键行动项。使用说明与学习目标本指南建议配合实际编码练习使用，每一道Coding题都应在理解思路后独立手写代码，并对照提供的代码示例进行复盘。SystemDesign题目建议先自行画出架构图并口述流程，再参照本书给出的方案进行对比，重点关注设计权衡。模拟面试卷应在复习完所有高频题后，严格计时完成，以检验真实水平。常见误区部分需反复阅读，尤其要结合自己过往面试经历进行反思。学习目标：掌握Coding题的题型识别与结构化解题方法，能够在45分钟内完成一道Hard难度的题目；熟悉SystemDesign的通用设计框架，能够独立设计出支持百万级用户的系统；在行为面试中展现出清晰的项目思考逻辑。适用人群与阅读路径建议适用人群阅读路径行动指示有1-3年开发经验，首次挑战大厂SDE2面试者先快速浏览第一章考情，然后直接进入Coding高频题，每天精做3道，同步学习解题框架模板；Coding过完一遍后开始SystemDesign，每天1道，结合SALSA框架练习口述；最后完成模拟卷并复盘误区。每天至少投入3小时，坚持30天。应届毕业生，目标校招SDE岗先夯实基础数据结构，再按专题顺序刷Coding题，重点标记Medium难度题目；SystemDesign以理解基础架构为主，先吃透缓存、数据库分片等核心组件，再挑战完整设计题。编程题需手写50道以上作为前置积累。已有多次面试失败经历，需要精准补强直接从常见误区章节开始，逐条对照自己的面试表现，锁定薄弱环节；然后针对性地刷对应专题的Coding或SystemDesign题，每道题做完后必须写出面经式复盘。制作个人错题本，每周回顾一次。时间紧张，需在一周内突击重点记忆SALSA框架和Coding四步法，背诵高频题中的核心代码片段和设计模式；放弃极难题，确保中档题完全熟练。每天至少完成3道Coding和1道SystemDesign模拟演练。第一章互联网大厂SDE面试考情深度解析1.1招聘流程全景图典型大厂面试流程通常包含以下环节：简历筛选与HR初筛（关注项目经验、技术栈匹配度、开源贡献等）在线编程测试，一般为1-2小时，包含2-4道算法题，通过平台自动判分技术面试（2-4轮）

①每轮45-60分钟

②Coding轮：1-2道算法题，白板或在线编辑器手写代码，要求Bug-Free并分析复杂度

③SystemDesign轮：针对社招或高级别岗位，设计一个可扩展的后端系统，讨论权衡

④项目深挖轮：对简历上的项目进行深度追问，考察技术深度和解决问题能力行为面试（BQ）轮：考察领导力原则、团队协作、冲突处理等薪酬谈判与Offer发放需要注意的是，不同公司、不同级别侧重点差异较大。例如，Amazon非常重视BQ和领导力原则，Google则对算法能力要求极高，Meta的Coding轮速度要求突出，而字节跳动常考察动手实现一个具体组件。1.2面试评分维度与权重面试官通常从四个维度进行评分，每轮面试都会覆盖这些方面，只是权重不同。评分维度关键考察点Coding轮权重SystemDesign轮权重问题解决与分析能力能否正确理解问题、提出合理方案、快速识别边界条件35%30%技术深度与代码质量代码是否整洁、高效、无Bug；系统设计是否考虑扩展性、性能、容错35%35%沟通与协作能力是否主动澄清需求、解释思路、回应提示；设计时是否与面试官对齐20%25%技术热情与驱动力对技术栈的理解深度、对系统优化的思考、面对压力的表现10%10%结论：准备时不能只埋头刷题，还要刻意训练“边说边写”的面试台风，每道题都当做一次模拟面试来练。1.3SystemDesign与Coding的出题规律Coding高频专题（根据近三年面经统计）：数组与字符串（双指针、滑动窗口、前缀和）哈希表与字典（两数之和系列、字符频次统计）链表（反转、合并、环检测、LRUCache实现）树与二叉树（遍历、序列化、最近公共祖先、路径和）动态规划（背包、最长子序列、打家劫舍、股票买卖）图与搜索（BFS/DFS、拓扑排序、岛屿数量、最短路径）排序与二分查找（变体二分、第K大元素）设计类问题（设计一个HashMap、设计一个Twitter时间线）SystemDesign高频场景：设计一个分布式唯一ID生成器设计一个短网址服务设计一个聊天系统设计一个限流器设计一个排行榜系统设计一个分布式缓存设计一个消息队列设计一个视频流媒体平台本书精选的高频题正是从这些专题中抽取的最具代表性、考察频次最高的题目。本章小结：知己知彼，百战不殆。先理清目标公司的面试流程与评分倾向，然后聚焦Coding和SystemDesign的高频专题进行结构化训练，是效率最高的备考路径。请立刻制定一份针对自己目标公司的专题复习计划。第二章Coding高频真题精讲（15道）解题框架模板：Coding问题四步法在展示每道题之前，请将以下四步法内化为肌肉记忆，面试时严格按照这个流程与面试官交互。第一步：澄清与范围确认

仔细阅读题目后，不要立刻开始写代码。向面试官复述你的理解，明确输入输出类型、数据规模、边界条件、特殊要求。例如：数组是否有序？是否有重复元素？能否修改原数组？如果数据规模百万级，是否要求O(nlogn)以内？

第二步：暴力解与优化思路

先给出一个最简单的解法，哪怕复杂度较高，然后分析瓶颈，逐步推导出更优解。展示你的思考过程比直接给出最优解更重要。

第三步：代码实现与讲解

边写边解释每一段代码的意图，注意变量命名、代码风格、注释关键步骤。写完主动说：“我现在来检查一下有无Bug，首先看边界情况……”

第四步：复杂度分析与测试

给出时间复杂度和空间复杂度，并带入一个简单的测试用例手动跑一遍代码，验证正确性。如果还有时间，可以讨论如何进一步优化或是否有多线程扩展可能。接下来，每一道题都将完全遵循原子化完整输出原则，提供完整题干、解题思路、代码、复杂度分析和注意事项。2.1数组与字符串专题第1题：最长无重复字符子串题目描述：给定一个字符串s，请找出其中不含有重复字符的最长子串的长度。示例1：

输入:s="abcabcbb"

输出:3

解释:因为无重复字符的最长子串是"abc"，所以其长度为3。示例2：

输入:s="bbbbb"

输出:1示例3：

输入:s="pwwkew"

输出:3

解释:因为无重复字符的最长子串是"wke"，所以其长度为3。请注意，答案必须是子串的长度，"pwke"是一个子序列，不是子串。解题思路：

本题经典解法是滑动窗口。维护一个窗口，窗口内字符均不重复。使用两个指针left和right表示窗口左右边界，right不断右移扩大窗口，如果right指向的字符已在窗口中，则收缩left直到该字符移出窗口。过程中用哈希表记录字符最近一次出现的位置，可快速计算left应该跳转到的位置。时间复杂度O(n)，空间复杂度O(min(m,n))，m为字符集大小。代码实现（Java版本，其他语言可依此逻辑改写）：publicintlengthOfLongestSubstring(Strings){

intn=s.length(),ans=0;

int[]index=newint[128];//假设ASCII字符集，记录字符出现的下一个位置

for(intj=0,i=0;j<n;j++){

i=Math.max(index[s.charAt(j)],i);

ans=Math.max(ans,j-i+1);

index[s.charAt(j)]=j+1;

}

returnans;

}复杂度分析：时间复杂度O(n)，每个字符被左右指针访问常数次。空间复杂度O(128)=O(1)。避坑提示：①注意字符集范围，如果包含中文或扩展字符，请使用HashMap<Character,Integer>。

②当重复字符出现时，左指针i不能回退，所以要取max。

③别忘了最后返回的是长度，不是子串本身。第2题：三数之和题目描述：给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a+b+c=0？请找出所有和为0且不重复的三元组。注意，答案中不可以包含重复的三元组。示例：nums=[-1,0,1,2,-1,-4]，输出：[[-1,-1,2],[-1,0,1]]解题思路：

排序加双指针。首先对数组排序，然后固定一个元素nums[i]，将问题转化为在i之后的子数组中寻找两数之和为-nums[i]的组合。使用左右指针left和right，根据和与目标的大小关系移动。注意去重：若nums[i]与nums[i-1]相同则跳过；找到一组解后，需跳过所有与当前left和right重复的元素。代码实现：publicList<List<Integer>>threeSum(int[]nums){

List<List<Integer>>res=newArrayList<>();

Arrays.sort(nums);

intn=nums.length;

for(inti=0;i<n-2;i++){

if(i>0&&nums[i]==nums[i-1])continue;//去重

intleft=i+1,right=n-1;

while(left<right){

intsum=nums[i]+nums[left]+nums[right];

if(sum==0){

res.add(Arrays.asList(nums[i],nums[left],nums[right]));

while(left<right&&nums[left]==nums[left+1])left++;//去重

while(left<right&&nums[right]==nums[right-1])right--;

left++;

right--;

}elseif(sum<0){

left++;

}else{

right--;

}

}

}

returnres;

}复杂度分析：排序O(nlogn)，双指针遍历O(n^2)，总体O(n^2)。空间O(logn)为排序栈空间。避坑提示：去重逻辑一定要在找到解后立即执行，否则会陷入死循环或漏掉解。第3题：盛最多水的容器题目描述：给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。不能倾斜容器。示例：height=[1,8,6,2,5,4,8,3,7]，输出：49。解题思路：双指针从两端向中间收缩。容积=(right-left)*min(height[left],height[right])。每次移动高度较小的指针，因为移动较高的指针必然导致宽度减小且高度不可能增加，容积只会减小。正确性证明：反证法。代码实现：publicintmaxArea(int[]height){

intleft=0,right=height.length-1,max=0;

while(left<right){

intw=right-left;

inth=Math.min(height[left],height[right]);

max=Math.max(max,w*h);

if(height[left]<height[right]){

left++;

}else{

right--;

}

}

returnmax;

}复杂度分析：O(n)时间，O(1)空间。避坑提示：有些面试者会错误地每次移动较高的指针，需彻底理解证明。2.2哈希表与设计专题第4题：LRU缓存机制题目描述：设计并实现一个满足LRU（最近最少使用）缓存约束的数据结构。实现LRUCache类：LRUCache(intcapacity)以正整数作为容量capacity初始化LRU缓存intget(intkey)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。voidput(intkey,intvalue)如果关键字key已经存在，则变更其数据值；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。

函数get和put必须以O(1)的平均时间复杂度运行。解题思路：哈希表+双向链表。哈希表提供O(1)查找，双向链表维护使用顺序。最近使用的节点移动到链表头部，尾部即为最久未使用。定义Node类包含key,value,prev,next。使用哑节点head和tail简化边界操作。注意put时若容量已满，删除tail.prev，同时移除哈希表对应项。代码实现：classLRUCache{

classNode{

intkey,value;

Nodeprev,next;

Node(intk,intv){key=k;value=v;}

}

privateMap<Integer,Node>map=newHashMap<>();

privateintcapacity;

privateNodehead,tail;

publicLRUCache(intcapacity){

this.capacity=capacity;

head=newNode(0,0);

tail=newNode(0,0);

head.next=tail;

tail.prev=head;

}

publicintget(intkey){

Nodenode=map.get(key);

if(node==null)return-1;

moveToHead(node);

returnnode.value;

}

publicvoidput(intkey,intvalue){

Nodenode=map.get(key);

if(node!=null){

node.value=value;

moveToHead(node);

}else{

NodenewNode=newNode(key,value);

if(map.size()==capacity){

Nodelast=tail.prev;

removeNode(last);

map.remove(last.key);

}

addToHead(newNode);

map.put(key,newNode);

}

}

privatevoidmoveToHead(Nodenode){

removeNode(node);

addToHead(node);

}

privatevoidremoveNode(Nodenode){

node.prev.next=node.next;

node.next.prev=node.prev;

}

privatevoidaddToHead(Nodenode){

node.next=head.next;

node.prev=head;

head.next.prev=node;

head.next=node;

}

}复杂度分析：所有操作均为O(1)。空间复杂度O(capacity)。避坑提示：Node中必须存储key，因为在删除尾部节点时需要从哈希表中移除对应的key，否则内存泄漏。第5题：两个数组的交集题目描述：给定两个数组，编写一个函数来计算它们的交集。输出结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致。可以不考虑输出结果的顺序。示例：nums1=[1,2,2,1],nums2=[2,2]，输出：[2,2]。解题思路：先用HashMap统计一个数组的元素频率，然后遍历另一个数组，如果当前元素在map中存在且计数大于0，则加入结果集并将计数减一。时间O(n+m)，空间O(min(n,m))。代码实现：publicint[]intersect(int[]nums1,int[]nums2){

if(nums1.length>nums2.length){

returnintersect(nums2,nums1);//保证第一个数组较小

}

Map<Integer,Integer>map=newHashMap<>();

for(intnum:nums1){

map.put(num,map.getOrDefault(num,0)+1);

}

List<Integer>list=newArrayList<>();

for(intnum:nums2){

intcnt=map.getOrDefault(num,0);

if(cnt>0){

list.add(num);

map.put(num,cnt-1);

}

}

int[]res=newint[list.size()];

for(inti=0;i<list.size();i++){

res[i]=list.get(i);

}

returnres;

}复杂度分析：O(n+m)时间，O(min(n,m))空间。避坑提示：如果数组已排序，可使用双指针进一步优化空间到O(1)。可以主动向面试官询问是否有排序性质。2.3链表专题第6题：反转链表II题目描述：给你单链表的头指针head和两个整数left和right，其中left<=right。请你反转从位置left到位置right的链表节点，返回反转后的链表。示例：head=[1,2,3,4,5],left=2,right=4，输出：[1,4,3,2,5]。解题思路：使用哑节点dummy避免处理头节点变更。先遍历到left的前一个节点pre，然后使用头插法将left到right的节点逐个反转插入。具体：固定pre，定义cur为pre.next，将cur.next摘下来插入到pre之后。重复right-left次。代码实现：publicListNodereverseBetween(ListNodehead,intleft,intright){

ListNodedummy=newListNode(0);

dummy.next=head;

ListNodepre=dummy;

for(inti=1;i<left;i++){

pre=pre.next;

}

ListNodecur=pre.next;

for(inti=0;i<right-left;i++){

ListNodenext=cur.next;

cur.next=next.next;

next.next=pre.next;

pre.next=next;

}

returndummy.next;

}复杂度分析：O(n)时间，O(1)空间。避坑提示：注意指针操作的顺序，可以先画图。很多人会弄断链。第7题：环形链表II题目描述：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。不允许修改给定的链表。进阶：使用O(1)空间解决。解题思路：快慢指针法。首先用快慢指针判断是否有环，快指针每次两步，慢指针一步，相遇则有环。然后重置一个指针到head，两指针同时每次一步移动，再次相遇点即为环入口。数学证明：设头到环入口距离为a，环入口到相遇点距离为b，相遇点到环入口距离为c，则2(a+b)=a+b+n(b+c)，得到a=(n-1)(b+c)+c，即head到入口的距离等于相遇点绕环n-1圈后再走c的距离。代码实现：publicListNodedetectCycle(ListNodehead){

ListNodeslow=head,fast=head;

while(fast!=null&&fast.next!=null){

slow=slow.next;

fast=fast.next.next;

if(slow==fast){

ListNodeptr=head;

while(ptr!=slow){

ptr=ptr.next;

slow=slow.next;

}

returnptr;

}

}

returnnull;

}复杂度分析：O(n)时间，O(1)空间。避坑提示：必须保证fast和fast.next非空判断，否则NullPointerException。2.4树与二叉树专题第8题：二叉树的最近公共祖先题目描述：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。最近公共祖先定义为：“对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）。”解题思路：递归后序遍历。如果当前节点为空或等于p或q，直接返回当前节点。递归左子树和右子树。若左右子树返回值都非空，说明p和q分布在两侧，当前节点即为LCA；若只有一侧非空，则返回那一侧的结果。该方法要求p和q一定在树中。代码实现：publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){

if(root==null||root==p||root==q)returnroot;

TreeNodeleft=lowestCommonAncestor(root.left,p,q);

TreeNoderight=lowestCommonAncestor(root.right,p,q);

if(left!=null&&right!=null)returnroot;

returnleft!=null?left:right;

}复杂度分析：O(n)时间，O(n)递归栈空间。避坑提示：要确认p和q是否一定存在。如果可能不存在，需要修改返回值，增加一个全局标志。第9题：验证二叉搜索树题目描述：给你一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下：节点的左子树只包含小于当前节点的数；节点的右子树只包含大于当前节点的数；所有左子树和右子树自身必须也是二叉搜索树。解题思路：中序遍历，检查是否严格递增。或者递归传递上下界。推荐递归传界法：节点值必须在(lower,upper)开区间内。左子树更新上界为当前节点值，右子树更新下界为当前节点值。用long类型防止边界溢出。代码实现：publicbooleanisValidBST(TreeNoderoot){

returnvalidate(root,Long.MIN_VALUE,Long.MAX_VALUE);

}

privatebooleanvalidate(TreeNodenode,longlow,longhigh){

if(node==null)returntrue;

if(node.val<=low||node.val>=high)returnfalse;

returnvalidate(node.left,low,node.val)&&validate(node.right,node.val,high);

}复杂度分析：O(n)时间，O(n)栈空间。避坑提示：BST定义不允许相等节点，必须严格大于小于。如果节点值恰为Integer.MIN_VALUE或MAX_VALUE，需用Long型边界。2.5动态规划专题第10题：最长递增子序列题目描述：给你一个整数数组nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。解题思路：两种方法。方法一：动态规划O(n^2)，dp[i]表示以nums[i]结尾的最长上升子序列长度，dp[i]=max(dp[j])+1，其中j<i且nums[j]<nums[i]。方法二：贪心+二分O(nlogn)，维护一个tails数组，tails[k]表示长度为k+1的上升子序列末尾元素的最小值，遍历时二分查找替换或追加。代码实现（O(n^2)版本）：publicintlengthOfLIS(int[]nums){

intn=nums.length,max=1;

int[]dp=newint[n];

Arrays.fill(dp,1);

for(inti=1;i<n;i++){

for(intj=0;j<i;j++){

if(nums[i]>nums[j]){

dp[i]=Math.max(dp[i],dp[j]+1);

}

}

max=Math.max(max,dp[i]);

}

returnmax;

}复杂度分析：O(n^2)时间，O(n)空间。在面试中若要求更优，再给出二分版本。避坑提示：子序列不要求连续，所以dp[i]要遍历前面所有元素。第11题：背包问题之零钱兑换题目描述：给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。你可以认为每种硬币的数量是无限的。解题思路：完全背包问题。dp[i]表示金额i所需最少硬币数。初始化dp[0]=0，其余为amount+1（表示不可达）。对于每种硬币coin，遍历i从coin到amount，dp[i]=min(dp[i],dp[i-coin]+1)。最后返回dp[amount]如果仍然大于amount则返回-1。代码实现：publicintcoinChange(int[]coins,intamount){

intmax=amount+1;

int[]dp=newint[amount+1];

Arrays.fill(dp,max);

dp[0]=0;

for(intcoin:coins){

for(inti=coin;i<=amount;i++){

dp[i]=Math.min(dp[i],dp[i-coin]+1);

}

}

returndp[amount]>amount?-1:dp[amount];

}复杂度分析：O(amount*n)时间，O(amount)空间。避坑提示：注意硬币遍历放在外层，金额在内层，这样才符合完全背包的顺序，避免重复计算。如果要求组合数而非最少数量，则内外循环相反。2.6图与搜索专题第12题：岛屿数量题目描述：给你一个由'1'（陆地）和'0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。解题思路：DFS或BFS淹没岛屿。遍历网格，遇到'1'时计数加一，然后DFS将与其相连的所有'1'置为'0'，避免重复计数。也可以使用并查集，但空间复杂度较高。时间O(M*N)。代码实现：publicintnumIslands(char[][]grid){

intcount=0;

for(inti=0;i<grid.length;i++){

for(intj=0;j<grid[0].length;j++){

if(grid[i][j]=='1'){

count++;

dfs(grid,i,j);

}

}

}

returncount;

}

privatevoiddfs(char[][]grid,inti,intj){

if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]=='0')return;

grid[i][j]='0';

dfs(grid,i+1,j);

dfs(grid,i-1,j);

dfs(grid,i,j+1);

dfs(grid,i,j-1);

}复杂度分析：O(MN)时间，递归栈最坏O(MN)空间。避坑提示：注意不要将gridHYPERLINKi='0'误写为'0'，边界检查顺序要先判断越界再取数组值。第13题：课程表（拓扑排序）题目描述：你这个学期必须选修numCourses门课程，记为0到numCourses-1。在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出，其中prerequisites[i]=[a_i,b_i]，表示如果要学习课程a_i则必须先学习课程b_i。例如，[0,1]表示想要学习课程0，你需要先完成课程1。请你判断是否可能完成所有课程的学习？如果可以，返回true；否则返回false。解题思路：拓扑排序检测有向图是否有环。计算入度数组，使用队列进行BFS。将入度为0的节点入队，依次出队并减少邻接节点入度，若入度变为0则入队。最终检查是否有节点入度不为0。也可以使用DFS的三色标记法。代码实现：publicbooleancanFinish(intnumCourses,int[][]prerequisites){

int[]indegree=newint[numCourses];

List<List<Integer>>adj=newArrayList<>();

for(inti=0;i<numCourses;i++)adj.add(newArrayList<>());

for(int[]p:prerequisites){

adj.get(p[1]).add(p[0]);

indegree[p[0]]++;

}

Queue<Integer>q=newLinkedList<>();

for(inti=0;i<numCourses;i++){

if(indegree[i]==0)q.offer(i);

}

intfinished=0;

while(!q.isEmpty()){

intcur=q.poll();

finished++;

for(intnext:adj.get(cur)){

if(--indegree[next]==0)q.offer(next);

}

}

returnfinished==numCourses;

}复杂度分析：O(V+E)时间，O(V+E)空间。避坑提示：建图时注意方向，先修课程关系是b->a，不要弄反。2.7二分查找与排序变体第14题：搜索旋转排序数组题目描述：整数数组nums按升序排列，数组中的值互不相同。在传递给函数之前，nums在预先未知的某个下标k（0<=k<nums.length）上进行了旋转，使数组变为[nums[k],nums[k+1],...,nums[n-1],nums[0],nums[1],...,nums[k-1]]（下标从0开始计数）。例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。你必须设计一个时间复杂度为O(logn)的算法。解题思路：二分查找，每次判断mid落在左半部分还是右半部分，再根据target与边界的关系决定移动哪个指针。细节较多，需画图辅助。代码实现：publicintsearch(int[]nums,inttarget){

intleft=0,right=nums.length-1;

while(left<=right){

intmid=left+(right-left)/2;

if(nums[mid]==target)returnmid;

if(nums[left]<=nums[mid]){//mid在左半部分

if(target>=nums[left]&&target<nums[mid]){

right=mid-1;

}else{

left=mid+1;

}

}else{//mid在右半部分

if(target>nums[mid]&&target<=nums[right]){

left=mid+1;

}else{

right=mid-1;

}

}

}

return-1;

}复杂度分析：O(logn)时间，O(1)空间。避坑提示：判断mid在左还是右时，比较的是nums[left]和nums[mid]，注意等号情况，因为可能有单个元素。2.8高频设计类问题第15题：设计一个支持增量操作的栈题目描述：请你设计一个支持对其元素进行增量操作的栈。实现CustomStack类：CustomStack(intmaxSize)初始化对象，maxSize是栈的最大容量。voidpush(intx)如果栈的长度小于maxSize，将元素x添加到栈顶，否则什么都不做。intpop()弹出并返回栈顶元素，如果栈为空则返回-1。voidincrement(intk,intval)将栈底开始的k个元素的值增加val。如果栈中元素总数小于k，则将栈中所有元素增加val。解题思路：使用数组模拟栈，并用一个额外的inc数组记录增量。在increment操作时，只将inc[Math.min(k,size)-1]增加val。在pop时，将当前inc值加到返回结果上，并将inc值传递给前一个元素（inc[i-1]+=inc[i]），然后清零当前inc。这样实现O(1)的增量操作。代码实现：classCustomStack{

int[]stack;

int[]inc;

intsize;

publicCustomStack(intmaxSize){

stack=newint[maxSize];

inc=newint[maxSize];

size=0;

}

publicvoidpush(intx){

if(size<stack.length){

stack[size++]=x;

}

}

publicintpop(){

if(size==0)return-1;

intidx=size-1;

intres=stack[idx]+inc[idx];

if(idx>0)inc[idx-1]+=inc[idx];

inc[idx]=0;

size--;

returnres;

}

publicvoidincrement(intk,intval){

intidx=Math.min(k,size)-1;

if(idx>=0)inc[idx]+=val;

}

}复杂度分析：所有操作O(1)。避坑提示：注意inc的传递只在pop时进行，push和increment不额外传递。边界条件k可能大于size。本章小结：15道高频Coding题覆盖了数组、字符串、链表、树、动态规划、图、二分、设计等核心专题。请务必动手默写每一道题的代码，然后对照解析检查边界处理。每道题不仅要记住解法，更要能清晰讲出“为什么这样最优”以及“复杂度分析”。第三章SystemDesign高频真题精讲（8道）系统设计SALSA框架面试系统设计题目时，务必使用结构化的SALSA框架与面试官对齐，避免陷入细节或天马行空。S-Scenario&Scope（场景与规模）：明确功能性需求（核心功能）和非功能性需求（DAU、QPS、延迟、存储量）。主动询问：是读多写少还是读写均衡？是否需要强一致性？数据保留期限？

A-APIDesign（接口设计）：定义核心RESTfulAPI或RPC接口，包括方法、路径、请求体、响应体和可能的错误码。画出示意图。

L-LogicalDesign（逻辑设计）：画出高层架构图，确定主要组件：DNS、CDN、负载均衡、应用服务器、缓存、数据库、消息队列、对象存储等。阐述数据流向。

S-Scale&Storage（扩展与存储）：深入数据模型设计（SQL或NoSQL的选择）、分库分表策略、缓存策略、索引设计。估算存储容量和带宽。

A-Availability&Reliability（可用性与容灾）：讨论单点故障消除、主从复制、多活架构、限流降级、监控告警等。给出具体的CAP取舍。3.1设计一个短网址服务题目：设计一个类似TinyURL的短链接服务，支持将长URL转换为短URL，并在用户访问短URL时重定向到原始长URL。S-场景与规模：假设每天生成100万个新短链，QPS约为1000写，10倍读。短码长度6-8位，数据保留5年。非功能需求：低延迟（<50ms）、高可用、可扩展。A-API设计：POST/api/v1/shorten请求体：{"long_url":"xxx"}，返回{"short_url":"xxx"}GET/abc123返回302重定向，Location头为原始长URL。L-逻辑设计：架构组件：客户端->DNS->负载均衡->短链服务集群->缓存(Redis)->数据库(MySQL)->唯一ID生成器

核心流程：写时，调用ID生成器获取全局唯一ID，将ID编码为62进制短码，存储映射到数据库和缓存；读时，先查缓存，未命中查数据库，然后重定向。S-存储与扩展：短码生成：采用分布式ID生成器（如Snowflake变种）或预生成批量号段，避免ID碰撞。62进制编码，6位可表示约568亿组合，足够使用。数据库：两张表，URL映射表（short_code,long_url,created_at,user_id），访问日志表（可选分库）。按short_code哈希分库分表。也可以使用NoSQL如DynamoDB。缓存：使用Redis存储热门映射，设置LRU淘汰，TTL根据热度动态调整。扩容：无状态服务层可水平扩展，数据库可水平分片。A-可用性与优化：单点ID生成器使用主备切换；缓存穿透用布隆过滤器；长URL校验防止垃圾数据；使用301重定向（永久移动）以提升浏览器缓存，但对点击统计有影响，通常用302方便计数。完整方案图（文字描述）：用户浏览器->DNS解析至短链服务域名->CDN静态化首页->应用负载均衡器->短链服务节点->Redis集群（主从+哨兵）->MySQL分片集群（主从复制，按short_code哈希分16库）->ID生成器（ZooKeeper协调的机器ID+时间戳序列）。3.2设计一个分布式缓存系统题目：设计一个类似Memcached或Redis的分布式缓存系统，要求支持get和set操作，高可用、可扩展。S-场景与规模：支持10万QPS，数据量TB级别，延迟<1ms，可用性99.99%。A-API设计：简单键值操作：get(key)->value,set(key,value,ttl)L-逻辑设计：客户端库使用一致性哈希将key路由到缓存节点。每个节点是一个内存存储引擎。采用主从架构或多活架构。组件包括：客户端SDK、缓存节点、配置中心（etcd/Consul）、监控系统。S-存储与扩展：一致性哈希环，引入虚拟节点平衡数据分布。节点增减时仅影响相邻部分数据。内存数据结构：使用哈希表+跳表（用于过期策略）。跳表按过期时间排序，定期或惰性删除。持久化：可选RDB快照或AOF日志，但不作为核心需求，缓存允许数据丢失。复制：主从异步复制，从节点可分担读流量。可用RedisCluster模式但需讨论数据迁移的slot机制。A-可用性：使用哨兵机制检测节点故障，自动提升从节点。客户端SDK实现重试和故障转移。为防止缓存雪崩，采用随机TTL、热点数据永不过期加异步更新。监控命中率、内存使用、网络流量。3.3设计一个消息队列题目：设计一个分布式消息队列系统，类似Kafka，支持高吞吐、持久化和消费组。S-场景与规模：日处理万亿级消息，单机吞吐量百万条/秒，消息持久化，支持多消费者组重复消费。A-API设计：生产者：produce(topic,message)，消费者：consume(topic,group_id)，提供offset提交。L-逻辑设计：架构：生产者->分区LeaderBroker->分区Follower同步->消费者。使用ZooKeeper或KRaft管理元数据和Controller选举。S-存储与扩展：存储使用顺序写日志（CommitLog），将消息追加到分区文件，利用操作系统的PageCache。分区内分段存储，方便清理。消息索引：使用稀疏索引记录offset与文件位置的映射。分区机制：topic分为多个partition，可水平扩展，每个partition在多个broker上有副本，leader负责读写。消费者组：组内每个消费者消费不同分区，实现并行。A-可用性：ISR（同步副本集）机制保证一致性。Leader故障时从ISR中选举新leader。生产者和消费者客户端实现重试和幂等。限流使用令牌桶。3.4设计一个聊天系统题目：设计一个类似WhatsApp的即时通讯系统，支持一对一聊天、群聊、在线状态、图片等消息。S-场景与规模：1亿DAU，每个用户平均每天发送50条消息，峰值QPS约200万。消息延迟<100ms。支持消息已读回执。A-API设计：使用WebSocket长连接用于实时消息。关键接口：发送消息POST/messages（或者通过WebSocket直接发送JSON格式消息），获取历史消息GET/messages?chat_id=&before_timestamp=，上传附件POST/attachments。L-逻辑设计：客户端与服务端维持WebSocket连接，通过连接管理服务（长连接网关）路由。消息流程：用户A发送消息到网关，网关将消息推送到消息队列，消息处理服务保存消息到数据库，然后推送到用户B所在的网关节点，最终下发。存储：消息表按chat_id分片，使用时序数据库（如HBase或Cassandra）适合大量写。最新消息缓存Redis。S-存储扩展：消息表巨大，使用chat_id哈希分片，每个分片多副本。历史消息访问低频，可考虑冷热分离，冷数据归档对象存储。附件使用对象存储（如S3），返回URL。在线状态：使用心跳保持，通过Redis维护在线用户集合。A-可用性：消息不丢失通过写数据库后返回ACK，客户端本地存储已发送但未确认的消息。重连机制。消息有序通过服务端序列号保证。3.5设计一个限流器题目：设计一个API限流器，限制每个用户在规定时间窗口内的请求次数，比如每分钟不超过100次。S-场景与规模：面向数百万用户，需要在网关层或服务层实现低延迟限流。允许一定的分布式误差，但不能阻塞正常请求。A-API设计：非对外API，而是中间件函数：RateLimiter.allow(user_id,limit,window)->booleanL-逻辑设计：常见算法：固定窗口计数器、滑动窗口日志、滑动窗口计数器、令牌桶、漏桶。考虑到精度与内存消耗，推荐使用滑动窗口计数器（结合Redis的有序集合或本地内存）或令牌桶。分布式环境下可以用Redis+Lua脚本实现原子性。每个用户一个key，存储请求时间戳有序集合，每次请求删除窗口外的时间戳，然后判断当前集合大小。S-存储：使用Redis集群，每个用户耗费少量内存，存储窗口内时间戳。可定期清理。也可使用本地GuavaRateLimiter，但分布式不精确。A-可用性：Redis故障时降级为本地计数或放行。监控限流命中率，动态调整阈值。3.6设计一个排行榜系统题目：设计一个游戏排行榜，实时显示用户积分排名，支持查看TopN和某用户周边排名。S-场景与规模：日活用户5000万，积分更新频繁，要求排行榜延迟<5秒。A-API设计：POST/score/update(user_id,score)GET/leaderboard/top?n=100返回前100名GET/leaderboard/around?user_id=xxx&range=10返回该用户前后10名L-逻辑设计：使用Redis有序集合（SortedSet）天然适合。积分作为score，用户ID作为member。更新时ZADD。查询TopN使用ZREVRANGE。查询周边排名先ZREVRANK获取排名，再ZREVRANGE前后range。考虑海量用户时，有序集合内存占用大，可对用户分桶（按积分段），每个桶一个有序集合，查询TopN时合并多个桶数据。或者使用树形结构的堆。S-存储：RedisCluster分片，键按user_id哈希，但有序集合无法直接跨分片排序。因此可以按排行榜类型整体单分片，或者使用单独的Redis大内存实例，并通过读写分离和备份保证可用性。如果数据量极大，可采用分层排行榜：本地内存缓存Top1000，次热门数据放Redis，全量数据放Cassandra并定期用Spark计算批处理排行榜。A-可用性：Redis主从+哨兵。积分更新异步写入数据库持久化，Redis故障可从数据库重建。3.7设计一个视频流媒体平台题目：设计类似YouTube的视频分享平台，支持视频上传、转码、播放、评论。S-场景：支持大量用户上传和观看视频，高并发播放，多分辨率自适应，全球低延迟。A-API设计：POST/upload视频文件上传GET/video/{id}返回视频元数据和播放地址（m3u8）POST/comment发表评论GET/comments?video_id=xxxL-逻辑设计：上传：客户端直传对象存储（S3），完成后回调视频服务。视频服务发送转码任务到消息队列，转码集群（FFmpeg）消费任务生成不同分辨率（360p,720p,1080p）和HLS切片，存回对象存储。结果更新到数据库。播放：使用CDN分发，视频元数据服务返回对应CDN地址。自适应码率HLS。评论存储：按视频ID分库分表，NoSQL亦可。S-存储：视频和图片用对象存储+CDN。元数据用MySQL或NoSQL。转码计算资源按需弹性扩缩。A-可用性：多区域部署，CDN回源策略，热度视频预推送到边缘节点。播放统计和推荐系统离线处理。3.8设计一个分布式唯一ID生成器题目：设计一个全局唯一ID生成服务，要求高性能、趋势递增（或大致有序），在分布式环境中不重复。S-场景与规模：每秒需生成数万个ID，ID长度64位，可用于数据库主键。A-API设计：GET/id/next返回一个long型IDL-逻辑设计：典型方案Snowflake。64位：1位保留+41位时间戳（毫秒级，可用69年）+10位工作机器ID（可配置1024个节点）+12位序列号（每毫秒4096个）。服务启动时从配置中心获取唯一的workerId（用ZooKeeper临时顺序节点避免冲突）。序列号在每毫秒内自增，用完则等待下一毫秒。也可使用号段模式：服务从数据库批量获取一段ID，本地缓存分发，减少网络调用。S-存储与扩展：无状态服务可水平扩展，只要保证workerId唯一。时钟回拨处理：回拨较小时等待，回拨较大时报错或切换到备用workerId。也可使用Leaf-segment模式依赖数据库号段，更简单。A-可用性：多实例部署，workerId分配需有自动回收和续约机制。监控ID生成速率和时钟偏差。本章小结：8道系统设计题涵盖了缓存、消息、聊天、限流、排行榜、视频、ID生成器等典型互联网场景，关键在于展示你的设计思路、权衡和演进能力，而非死记硬背。每次练习时务必严格套用SALSA框架，口述完整。第四章配套全真模拟面试卷卷结构：Coding题3道（第1题字符串+哈希表，第2题树与递归，第3题动态规划），SystemDesign题2道（设计限流器、设计短链服务）。限时90分钟，请模拟真实面试环境，边写边讲。4.1Coding部分第1题：字母异位词分组题目：给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。答案与解析：解题思路：利用排序后的字符串作为key，将相同字母构成的单词归为一组。也可以使用字符频次统计的字符串作为key。时间复杂度O(NKlogK)，N为单词数，K为最大单词长度。代码实现：publicList<List<String>>groupAnagrams(String[]strs){

Map<String,List<String>>map=newHashMap<>();

for(Strings:strs){

char[]chars=s.toCharArray();

Arrays.sort(chars);

Stringkey=newString(chars);

puteIfAbsent(key,k->newArrayList<>()).add(s);

}

returnnewArrayList<>(map.values());

}复杂度：时间O(NKlogK)，空间O(NK)。如果使用计数统计（26个字母计数拼接字符串），可优化到O(NK)。评分标准：写出思路得40%，代码正确无Bug得40%，正确分析复杂度得20%。第2题：二叉树的序列化与反序列化题目：请设计一个算法来实现二叉树的序列化与反序列化。不限定序列化/反序列化算法的具体执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且这个字符串可以被反序列化成原始的树结构。答案与解析：解题思路：使用前序遍历序列化，遇到null用特殊字符如“#”表示。反序列化时用队列从左到右重建。也可使用层序遍历。代码实现：publicStringserialize(TreeNoderoot){

StringBuildersb=newStringBuilder();

serializeHelper(root,sb);

returnsb.toString();

}

privatevoidserializeHelper(TreeNodenode,StringBuildersb){

if(node==null){

sb.append("#,");

return;

}

sb.append(node.val).append(",");

serializeHelper(node.left,sb);

serializeHelper(node.right,sb);

}

publicTreeNodedeserialize(Stringdata){

Queue<String>queue=newLinkedList<>(Arrays.asList(data.split(",")));

returndeserializeHelper(queue);

}

privateTreeNodedeserializeHelper(Queue<String>queue){

Stringval=queue.poll();

if(val.equals("#"))returnnull;

TreeNodenode=newTreeNode(Integer.parseInt(val));

node.left=deserializeHelper(queue);

node.right=deserializeHelper(queue);

returnnode;

}复杂度：O(N)时间，O(N)空间。评分标准：能处理null的标记得30%，序