2026年软件开发工程师面试题算法设计与编程能力测试题

2026年软件开发工程师面试题：算法设计与编程能力测试题一、编程实现题（共5题，每题10分，总分50分）要求：以下题目需使用Python或C++实现，请提供完整的代码和必要注释。1.字符串反转（10分）题目：编写一个函数，将输入的字符串反转，不使用现成的反转函数（如`reverse()`或`[::-1]`）。示例：输入`"hello"`，输出`"olleh"`。2.爬取网页数据（10分）题目：编写一个Python脚本，使用`requests`库爬取指定URL的网页内容，并去除所有HTML标签，只保留纯文本。要求：必须处理异常情况（如网络错误、页面不存在等），并输出最终的文本内容。3.排序算法优化（10分）题目：实现快速排序算法，但要求在原始数组部分有序时，优化比较次数，提高效率。说明：可以使用三数取中法选择基准值，并考虑尾递归优化。4.拓扑排序（10分）题目：给定一个有向无环图（DAG），编写函数进行拓扑排序。输入：使用邻接表表示图，例如：`{"A":["B"],"B":["C"],"C":["D"],"D":[]}`。输出：拓扑排序的结果序列（如`["A","B","C","D"]`）。5.动态规划：最长递增子序列（10分）题目：编写函数计算数组的最长递增子序列（LIS）长度。示例：输入`[10,9,2,5,3,7,101,18]`，输出`4`（对应子序列`[2,3,7,101]`）。二、算法设计题（共3题，每题15分，总分45分）要求：请描述算法思路，提供伪代码或关键步骤，无需完整代码。1.最小路径和（15分）题目：给定一个二维矩阵，找到从左上角到右下角的最小路径和，每次只能向下或向右移动。示例：[[1,3,1],[1,5,1],[4,2,1]]输出：`7`（路径：`1→3→1→1→1`）。2.字符串匹配：KMP算法（15分）题目：实现KMP（Knuth-Morris-Pratt）字符串匹配算法，计算部分匹配表（PartialMatchTable）。说明：描述如何构建部分匹配表，并解释匹配过程。3.并查集：连通分量问题（15分）题目：设计并查集（Union-Find）数据结构，支持路径压缩和按秩合并，解决连通分量问题。要求：描述关键操作（`find`和`union`）的实现细节。三、系统设计题（共2题，每题20分，总分40分）要求：请提供系统架构设计思路，包括模块划分、数据结构选择和关键算法。1.设计URL短链接服务（20分）题目：设计一个URL短链接服务（如TinyURL），要求：-支持将长URL转换为短URL，并可反向解析。-高并发场景下仍能保证性能。-短URL应唯一且易于记忆。2.设计LRU缓存（20分）题目：设计一个LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作，要求：-使用双向链表+哈希表实现，时间复杂度为O(1)。-描述核心数据结构和操作流程。答案与解析一、编程实现题答案1.字符串反转pythondefreverse_string(s:str)->str:result=[]forcharins:result.insert(0,char)#从头部插入return''.join(result)或使用双指针法：defreverse_string_two_pointers(s:str)->str:s=list(s)left,right=0,len(s)-1whileleft<right:s[left],s[right]=s[right],s[left]left+=1right-=1return''.join(s)2.爬取网页数据pythonimportrequestsfrombs4importBeautifulSoupdefcrawl_web(url:str)->str:try:response=requests.get(url)response.raise_for_status()soup=BeautifulSoup(response.text,'html.parser')forscriptinsoup(["script","style"]):script.decompose()#去除脚本和样式text=soup.get_text(separator='')returntext.strip()exceptrequests.RequestExceptionase:returnf"Error:{e}"3.快速排序优化pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=median_of_three(arr[0],arr[len(arr)//2],arr[-1])left,right=partition(arr,pivot)returnquick_sort(left)+[pivot]+quick_sort(right)defmedian_of_three(a,b,c):if(a-b)(c-a)>=0:returnaelif(b-a)(c-b)>=0:returnbelse:returncdefpartition(arr,pivot):left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnleft,right4.拓扑排序pythondeftopological_sort(graph):in_degree={u:0foruingraph}foruingraph:forvingraph[u]:in_degree[v]+=1queue=[uforuingraphifin_degree[u]==0]result=[]whilequeue:u=queue.pop(0)result.append(u)forvingraph[u]:in_degree[v]-=1ifin_degree[v]==0:queue.append(v)iflen(result)==len(graph):returnresultelse:raiseValueError("Graphhasacycle")5.最长递增子序列pythondeflis(nums):ifnotnums:return0dp=[1]len(nums)foriinrange(1,len(nums)):forjinrange(i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)二、算法设计题答案1.最小路径和思路：动态规划，定义`dp[i][j]`为到达`(i,j)`的最小路径和，状态转移方程为：`dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]`（注意边界条件）。伪代码：plaintextfunctionminPathSum(grid):ifgridisempty:return0rows,cols=len(grid),len(grid[0])dp[0][0]=grid[0][0]forifrom1torows-1:dp[i][0]=dp[i-1][0]+grid[i][0]forjfrom1tocols-1:dp[0][j]=dp[0][j-1]+grid[0][j]forifrom1torows-1:forjfrom1tocols-1:dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]returndp[rows-1][cols-1]2.KMP算法部分匹配表构建：对于模式串`P`，计算`lps[i]`表示以`P[0..i]`为后缀的最长公共前后缀长度。伪代码：plaintextfunctioncomputeLPS(P):lps=[0]len(P)length=0i=1whilei<len(P):ifP[i]==P[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=13.并查集按秩合并：-`find(u)`:递归查找`u`的根节点，并路径压缩。-`union(u,v)`:将`u`和`v`所属的集合合并，按秩选择较小的根节点合并到较大的根节点。伪代码：plaintextfunctionfind(u):ifparent[u]!=u:parent[u]=find(parent[u])#路径压缩returnparent[u]functionunion(u,v):root_u=find(u)root_v=find(v)ifroot_u!=root_v:ifrank[root_u]<rank[root_v]:parent[root_u]=root_velifrank[root_u]>rank[root_v]:parent[root_v]=root_uelse:parent[root_v]=root_urank[root_u]+=1三、系统设计题答案1.URL短链接服务设计思路：-编码方式：使用Base62（字母+数字）将长URL映射为短字符串，如`aV3`。-数据结构：哈希表存储`long_url→short_url`，分布式缓存（如Redis）加速查询。-架构：-用户请求长URL，生成短URL并存储到数据库。-用户访问短URL时，反向解析并返回长URL。-高并发优化：-使用负载均衡分发请求。-短URL使用分布式ID生成器。2.LRU缓存设计思路：-数据结构：