2026年軟件工程師面試題集及解答詳解一、編程基礎(chǔ)題（5題，每題10分，共50分）題目1（10分）編寫一個函數(shù)，實(shí)現(xiàn)二叉樹的深度優(yōu)先遍歷（前序遍歷）。要求使用遞歸方式實(shí)現(xiàn)，并返回遍歷結(jié)果的列表。python示例輸入classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right創(chuàng)建示例二叉樹1/\23/\45root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)請實(shí)現(xiàn)`preorder_traversal`函數(shù)。題目2（10分）實(shí)現(xiàn)一個函數(shù)，檢查一個字符串是否是有效的括號組合。字符串只包含三種括號：'(',')','{','}','['和']'。示例：pythonprint(is_valid("()"))#Trueprint(is_valid("()[]{}"))#Trueprint(is_valid("(]"))#Falseprint(is_valid("([)]"))#Falseprint(is_valid("{[]}"))#True題目3（10分）給定一個排序數(shù)組和一個目標(biāo)值，使用二分查找算法找出目標(biāo)值在數(shù)組中的位置。如果目標(biāo)值不存在于數(shù)組中，返回它應(yīng)插入的位置。示例：pythonsearch_insert([1,3,5,6],5)->2search_insert([1,3,5,6],2)->1search_insert([1,3,5,6],7)->4search_insert([1,3,5,6],0)->0題目4（10分）實(shí)現(xiàn)一個LRU（最近最少使用）緩存機(jī)制。緩存應(yīng)該支持以下操作：-`get(key)`:獲取鍵key對應(yīng)的值，如果鍵不存在返回-1。-`put(key,value)`:插入或更新鍵值為key的值。當(dāng)緩存容量已滿時，應(yīng)該刪除最近最少使用的項(xiàng)目。假設(shè)緩存容量為2。python示例：LRUCache=LRUCache(2)LRUCache.put(1,1)LRUCache.put(2,2)LRUCache.get(1)#返回1LRUCache.put(3,3)#去除鍵2LRUCache.get(2)#返回-1(未找到)LRUCache.put(4,4)#去除鍵1LRUCache.get(1)#返回-1(未找到)LRUCache.get(3)#返回3LRUCache.get(4)#返回4題目5（10分）編寫一個函數(shù)，實(shí)現(xiàn)字符串的剪枝。移除字符串中所有的空格，并將連續(xù)的多個空格替換為單個空格。如果字符串開頭或結(jié)尾有空格，也需要去除。示例：pythontrim_spaces("HelloWorld")#"HelloWorld"trim_spaces("Thisisatest")#"Thisisatest"trim_spaces("NoSpacesHere")#"NoSpacesHere"二、算法設(shè)計題（4題，每題15分，共60分）題目6（15分）設(shè)計一個算法，找出數(shù)組中第三大的數(shù)。如果數(shù)組中的不同數(shù)少于3個，返回最大的數(shù)。示例：pythonthird_max([1,2,-2147483648])->-2147483648third_max([1,2,2,5,3,5])->2third_max([1,1,2])->2題目7（15分）設(shè)計一個算法，找出字符串中的最長回文子串?？梢约僭O(shè)字符串的長度不超過1000。示例：pythonlongest_palindrome("babad")->"bab"or"aba"longest_palindrome("cbbd")->"bb"題目8（15分）設(shè)計一個算法，實(shí)現(xiàn)LRU緩存的高效實(shí)現(xiàn)。要求使用哈希表和雙向鏈表結(jié)合的方式實(shí)現(xiàn)，確保`get`和`put`操作的時間復(fù)雜度為O(1)。python示例：classLRUCache:def__init__(self,capacity:int):初始化LRUCache對象passdefget(self,key:int)->int:獲取鍵key對應(yīng)的值passdefput(self,key:int,value:int)->None:插入或更新鍵值為key的值pass題目9（15分）設(shè)計一個算法，實(shí)現(xiàn)字符串的URL編碼。將空格轉(zhuǎn)換為`%20`，并確保所有非字母數(shù)字字符也進(jìn)行編碼。示例：pythonurl_encode("HelloWorld!")#"Hello%20World%21"url_encode("")#"http%3A%2F%2F"url_encode("123456")#"123%20%20456"三、系統(tǒng)設(shè)計題（2題，每題25分，共50分）題目10（25分）設(shè)計一個簡單的微博系統(tǒng)，需要支持以下功能：1.用戶注冊和登錄2.發(fā)布微博（包含文本內(nèi)容和時間戳）3.獲取用戶的時間線（包含自己發(fā)布的和關(guān)注的人發(fā)布的微博）4.關(guān)注和取消關(guān)注用戶要求：-描述系統(tǒng)的數(shù)據(jù)存儲設(shè)計（至少兩種數(shù)據(jù)結(jié)構(gòu)）-描述關(guān)鍵API的設(shè)計-考慮系統(tǒng)的擴(kuò)展性和性能題目11（25分）設(shè)計一個簡單的在線購物車系統(tǒng)，需要支持以下功能：1.添加商品到購物車2.從購物車移除商品3.修改商品數(shù)量4.計算購物車總價5.查看購物車內(nèi)容要求：-描述系統(tǒng)的數(shù)據(jù)存儲設(shè)計-描述關(guān)鍵API的設(shè)計-考慮系統(tǒng)的擴(kuò)展性和性能-分析可能遇到的主要技術(shù)挑戰(zhàn)答案及解析編程基礎(chǔ)題答案及解析題目1答案及解析（10分）pythondefpreorder_traversal(root):result=[]defdfs(node):ifnotnode:returnresult.append(node.val)dfs(node.left)dfs(node.right)dfs(root)returnresult解析：-使用遞歸方式實(shí)現(xiàn)前序遍歷（根-左-右）-定義輔助函數(shù)dfs進(jìn)行深度優(yōu)先遍歷-遍歷順序：先訪問當(dāng)前節(jié)點(diǎn)，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹-時間復(fù)雜度：O(n)，每個節(jié)點(diǎn)訪問一次-空間復(fù)雜度：O(h)，h為二叉樹的高度題目2答案及解析（10分）pythondefis_valid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping.values():stack.append(char)elifcharinmapping.keys():ifnotstackorstack[-1]!=mapping[char]:returnFalsestack.pop()else:returnFalsereturnnotstack解析：-使用棧來匹配括號-遇到開括號入棧，遇到閉括號時檢查棧頂元素是否匹配-最后棧應(yīng)為空表示所有括號匹配-時間復(fù)雜度：O(n)，每個字符遍歷一次-空間復(fù)雜度：O(n)，最壞情況下棧大小為n題目3答案及解析（10分）pythondefsearch_insert(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1returnleft解析：-使用二分查找算法-如果找到目標(biāo)值，返回其索引-如果未找到，返回應(yīng)該插入的位置（left的最終值）-時間復(fù)雜度：O(logn)-空間復(fù)雜度：O(1)題目4答案及解析（10分）pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=self.Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head解析：-使用雙向鏈表和哈希表實(shí)現(xiàn)LRU緩存-雙向鏈表維護(hù)訪問順序，頭部為最近訪問，尾部為最久未訪問-哈希表實(shí)現(xiàn)O(1)時間復(fù)雜度的get操作-put操作時如果超出容量，刪除鏈表尾部節(jié)點(diǎn)-時間復(fù)雜度：O(1)-空間復(fù)雜度：O(capacity)題目5答案及解析（10分）pythondeftrim_spaces(s:str)->str:start,end=0,len(s)-1去除開頭空格whilestart<=endands[start]=='':start+=1去除結(jié)尾空格whileend>=startands[end]=='':end-=1去除中間多余空格result=[]space_found=Falseforiinrange(start,end+1):ifs[i]!='':result.append(s[i])space_found=Falseelifnotspace_found:result.append('')space_found=Truereturn''.join(result)解析：-首先找到字符串的有效開頭和結(jié)尾-然后遍歷有效部分，合并連續(xù)空格-時間復(fù)雜度：O(n)-空間復(fù)雜度：O(n)答案及解析（續(xù)）算法設(shè)計題答案及解析題目6答案及解析（15分）pythondefthird_max(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:third=secondsecond=firstfirst=numeliffirst>num>second:third=secondsecond=numelifsecond>num>third:third=numreturnfirstifthird!=float('-inf')elsesecond解析：-維護(hù)三個變量表示最大的三個數(shù)-遍歷數(shù)組，更新三個變量-最后如果第三大的數(shù)存在，返回它，否則返回最大的數(shù)-時間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)題目7答案及解析（15分）pythondeflongest_palindrome(s:str)->str:ifnots:return""start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)len2=expand_from_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]defexpand_from_center(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：-使用中心擴(kuò)展法-對于每個字符，檢查以它為中心的回文（奇數(shù)長度和偶數(shù)長度）-記錄最長的回文子串-時間復(fù)雜度：O(n2)-空間復(fù)雜度：O(1)題目8答案及解析（15分）pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=self.Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head解析：-與題目4的答案相同，因?yàn)長RU緩存的核心數(shù)據(jù)結(jié)構(gòu)相同-使用雙向鏈表維護(hù)訪問順序，哈希表實(shí)現(xiàn)O(1)訪問-時間復(fù)雜度：O(1)-空間復(fù)雜度：O(capacity)題目9答案及解析（15分）pythondefurl_encode(url:str)->str:result=[]forcharinurl:ifchar.isalnum():result.append(char)else:result.append('%{:02X}'.format(ord(char)))return''.join(result)解析：-遍歷字符串中的每個字符-字母數(shù)字字符直接保留-其他字符轉(zhuǎn)換為兩位十六進(jìn)制數(shù)-使用`%{:02X}`格式化字符-時間復(fù)雜度：O(n)-空間復(fù)雜度：O(n)系統(tǒng)設(shè)計題答案及解析題目10答案及解析（25分）設(shè)計一個簡單的微博系統(tǒng)數(shù)據(jù)存儲設(shè)計1.用戶表：-user_id(主鍵)-username-password_hash-email-created_at2.微博表：-tweet_id(主鍵)-user_id(外鍵)-content-created_at3.關(guān)注關(guān)系表：-follower_id(外鍵)-followee_id(外鍵)-created_at關(guān)鍵API設(shè)計1.用戶相關(guān)：-POST/register:注冊新用戶-參數(shù)：username,password,email-返回：用戶信息或錯誤-POST/login:用戶登錄-參數(shù)：username,password-返回：token或錯誤-GET/users/me:獲取當(dāng)前用戶信息-參數(shù)：token-返回：用戶信息2.微博相關(guān)：-POST/tweets:發(fā)布微博-參數(shù)：token,content-返回：微博信息或錯誤-GET/tweets:獲取用戶時間線-參數(shù)：token-返回：微博列表3.關(guān)注相關(guān)：-POST/follow:關(guān)注用戶-參數(shù)：token,followee_id-返回：成功或錯誤-DELETE/follow:取消關(guān)注-參數(shù)：token,followee_id-返回：成功或錯誤擴(kuò)展性和性能考慮-數(shù)據(jù)庫索引：在user_id,followee_id,created_at等字段上建立索引-緩存：使用Redis緩存熱點(diǎn)數(shù)據(jù)，如用戶時間線-分頁：微博列表支持分頁加載-異步處理：發(fā)布微博等操作可以異步處理-負(fù)載均衡：使用Nginx等