2025年IT行業(yè)軟件開發(fā)工程師面試模擬題及答案解析一、編程題（共3題，每題15分）題目1（15分）問題描述：實現(xiàn)一個函數(shù)，輸入一個正整數(shù)n，返回其漢諾塔移動方案。要求：1.輸出每一步的移動，例如"移動盤子從A到C"2.采用遞歸方式實現(xiàn)3.時間復雜度要求O(n)示例輸入：pythonn=2示例輸出：移動盤子從A到C移動盤子從A到B移動盤子從C到B移動盤子從A到C移動盤子從B到A移動盤子從B到C移動盤子從A到C答題要求：請用Python實現(xiàn)該函數(shù)，并附上測試用例。題目2（15分）問題描述：設(shè)計一個LRU（最近最少使用）緩存類，要求：1.支持`get(key)`和`put(key,value)`操作2.當緩存容量滿了時，需要淘汰最久未使用的元素3.時間復雜度為O(1)示例輸入：pythonLRUCache=LRUCache(2)LRUCache.put(1,1)LRUCache.put(2,2)print(LRUCache.get(1))#返回1LRUCache.put(3,3)#去除鍵2print(LRUCache.get(2))#返回-1(未找到)LRUCache.put(4,4)#去除鍵1print(LRUCache.get(1))#返回-1(未找到)print(LRUCache.get(3))#返回3print(LRUCache.get(4))#返回4示例輸出：1-1-134答題要求：請用Python實現(xiàn)LRUCache類，可使用哈希表和雙向鏈表結(jié)合的方式。題目3（15分）問題描述：實現(xiàn)一個函數(shù)，將字符串中的所有相鄰的重復字符合并為一個，并返回新字符串。要求：1.不使用內(nèi)置的字符串替換函數(shù)2.時間復雜度O(n)示例輸入：pythons="aaabccddd"示例輸出：python"aabcd"答題要求：請用Python實現(xiàn)該函數(shù)，并附上測試用例。二、算法題（共4題，每題10分）題目4（10分）問題描述：給定一個包含n個整數(shù)的數(shù)組，判斷該數(shù)組是否可以劃分為至少兩個連續(xù)的子數(shù)組，且這兩個子數(shù)組的和相等。如果可以，返回true；否則返回false。示例輸入：pythonnums=[1,2,3,4,5]示例輸出：pythontrue解析思路：需要先計算前綴和，然后遍歷數(shù)組尋找分割點。題目5（10分）問題描述：設(shè)計一個算法，找出數(shù)組中未出現(xiàn)的最小正整數(shù)。要求：1.不能使用額外的存儲空間2.時間復雜度O(n)示例輸入：pythonnums=[3,4,-1,1]示例輸出：python2解析思路：可以利用數(shù)組索引作為標記，將正整數(shù)放到對應(yīng)索引位置。題目6（10分）問題描述：給定一個二叉樹，判斷其是否為平衡二叉樹。平衡二叉樹定義：對于任意節(jié)點，其左右子樹高度差不超過1。示例輸入：python#構(gòu)建二叉樹classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightroot=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)示例輸出：pythontrue解析思路：需要遞歸計算每個節(jié)點的高度，同時判斷左右子樹高度差。題目7（10分）問題描述：實現(xiàn)一個函數(shù)，找出字符串中的最長回文子串。要求：1.時間復雜度O(n^2)2.空間復雜度O(1)示例輸入：pythons="babad"示例輸出：python"bab"或"aba"解析思路：可以采用中心擴展法，遍歷每個字符作為中心，向兩邊擴展。三、系統(tǒng)設(shè)計題（共2題，每題20分）題目8（20分）問題描述：設(shè)計一個簡單的消息隊列系統(tǒng)，要求：1.支持生產(chǎn)者-消費者模式2.需要考慮消息的持久化（防止服務(wù)器宕機丟失消息）3.需要處理消息重復消費的問題4.簡述關(guān)鍵模塊的設(shè)計思路答題要求：請說明系統(tǒng)架構(gòu)、關(guān)鍵組件設(shè)計、數(shù)據(jù)存儲方式、以及如何保證消息不丟失。題目9（20分）問題描述：設(shè)計一個高并發(fā)的短鏈接系統(tǒng)，要求：1.輸入任意長度的URL，生成固定長度的短鏈接2.支持短鏈接跳轉(zhuǎn)到原始URL3.需要考慮高并發(fā)下的性能問題4.簡述技術(shù)選型和關(guān)鍵實現(xiàn)方案答題要求：請說明系統(tǒng)架構(gòu)、使用的技術(shù)棧、如何處理高并發(fā)、以及如何保證URL的唯一性。答案解析編程題答案題目1答案pythondefhanoi(n,source,target,auxiliary):ifn==1:print(f"移動盤子從{source}到{target}")returnhanoi(n-1,source,auxiliary,target)print(f"移動盤子從{source}到{target}")hanoi(n-1,auxiliary,target,source)#測試用例n=2hanoi(n,'A','C','B')題目2答案pythonclassDLinkedNode: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=DLinkedNode()self.tail=DLinkedNode()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=DLinkedNode(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)#測試用例LRUCache=LRUCache(2)LRUCache.put(1,1)LRUCache.put(2,2)print(LRUCache.get(1))#返回1LRUCache.put(3,3)#去除鍵2print(LRUCache.get(2))#返回-1(未找到)LRUCache.put(4,4)#去除鍵1print(LRUCache.get(1))#返回-1(未找到)print(LRUCache.get(3))#返回3print(LRUCache.get(4))#返回4題目3答案pythondefmerge_repeated_chars(s:str)->str:ifnots:return""result=[]i=0whilei<len(s):result.append(s[i])whilei<len(s)-1ands[i]==s[i+1]:i+=1i+=1return''.join(result)#測試用例s="aaabccddd"print(merge_repeated_chars(s))#輸出"aabcd"算法題答案題目4答案pythondefcan_partition(nums):total_sum=sum(nums)iftotal_sum%2!=0:returnFalsetarget=total_sum//2n=len(nums)dp=[False]*(target+1)dp[0]=Truefornuminnums:forjinrange(target,num-1,-1):dp[j]=dp[j]ordp[j-num]returndp[target]題目5答案pythondeffirst_missing_positive(nums):n=len(nums)foriinrange(n):while1<=nums[i]<=nandnums[nums[i]-1]!=nums[i]:nums[nums[i]-1],nums[i]=nums[i],nums[nums[i]-1]foriinrange(n):ifnums[i]!=i+1:returni+1returnn+1題目6答案pythonclassSolution:defisBalanced(self,root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)balanced=left_balancedandright_balancedandabs(left_height-right_height)<=1returnmax(left_height,right_height)+1,balancedreturncheck(root)[1]題目7答案pythondeflongest_palindrome(s:str)->str:ifnots:return""start,end=0,0foriinrange(len(s)):len1=self._expand_around_center(s,i,i)len2=self._expand_around_center(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]def_expand_around_center(self,s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1系統(tǒng)設(shè)計題答案題目8答案系統(tǒng)架構(gòu)：1.消息生產(chǎn)者：將消息發(fā)送到消息隊列2.消息隊列：負責存儲消息，提供拉取接口3.消息消費者：從隊列中拉取消息并處理4.消息存儲：使用數(shù)據(jù)庫或文件系統(tǒng)持久化消息5.消息確認：消費者處理完消息后發(fā)送確認關(guān)鍵組件設(shè)計：-消息隊列：采用單生產(chǎn)者多消費者模式，支持阻塞拉取-消息持久化：將消息寫入磁盤，防止服務(wù)器宕機丟失-消息重復消費：通過冪等鍵或去重表防止重復消費數(shù)據(jù)存儲方式：-使用關(guān)系型數(shù)據(jù)庫（如PostgreSQL）存儲消息，包含id、內(nèi)容、狀態(tài)等字段-使用Redis存儲消息確認狀態(tài)，提高查詢效率保證消息不丟失：1.生產(chǎn)者發(fā)送消息后等待隊列確認2.消費者處理完消息后發(fā)送確認3.定期檢查未確認消息并重新發(fā)送題目9答案系統(tǒng)架構(gòu)：1.URL縮短服務(wù)：將長URL轉(zhuǎn)換為短URL2.短