2025年高級軟件工程師面試模擬題及答案1.編程題（3題，每題15分，共45分）題目1（15分）問題描述：實現(xiàn)一個函數(shù)，輸入一個整數(shù)數(shù)組，返回所有相加之和為特定數(shù)目的組合。組合中數(shù)字可以重復(fù)，但組合順序不同視為不同組合。示例：輸入：nums=[2,1,3],target=7輸出：[[2,2,3],[1,1,1,1,1,1,1],[1,1,1,1,1,2]]要求：-無重復(fù)元素組合-可以使用遞歸或迭代實現(xiàn)-時間復(fù)雜度盡可能優(yōu)化pythondefcombination_sum(nums,target):#你的代碼題目2（15分）問題描述：給定一個包含重復(fù)元素的數(shù)組，返回所有不重復(fù)的全排列。可以假設(shè)所有元素都是正整數(shù)。示例：輸入：nums=[1,1,2]輸出：[[1,1,2],[1,2,1],[2,1,1]]要求：-排列順序不同視為不同排列-必須處理重復(fù)元素的情況-不能使用庫函數(shù)直接生成排列pythondefpermute_unique(nums):#你的代碼題目3（15分）問題描述：實現(xiàn)一個二叉樹的最大路徑和。路徑可以從任意節(jié)點開始，也可以結(jié)束任意節(jié)點，但不一定經(jīng)過根節(jié)點。示例：輸入：[1,2,3]1/\23輸出：6要求：-可以使用遞歸或迭代實現(xiàn)-處理包含負(fù)數(shù)的樹結(jié)構(gòu)-時間復(fù)雜度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分）問題描述：給定一個字符串，找到最長的不包含重復(fù)字符的子串長度。示例：輸入："abcabcbb"輸出：3("abc")要求：-可以使用哈希表或滑動窗口-時間復(fù)雜度O(n)-必須考慮所有邊界情況pythondeflength_of_longest_substring(s):#你的代碼題目5（10分）問題描述：實現(xiàn)一個LRU（最近最少使用）緩存。支持get和put操作，當(dāng)緩存容量滿時，需要淘汰最久未使用的元素。示例：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操作時間復(fù)雜度O(1)-put操作時間復(fù)雜度O(1)-可以使用雙向鏈表和哈希表實現(xiàn)pythonclassLRUCache:def__init__(self,capacity:int):#你的代碼defget(self,key:int)->int:#你的代碼defput(self,key:int,value:int)->None:#你的代碼題目6（10分）問題描述：給定一個未排序的整數(shù)數(shù)組，找到其中第k個最大的元素。示例：輸入：[3,2,1,5,6,4],k=2輸出：5要求：-可以使用快速選擇算法-時間復(fù)雜度平均O(n)-必須考慮所有邊界情況pythondeffind_kth_largest(nums,k):#你的代碼題目7（10分）問題描述：實現(xiàn)一個函數(shù)，檢查一個二叉樹是否是完全二叉樹。完全二叉樹是指除最后一層外，每一層都是滿的，并且最后一層節(jié)點從左到右連續(xù)排列。示例：輸入：[1,2,3,4,5,6]1/\23/\45/6輸出：True要求：-可以使用BFS或遞歸實現(xiàn)-時間復(fù)雜度O(n)-必須考慮所有邊界情況（空樹、單節(jié)點等）pythondefis_complete_tree(root):#你的代碼3.系統(tǒng)設(shè)計題（2題，每題25分，共50分）題目8（25分）問題描述：設(shè)計一個簡單的消息隊列系統(tǒng)。需要支持以下功能：1.生產(chǎn)者發(fā)送消息2.消費(fèi)者接收消息3.消息持久化（使用本地文件或數(shù)據(jù)庫）4.消息確認(rèn)機(jī)制5.超時未確認(rèn)消息的重新投遞要求：-闡述系統(tǒng)架構(gòu)-描述核心數(shù)據(jù)結(jié)構(gòu)-說明如何處理高并發(fā)情況-提出至少三種可能的實現(xiàn)方案#系統(tǒng)設(shè)計描述架構(gòu)概述題目9（25分）問題描述：設(shè)計一個短鏈接生成系統(tǒng)。需要支持以下功能：1.將長鏈接轉(zhuǎn)換為短鏈接2.訪問短鏈接時解析為原始長鏈接3.高并發(fā)處理4.鏈接統(tǒng)計（點擊次數(shù)、訪問時間等）5.鏈接有效期管理要求：-闡述系統(tǒng)架構(gòu)-描述核心算法-說明如何保證鏈接唯一性和安全性-提出至少兩種可能的實現(xiàn)方案-考慮分布式部署方案#系統(tǒng)設(shè)計描述架構(gòu)概述答案編程題答案題目1答案（15分）pythondefcombination_sum(nums,target):result=[]nums.sort()#先排序處理重復(fù)元素defbacktrack(start,path,target):iftarget==0:result.append(path.copy())returnforiinrange(start,len(nums)):ifi>startandnums[i]==nums[i-1]:continue#跳過重復(fù)元素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()#先排序處理重復(fù)元素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))#忽略負(fù)值分支right=max(0,dfs(node.right))max_sum=max(max_sum,left+right+node.val)returnmax(left,right)+node.valdfs(root)returnmax_sum測試用例：python#構(gòu)建測試樹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={}#創(chuàng)建偽頭部和偽尾部self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):#添加節(jié)點到頭部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):#刪除指定節(jié)點prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):#將節(jié)點移動到頭部self._remove_node(node)self._add_node(node)def_pop_tail(self):#彈出尾部節(jié)點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#標(biāo)記是否遇到不完整的層whilequeue:node=queue.pop(0)ifnode:ifend:returnFalse#在不完整層后面發(fā)現(xiàn)了節(jié)點queue.append(node.left)queue.append(node.right)else:end=True#標(biāo)記為不完整層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系統(tǒng)設(shè)計題答案題目8答案（25分）#消息隊列系統(tǒng)設(shè)計架構(gòu)概述消息隊列系統(tǒng)采用生產(chǎn)者-消費(fèi)者模式，核心組件包括：1.消息存儲層（關(guān)系型數(shù)據(jù)庫或NoSQL）2.消息路由器（處理消息分發(fā)）3.消息代理（處理網(wǎng)絡(luò)通信）4.緩存層（提高讀取性能）5.監(jiān)控系統(tǒng)（跟蹤消息狀態(tài)）系統(tǒng)架構(gòu)圖：#示意圖（文字描述）消息產(chǎn)生者->消息代理->消息存儲層|->緩存層消息消費(fèi)者<-消息代理<-消息存儲層核心數(shù)據(jù)結(jié)構(gòu)1.消息對象：json{"id":"唯一標(biāo)識","topic":"消息主題","payload":"消息內(nèi)容","timestamp":"時間戳","status":"處理狀態(tài)","retries":"重試次數(shù)"}2.消息隊列：json{"queue_id":"隊列ID","messages":["消息ID1","消息ID2"],"offset":"消費(fèi)偏移量"}高并發(fā)處理方案1.消息存儲層采用分片策略，按topic或queue_id進(jìn)行分區(qū)2.使用Redis等內(nèi)存數(shù)據(jù)庫緩存熱點消息3.消息代理支持負(fù)載均衡，可水平擴(kuò)展4.消息確認(rèn)機(jī)制采用冪等寫入，防止重復(fù)處理實現(xiàn)方案1.基于RabbitMQ的實現(xiàn)-使用RabbitMQ的directexchange實現(xiàn)點對點通信-結(jié)合死信隊列處理無法消費(fèi)的消息-使用TTL策略自動清理過期消息2.基于Kafka的實現(xiàn)-使用Kafka的partition機(jī)制保證消息