面试考题集针对研发工程师

2026年面试考题集针对研发工程师2026年研发工程师面试考题集（测试方向）一、编程语言与数据结构（5题，每题10分，共50分）1.题目：数组旋转问题问题描述：给定一个数组`nums`和一个整数`k`，将数组向右旋转`k`步。例如，`nums=[1,2,3,4,5]`,`k=2`，旋转后的数组为`[4,5,1,2,3]`。请实现该功能。要求：时间复杂度为O(n)，空间复杂度为O(1)。2.题目：链表相交判断问题描述：给定两个单链表，判断它们是否相交。如果相交，返回交点节点；如果不相交，返回`null`。例如：A:a1→a2→c1→c2→nullB:b1→b2→c1→c2→null交点为`c1`。要求：不使用额外空间，时间复杂度为O(n)。3.题目：二叉树最大深度问题描述：给定一个二叉树，求其最大深度。例如：3/\920/\157最大深度为3。要求：使用递归或迭代方法实现。4.题目：字符串匹配KMP算法问题描述：实现KMP（Knuth-Morris-Pratt）字符串匹配算法，计算模式串`pattern`在主串`text`中出现的次数。例如：text="ABABDABACDABABCABAB"pattern="ABABCABAB"匹配次数为1（从第10个字符开始匹配）。要求：实现前缀函数计算和匹配过程。5.题目：堆排序实现问题描述：实现堆排序算法，对给定数组进行排序。例如：nums=[12,11,13,5,6,7]排序后为`[5,6,7,11,12,13]`。要求：实现建堆和堆调整过程。二、算法设计（3题，每题15分，共45分）1.题目：最短路径问题问题描述：给定一个加权无向图，找出从起点`s`到终点`t`的最短路径。图用邻接矩阵表示，权重可能为负数（但无负权回路）。例如：graph=[[0,5,INF,10],[INF,0,3,INF],[INF,INF,0,1],[INF,INF,INF,0]]s=0,t=3最短路径长度为14（0→1→2→3）。要求：实现Dijkstra或Bellman-Ford算法。2.题目：区间调度问题问题描述：给定一组区间，每个区间表示为`(start,end)`，请找到最多的不重叠区间。例如：intervals=[[1,3],[2,5],[4,6],[6,7],[5,8]]最多可以选择3个区间（如[1,3],[4,6],[5,8]）。要求：实现贪心算法，按结束时间排序。3.题目：拓扑排序问题描述：给定一个有向无环图（DAG），输出所有顶点的拓扑排序序列。例如：edges=[[1,0],[2,0],[3,2],[3,1]]可能的拓扑序列为[0,1,2,3]或[0,2,1,3]。要求：实现基于DFS或BFS的拓扑排序。三、系统设计与架构（2题，每题20分，共40分）1.题目：设计短链接系统问题描述：设计一个短链接系统，将长URL转换为短URL，并支持反向解析。例如：longURL="/path/to/resource?query=123"shortURL="http://short.ly/xyz123"访问`http://short.ly/xyz123`应返回原长URL。要求：1.短URL生成规则2.数据存储方案3.高并发处理4.原URL加密存储2.题目：设计高可用计数器服务问题描述：设计一个分布式计数器服务，支持高并发访问和严格一致性。要求：1.支持多进程/线程安全2.分布式部署3.异常处理机制4.性能指标四、数据库与存储（3题，每题15分，共45分）1.题目：SQL查询优化问题描述：优化以下SQL查询性能：sqlSELECTuser_id,COUNT(order_id)FROMordersWHEREstatus='completed'GROUPBYuser_idHAVINGCOUNT(order_id)>10ORDERBYCOUNT(order_id)DESCLIMIT100;表结构：-orders(order_idINT,user_idINT,statusVARCHAR,timestampDATETIME)要求：提出索引优化、查询重写建议。2.题题目：NoSQL选型与设计问题描述：为电商平台设计用户行为数据存储方案。场景：1.用户浏览记录（PV）2.商品点击流3.购物车数据要求：1.选择合适的NoSQL类型（Redis/MongoDB/Cassandra等）2.数据模型设计3.高可用方案3.题目：分布式事务解决方案问题描述：设计一个分布式事务解决方案，支持多个数据库操作的原子性。场景：下单需要同时扣减库存和创建订单。要求：1.解决方案选型（2PC/3PC/SAGA等）2.实现难点3.补偿机制设计五、操作系统与网络（3题，每题15分，共45分）1.题目：进程调度算法问题描述：比较以下进程调度算法的优缺点：1.FCFS（先来先服务）2.SJF（最短作业优先）3.RoundRobin（轮转法）要求：给出不同场景下的适用性分析。2.题目：TCP三次握手过程问题描述：描述TCP三次握手过程，并说明为什么不能有四次握手。要求：绘制状态图并解释每个步骤。3.题目：DNS解析过程问题描述：描述从用户输入URL到获取IP地址的DNS解析过程。例如：→要求：说明每个DNS服务器的作用和查询顺序。答案与解析一、编程语言与数据结构1.数组旋转问题答案：pythondefrotate(nums,k):n=len(nums)k=k%nnums[:]=nums[-k:]+nums[:-k]解析：1.基本思路：将数组分为两部分，分别反转后合并2.具体步骤：-计算有效旋转次数：k%=n-反转整个数组-反转前k个元素-反转剩余元素3.时间复杂度：O(n)，空间复杂度：O(1)2.链表相交判断答案：pythondefgetIntersectionNode(headA,headB):ifnotheadAornotheadB:returnNonepa,pb=headA,headBwhilepa!=pb:pa=pa.nextifpaelseheadBpb=pb.nextifpbelseheadAreturnpa解析：1.基本思路：双指针法2.具体步骤：-初始化两个指针分别指向两个链表头-当指针到达链表末尾时转向另一个链表-相交时两个指针会相遇3.时间复杂度：O(n)，空间复杂度：O(1)3.二叉树最大深度答案：pythondefmaxDepth(root):ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))解析：1.递归思路：树的最大深度等于左右子树最大深度的最大值加12.终止条件：空节点深度为03.时间复杂度：O(n)，空间复杂度：O(h)（递归栈深度）4.KMP字符串匹配算法答案：pythondefcomputeLPS(pattern):lps=[0]len(pattern)length=0i=1whilei<len(pattern):ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=1returnlpsdefKMPSearch(text,pattern):lps=computeLPS(pattern)i=j=0count=0whilei<len(text):ifpattern[j]==text[i]:i+=1j+=1ifj==len(pattern):count+=1j=lps[j-1]elifi<len(text)andpattern[j]!=text[i]:ifj!=0:j=lps[j-1]else:i+=1returncount解析：1.KMP核心是前缀函数（LPS数组）2.计算前缀函数记录相同前后缀长度3.匹配时遇到不匹配时利用LPS数组跳转5.堆排序实现答案：pythondefheapify(nums,n,i):largest=ileft=2i+1right=2i+2ifleft<nandnums[left]>nums[largest]:largest=leftifright<nandnums[right]>nums[largest]:largest=rightiflargest!=i:nums[i],nums[largest]=nums[largest],nums[i]heapify(nums,n,largest)defheapSort(nums):n=len(nums)建大顶堆foriinrange(n//2-1,-1,-1):heapify(nums,n,i)逐个提取元素foriinrange(n-1,0,-1):nums[i],nums[0]=nums[0],nums[i]heapify(nums,i,0)解析：1.堆排序是原地排序，时间复杂度O(nlogn)2.建堆过程从最后一个非叶子节点开始向上调整3.排序过程每次将最大元素移到末尾二、算法设计1.最短路径问题答案：pythondefdijkstra(graph,s,t):n=len(graph)dist=[float('inf')]ndist[s]=0visited=[False]nfor_inrange(n):u=min_idx(dist,visited)ifu==-1:breakvisited[u]=Trueforvinrange(n):ifgraph[u][v]!=INFandnotvisited[v]anddist[u]+graph[u][v]<dist[v]:dist[v]=dist[u]+graph[u][v]returndist[t]ifdist[t]!=INFelse-1defmin_idx(dist,visited):min_val=float('inf')min_idx=-1foriinrange(len(dist)):ifnotvisited[i]anddist[i]<=min_val:min_val=dist[i]min_idx=ireturnmin_idx解析：1.Dijkstra算法适用于无负权边的最短路径问题2.使用贪心策略每次选择距离最短的未访问节点3.时间复杂度：O(n^2)，可优化为O((n+m)logn)使用优先队列2.区间调度问题答案：pythondefmax_intervals(intervals):按结束时间排序intervals.sort(key=lambdax:x[1])count=0end=float('-inf')forintervalinintervals:ifinterval[0]>=end:count+=1end=interval[1]returncount解析：1.贪心策略：每次选择结束最早的区间2.排序后按结束时间从小到大遍历3.时间复杂度：O(nlogn)，空间复杂度：O(1)3.拓扑排序答案：pythondeftopological_sort(num_nodes,edges):计数入度in_degree=[0]num_nodesforu,vinedges:in_degree[v]+=1初始化队列queue=[iforiinrange(num_nodes)ifin_degree[i]==0]result=[]whilequeue:u=queue.pop(0)result.append(u)forvinget_neighbors(num_nodes,edges,u):in_degree[v]-=1ifin_degree[v]==0:queue.append(v)iflen(result)==num_nodes:returnresultelse:return[]#无环图defget_neighbors(num_nodes,edges,node):neighbors=[]foru,vinedges:ifu==node:neighbors.append(v)returnneighbors解析：1.拓扑排序基于Kahn算法2.按入度为0的节点进行拓扑3.时间复杂度：O(n+m)，空间复杂度：O(n)三、系统设计与架构1.设计短链接系统要求：1.短URL生成：使用Base62编码（a-z,A-Z,0-9）+hashpythonimporthashlibdefencode_base62(num):chars="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"ifnum==0:returnchars[0]base=len(chars)result=[]whilenum>0:result.append(chars[num%base])num//=basereturn''.join(reversed(result))defgenerate_short_url(long_url):hash_obj=hashlib.md5(long_url.encode())hash_num=int(hash_obj.hexdigest(),16)returnf"http://short.ly/{encode_base62(hash_num%1_000_000)}"2.数据存储：Redis（Hash结构存储long_url和short_url）redisHSETshort_urls:xyz123<long_url>3.高并发处理：使用RedisCluster+负载均衡4.加密存储：对long_url使用hash或AES加密2.设计高可用计数器服务要求：1.数据结构：使用Redis的INCR命令2.分布式部署：使用RedisCluster分片3.异常处理：实现降级策略（如熔断）4.性能指标：-TPS：每秒请求数-QPS：每秒查询数-延迟：毫秒级四、数据库与存储1.SQL查询优化优化建议：1.添加索引：sqlCREATEINDEXidx_status_userONorders(status,user_id);2.查询重写：sqlSELECTuser_id,COUNT()asorder_countFROMordersWHEREstatus='completed'GROUPBYuser_idHAVINGorder_count>10ORDERBYorder_countDESCLIMIT100;3.分析执行计划：sqlEXPLAINSELECT...;2.NoSQL选型与设计设计方案：1.Redis：存储购物车（Hash结构）redisHSETcarts:123items:"product_id:1:quantity:3"2.MongoDB：存储浏览记录（文档模型）json{"user_id":"u123","products":[{"product_id":"p456","timestamp":"2026-01-01T10:00:00Z"},...]}3.Cassandra