2026年软件工程面试编程题库及答案

2026年软件工程面试编程题库及答案一、算法设计题（共3题，每题20分）1.字符串最长重复子串问题题目：给定两个字符串`str1`和`str2`，请编写函数返回它们的最长重复子串的长度。例如：-输入：`str1="ABABC",str2="BABCA"`-输出：`3`（最长重复子串为"ABC"）答案：pythondeflongest_common_substring(s1,s2):m,n=len(s1),len(s2)dp=[[0](n+1)for_inrange(m+1)]max_len=0end_idx=0foriinrange(1,m+1):forjinrange(1,n+1):ifs1[i-1]==s2[j-1]:dp[i][j]=dp[i-1][j-1]+1ifdp[i][j]>max_len:max_len=dp[i][j]end_idx=ielse:dp[i][j]=0returns1[end_idx-max_len:end_idx]解析：使用动态规划（DynamicProgramming）方法，构建二维数组`dp`，其中`dp[i][j]`表示`s1`的前`i`个字符与`s2`的前`j`个字符的最长公共子串长度。遍历过程中，若`s1[i-1]==s2[j-1]`，则`dp[i][j]=dp[i-1][j-1]+1`，否则`dp[i][j]=0`。通过记录最大值和结束位置，最终返回最长重复子串。时间复杂度O(mn)，空间复杂度O(mn)。2.矩阵螺旋遍历问题题目：给定一个`mxn`的矩阵，请按螺旋顺序从外向内遍历并返回元素列表。例如：-输入：`matrix=[[1,2,3],[4,5,6],[7,8,9]]`-输出：`[1,2,3,6,9,8,7,4,5]`答案：pythondefspiral_matrix(matrix):ifnotmatrixornotmatrix[0]:return[]result=[]top,bottom=0,len(matrix)-1left,right=0,len(matrix[0])-1whiletop<=bottomandleft<=right:从左到右遍历顶部forjinrange(left,right+1):result.append(matrix[top][j])top+=1从上到下遍历右侧foriinrange(top,bottom+1):result.append(matrix[i][right])right-=1iftop<=bottom:从右到左遍历底部forjinrange(right,left-1,-1):result.append(matrix[bottom][j])bottom-=1ifleft<=right:从下到上遍历左侧foriinrange(bottom,top-1,-1):result.append(matrix[i][left])left+=1returnresult解析：使用边界变量`top`、`bottom`、`left`、`right`表示当前遍历的边界，按顺序遍历矩阵的顶部、右侧、底部、左侧，每次遍历后更新边界值。注意在遍历过程中需要检查边界是否仍然有效，避免重复遍历。时间复杂度O(mn)，空间复杂度O(1)（若不计返回结果的空间）。3.树的最大深度问题题目：给定二叉树的根节点`root`，请编写函数返回其最大深度。例如：-输入：`root=[3,9,20,null,null,15,7]`（使用层序遍历表示）-输出：`3`答案：pythonDefinitionforabinarytreenode.classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmax_depth(root):ifnotroot:return0queue=[root]depth=0whilequeue:level_size=len(queue)for_inrange(level_size):node=queue.pop(0)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)depth+=1returndepth解析：使用广度优先搜索（BFS）方法，通过队列逐层遍历二叉树，每遍历完一层深度加1。当队列为空时，表示所有节点已遍历，此时`depth`即为最大深度。时间复杂度O(n)，空间复杂度O(n)。二、数据库查询题（共2题，每题25分）1.SQL分组与排序查询题目：假设有一个订单表`orders`，包含列`order_id`（订单ID）、`customer_id`（客户ID）、`order_date`（订单日期）、`total_amount`（订单金额）。请编写SQL查询：-统计每个客户的总订单金额，并按金额从高到低排序。-若金额相同，则按客户ID升序排序。答案：sqlSELECTcustomer_id,SUM(total_amount)AStotal_order_amountFROMordersGROUPBYcustomer_idORDERBYtotal_order_amountDESC,customer_idASC;解析：使用`GROUPBY`对客户进行分组，并使用`SUM`聚合函数计算每个客户的总订单金额。通过`ORDERBY`进行排序，先按`total_order_amount`降序，再按`customer_id`升序。确保金额相同时客户ID较小的排在前面。2.SQL子查询与连接查询题目：假设有一个员工表`employees`（列：`employee_id`、`name`、`department_id`）和一个部门表`departments`（列：`department_id`、`department_name`）。请编写SQL查询：-查询每个部门的平均员工年龄（假设`employees`表中有`age`列）。-排除员工人数少于5人的部门。答案：sqlSELECTd.department_name,AVG(e.age)ASaverage_ageFROMemployeeseJOINdepartmentsdONe.department_id=d.department_idGROUPBYd.department_nameHAVINGCOUNT(e.employee_id)>=5;解析：使用`JOIN`连接`employees`和`departments`表，通过`GROUPBY`按部门名称分组，并使用`AVG`计算平均年龄。使用`HAVING`子句过滤掉员工人数少于5人的部门。时间复杂度受索引影响，但通常为O(nlogn)。三、系统设计题（共1题，30分）1.设计一个简单的短链接系统题目：请设计一个短链接系统，要求：-输入一个长链接，系统返回一个短链接。-输入短链接，系统返回对应的长链接。-支持高并发访问。-短链接应具有唯一性和可读性（如使用字母+数字组合）。答案：系统架构：1.短链接生成：-使用哈希算法（如SHA-256）对长链接进行哈希，取前6位作为短链接的标识。-若生成的短链接已存在，则重新哈希直到唯一。2.数据库设计：sqlCREATETABLEshort_links(short_codeVARCHAR(10)PRIMARYKEY,long_urlVARCHAR(255)NOTNULL,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP);3.缓存层：-使用Redis缓存短链接对应的原始长链接，减少数据库查询次数。4.API设计：python生成短链接defgenerate_short_link(long_url):short_code=hash_url(long_url)whileexists(short_code):short_code=hash_url(long_url+str(random.randint(0,1000)))save_to_db(short_code,long_url)return"/"+short_code获取长链接defresolve_short_link(short_code):long_url=redis.get(short_code)ifnotlong_url:long_url=get_from_db(short_code)iflong_url:redis.set(short_code,long_url)returnlong_url5.高并发处理：-使用负载均衡分配请求。-数据库读写分离，主库负责写入，从库负责查询。解析：-唯一性：通过哈希算法确保短链接唯一，若冲突则添加随机数重新哈希。-可读性：哈希后可使用字母+数字组合，便于传播。-高并发：通过缓存和负载均衡提升性能，数据库读写分离减轻主库压力。四、编码实现题（共3题，每题15分）1.递归斐波那契数列优化题目：请实现一个递归函数计算斐波那契数列的第`n`项，要求优化递归调用，避免重复计算。答案：pythondeffib(n,memo={}):ifninmemo:returnmemo[n]ifn<=2:return1memo[n]=fib(n-1,memo)+fib(n-2,memo)returnmemo[n]解析：使用字典`memo`缓存已计算的结果，避免重复递归调用。时间复杂度O(n)，空间复杂度O(n)。2.并发爬虫任务分配题目：假设需要爬取一个包含`m`个URL的网站，请编写代码使用`threading`模块并行爬取，每个线程最多爬取`k`个URL。答案：pythonimportthreadingfromqueueimportQueuedeffetch_url(url):print(f"Fetching{url}")defworker(url_queue,max_tasks):whilenoturl_queue.empty():for_inrange(max_tasks):ifurl_queue.empty():breakurl=url_queue.get()fetch_url(url)url_queue.task_done()defconcurrent_crawler(urls,max_tasks=10):url_queue=Queue()forurlinurls:url_queue.put(url)threads=[]for_inrange(max_tasks):t=threading.Thread(target=worker,args=(url_queue,max_tasks))t.start()threads.append(t)fortinthreads:t.join()解析：使用`Queue`存储URL，每个线程从队列中获取`k`个URL进行爬取。通过控制线程数量和任务分配，实现高效并行爬取。注意线程安全。3.JSON数据解析与转换题目：给定一个嵌套的JSON对象，请编写函数将其转换为扁平化的字典。例如：-输入：`{"a":{"b":{"c":1}}}`-输出：`{"a.b.c":1}`答案：pythondefflatten_json(obj,parent_key='',sep='.'):items=[]fork,vinobj.items():new_key=f"{parent