2025年高级软件工程师面试模拟题及答案

2025年高级软件工程师面试模拟题及答案1.编程题（3题，每题15分，共45分）题目1（15分）问题描述：实现一个函数，输入一个整数数组，返回所有相加之和为特定数目的组合。组合中数字可以重复，但组合顺序不同视为不同组合。示例：输入：nums=[2,1,3],target=7输出：[[2,2,3],[1,1,1,1,1,1,1],[1,1,1,1,1,2]]要求：-无重复元素组合-可以使用递归或迭代实现-时间复杂度尽可能优化pythondefcombination_sum(nums,target):#你的代码题目2（15分）问题描述：给定一个包含重复元素的数组，返回所有不重复的全排列。可以假设所有元素都是正整数。示例：输入：nums=[1,1,2]输出：[[1,1,2],[1,2,1],[2,1,1]]要求：-排列顺序不同视为不同排列-必须处理重复元素的情况-不能使用库函数直接生成排列pythondefpermute_unique(nums):#你的代码题目3（15分）问题描述：实现一个二叉树的最大路径和。路径可以从任意节点开始，也可以结束任意节点，但不一定经过根节点。示例：输入：[1,2,3]1/\23输出：6要求：-可以使用递归或迭代实现-处理包含负数的树结构-时间复杂度O(n)pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmax_path_sum(root):#你的代码2.算法题（4题，每题10分，共40分）题目4（10分）问题描述：给定一个字符串，找到最长的不包含重复字符的子串长度。示例：输入："abcabcbb"输出：3("abc")要求：-可以使用哈希表或滑动窗口-时间复杂度O(n)-必须考虑所有边界情况pythondeflength_of_longest_substring(s):#你的代码题目5（10分）问题描述：实现一个LRU（最近最少使用）缓存。支持get和put操作，当缓存容量满时，需要淘汰最久未使用的元素。示例：LRUCache容量=2put(1,1)put(2,2)get(1)//返回1put(3,3)//去除键2get(2)//返回-1(未找到)put(4,4)//去除键1get(1)//返回-1(未找到)get(3)//返回3get(4)//返回4要求：-get操作时间复杂度O(1)-put操作时间复杂度O(1)-可以使用双向链表和哈希表实现pythonclassLRUCache:def__init__(self,capacity:int):#你的代码defget(self,key:int)->int:#你的代码defput(self,key:int,value:int)->None:#你的代码题目6（10分）问题描述：给定一个未排序的整数数组，找到其中第k个最大的元素。示例：输入：[3,2,1,5,6,4],k=2输出：5要求：-可以使用快速选择算法-时间复杂度平均O(n)-必须考虑所有边界情况pythondeffind_kth_largest(nums,k):#你的代码题目7（10分）问题描述：实现一个函数，检查一个二叉树是否是完全二叉树。完全二叉树是指除最后一层外，每一层都是满的，并且最后一层节点从左到右连续排列。示例：输入：[1,2,3,4,5,6]1/\23/\45/6输出：True要求：-可以使用BFS或递归实现-时间复杂度O(n)-必须考虑所有边界情况（空树、单节点等）pythondefis_complete_tree(root):#你的代码3.系统设计题（2题，每题25分，共50分）题目8（25分）问题描述：设计一个简单的消息队列系统。需要支持以下功能：1.生产者发送消息2.消费者接收消息3.消息持久化（使用本地文件或数据库）4.消息确认机制5.超时未确认消息的重新投递要求：-阐述系统架构-描述核心数据结构-说明如何处理高并发情况-提出至少三种可能的实现方案#系统设计描述架构概述题目9（25分）问题描述：设计一个短链接生成系统。需要支持以下功能：1.将长链接转换为短链接2.访问短链接时解析为原始长链接3.高并发处理4.链接统计（点击次数、访问时间等）5.链接有效期管理要求：-阐述系统架构-描述核心算法-说明如何保证链接唯一性和安全性-提出至少两种可能的实现方案-考虑分布式部署方案#系统设计描述架构概述答案编程题答案题目1答案（15分）pythondefcombination_sum(nums,target):result=[]nums.sort()#先排序处理重复元素defbacktrack(start,path,target):iftarget==0:result.append(path.copy())returnforiinrange(start,len(nums)):ifi>startandnums[i]==nums[i-1]:continue#跳过重复元素ifnums[i]>target:break#剪枝path.append(nums[i])backtrack(i+1,path,target-nums[i])path.pop()backtrack(0,[],target)returnresult测试用例：pythonprint(combination_sum([2,1,3],7))#输出：[[1,1,1,1,1,1,1],[1,1,1,1,2],[1,2,2],[1,3,3],[2,2,3]]题目2答案（15分）pythondefpermute_unique(nums):defbacktrack(path,used,res):iflen(path)==len(nums):res.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack(path,used,res)path.pop()used[i]=Falsenums.sort()#先排序处理重复元素res=[]used=[False]*len(nums)backtrack([],used,res)returnres测试用例：pythonprint(permute_unique([1,1,2]))#输出：[[1,1,2],[1,2,1],[2,1,1]]题目3答案（15分）pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmax_path_sum(root):max_sum=float('-inf')defdfs(node):nonlocalmax_sumifnotnode:return0left=max(0,dfs(node.left))#忽略负值分支right=max(0,dfs(node.right))max_sum=max(max_sum,left+right+node.val)returnmax(left,right)+node.valdfs(root)returnmax_sum测试用例：python#构建测试树root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)print(max_path_sum(root))#输出：6算法题答案题目4答案（10分）pythondeflength_of_longest_substring(s):char_map={}left=0max_len=0forrightinrange(len(s)):ifs[right]inchar_map:left=max(left,char_map[s[right]]+1)char_map[s[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len测试用例：pythonprint(length_of_longest_substring("abcabcbb"))#输出：3题目5答案（10分）pythonclassNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}#创建伪头部和伪尾部self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):#添加节点到头部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):#删除指定节点prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):#将节点移动到头部self._remove_node(node)self._add_node(node)def_pop_tail(self):#弹出尾部节点res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:node.value=valueself._move_to_head(node)测试用例：pythoncache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#返回1cache.put(3,3)#去除键2print(cache.get(2))#返回-1cache.put(4,4)#去除键1print(cache.get(1))#返回-1print(cache.get(3))#返回3print(cache.get(4))#返回4题目6答案（10分）pythondeffind_kth_largest(nums,k):defquick_select(left,right,index):pivot=nums[right]i=leftforjinrange(left,right):ifnums[j]>pivot:nums[i],nums[j]=nums[j],nums[i]i+=1nums[i],nums[right]=nums[right],nums[i]ifi==index:returnnums[i]elifi>index:returnquick_select(left,i-1,index)else:returnquick_select(i+1,right,index)returnquick_select(0,len(nums)-1,k-1)测试用例：pythonprint(find_kth_largest([3,2,1,5,6,4],2))#输出：5题目7答案（10分）pythondefis_complete_tree(root):ifnotroot:returnTruequeue=[root]end=False#标记是否遇到不完整的层whilequeue:node=queue.pop(0)ifnode:ifend:returnFalse#在不完整层后面发现了节点queue.append(node.left)queue.append(node.right)else:end=True#标记为不完整层returnTrue测试用例：python#完全二叉树root1=TreeNode(1)root1.left=TreeNode(2)root1.right=TreeNode(3)root1.left.left=TreeNode(4)root1.left.right=TreeNode(5)root1.right.left=TreeNode(6)#非完全二叉树root2=TreeNode(1)root2.left=TreeNode(2)root2.right=TreeNode(3)root2.left.left=TreeNode(4)root2.left.right=Noneroot2.right.left=TreeNode(5)print(is_complete_tree(root1))#输出：Trueprint(is_complete_tree(root2))#输出：False系统设计题答案题目8答案（25分）#消息队列系统设计架构概述消息队列系统采用生产者-消费者模式，核心组件包括：1.消息存储层（关系型数据库或NoSQL）2.消息路由器（处理消息分发）3.消息代理（处理网络通信）4.缓存层（提高读取性能）5.监控系统（跟踪消息状态）系统架构图：#示意图（文字描述）消息产生者->消息代理->消息存储层|->缓存层消息消费者<-消息代理<-消息存储层核心数据结构1.消息对象：json{"id":"唯一标识","topic":"消息主题","payload":"消息内容","timestamp":"时间戳","status":"处理状态","retries":"重试次数"}2.消息队列：json{"queue_id":"队列ID","messages":["消息ID1","消息ID2"],"offset":"消费偏移量"}高并发处理方案1.消息存储层采用分片策略，按topic或queue_id进行分区2.使用Redis等内存数据库缓存热点消息3.消息代理支持负载均衡，可水平扩展4.消息确认机制采用幂等写入，防止重复处理实现方案1.基于RabbitMQ的实现-使用RabbitMQ的directexchange实现点对点通信-结合死信队列处理无法消费的消息-使用TTL策略自动清理过期消息2.基于Kafka的实现-使用Kafka的partition机制保证消息