2026年軟件開發(fā)工程師技術面試試題一、編程題（共5題，每題20分，總分100分）1.題目：編寫一個函數(shù)，實現(xiàn)快速排序算法。輸入一個整數(shù)數(shù)組，返回排序后的數(shù)組。要求使用原地排序（不使用額外數(shù)組），并說明時間復雜度和空間復雜度。示例輸入：`[3,1,4,1,5,9,2,6,5,3,5]`示例輸出：`[1,1,2,3,3,4,5,5,5,6,9]`2.題目：實現(xiàn)一個無重復字符的最長子串查找函數(shù)。輸入一個字符串，返回最長無重復字符的子串長度。示例輸入：`"abcabcbb"`示例輸出：`3`（最長無重復子串為"abc"）3.題目：設計一個簡單的LRU（LeastRecentlyUsed）緩存，支持`get`和`put`操作。緩存容量為固定值`capacity`。要求實現(xiàn)時間復雜度為O(1)的版本。示例輸入：-`put(1,1)`-`put(2,2)`-`get(1)`→返回`1`-`put(3,3)`（使鍵1作廢）-`get(2)`→返回`2`4.題目：編寫一個函數(shù)，檢查一個二叉樹是否是二叉搜索樹（BST）。假設節(jié)點定義如下：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right示例輸入：pythonroot=TreeNode(2,TreeNode(1),TreeNode(3))示例輸出：`True`5.題目：實現(xiàn)一個簡單的Trie（前綴樹），支持`insert`和`search`操作。示例輸入：-`insert("apple")`-`search("apple")`→返回`True`-`search("app")`→返回`False`-`startsWith("app")`→返回`True`二、算法題（共5題，每題20分，總分100分）1.題目：給定一個非負整數(shù)數(shù)組，返回其中連續(xù)子數(shù)組的最大和。要求使用動態(tài)規(guī)劃解決。示例輸入：`[-2,1,-3,4,-1,2,1,-5,4]`示例輸出：`6`（子數(shù)組[4,-1,2,1]）2.題目：實現(xiàn)一個函數(shù)，判斷一個整數(shù)是否是素數(shù)。要求時間復雜度為O(√n)。示例輸入：`17`示例輸出：`True`3.題目：給定一個字符串`s`和一個字符集`words`，判斷`s`是否可以由`words`中的單詞串聯(lián)而成。每個單詞可以重復使用。示例輸入：-`s="leetcode"`-`words=["leet","code"]`示例輸出：`True`（"leetcode"="leet"+"code"）4.題目：實現(xiàn)一個函數(shù)，計算二叉樹的所有節(jié)點之和。假設節(jié)點定義同編程題第4題。示例輸入：pythonroot=TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3))示例輸出：`15`（1+2+3+4+5）5.題目：給定一個整數(shù)`n`，返回`n`的格雷碼序列。格雷碼是一個二進制數(shù)字序列，其中任意兩個相鄰數(shù)字的二進制表示只有一位不同。示例輸入：`2`示例輸出：`[0,1,3,2]`（格雷碼為"00","01","11","10"）三、系統(tǒng)設計題（共3題，每題33分，總分99分）1.題目：設計一個簡單的微博系統(tǒng)，支持用戶發(fā)布、關注、獲取時間線等基本功能。需要說明系統(tǒng)架構、數(shù)據(jù)存儲方式（數(shù)據(jù)庫選型及表結構）、關鍵接口設計（如發(fā)布微博、獲取關注者時間線）。2.題目：設計一個短鏈接生成服務，要求：-支持將長鏈接轉換為短鏈接，并可通過短鏈接跳轉回原鏈接。-高并發(fā)場景下仍能穩(wěn)定運行。-需要說明技術選型（如數(shù)據(jù)庫、緩存）、短鏈接生成算法、系統(tǒng)架構。3.題目：設計一個實時聊天系統(tǒng)，支持一對一和群組聊天。需要說明系統(tǒng)架構（如WebSocket、消息隊列）、數(shù)據(jù)存儲方式（如聊天記錄、用戶關系）、關鍵功能實現(xiàn)（如消息推送、離線消息）。答案與解析編程題答案與解析1.快速排序代碼：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：-時間復雜度：平均O(nlogn)，最壞O(n2)（當pivot取到最小或最大值時）。-空間復雜度：O(logn)（遞歸棧空間）。2.最長無重復子串代碼：pythondeflength_of_longest_substring(s):char_set=set()left=0max_len=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_len=max(max_len,right-left+1)returnmax_len解析：-使用滑動窗口思想，`left`和`right`分別表示窗口的左右邊界。-時間復雜度：O(n)，每個字符最多訪問兩次。3.LRU緩存代碼：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:self.cache.pop(self.order.pop(0))self.cache[key]=valueself.order.append(key)解析：-使用哈希表記錄鍵值對，`order`列表記錄訪問順序。-`get`操作時移動鍵到末尾，`put`操作時先刪除最久未使用的鍵。4.檢查BST代碼：pythondefis_valid_BST(root:TreeNode)->bool:defhelper(node,low=float('-inf'),high=float('inf')):ifnotnode:returnTrueifnot(low<node.val<high):returnFalsereturnhelper(node.left,low,node.val)andhelper(node.right,node.val,high)returnhelper(root)解析：-BST中左子樹所有節(jié)點<根節(jié)點<右子樹所有節(jié)點。-遞歸驗證每個節(jié)點是否在合法范圍內。5.Trie實現(xiàn)代碼：pythonclassTrieNode:def__init__(self):self.children={}self.is_end=FalseclassTrie:def__init__(self):self.root=TrieNode()definsert(self,word:str)->None:node=self.rootforcharinword:ifcharnotinnode.children:node.children[char]=TrieNode()node=node.children[char]node.is_end=Truedefsearch(self,word:str)->bool:node=self._find(word)returnnodeisnotNoneandnode.is_enddefstartsWith(self,prefix:str)->bool:returnself._find(prefix)isnotNonedef_find(self,word:str):node=self.rootforcharinword:ifcharnotinnode.children:returnNonenode=node.children[char]returnnode解析：-Trie通過哈希表存儲子節(jié)點，`is_end`標記單詞結束。-`search`和`startsWith`分別檢查完整單詞和前綴。算法題答案與解析1.最大子數(shù)組和代碼：pythondefmax_subarray(nums):max_sum=nums[0]current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum解析：-動態(tài)規(guī)劃思想，`current_sum`記錄當前最大和，`max_sum`記錄全局最大和。-時間復雜度：O(n)，空間復雜度：O(1)。2.判斷素數(shù)代碼：pythondefis_prime(n):ifn<=1:returnFalseforiinrange(2,int(n0.5)+1):ifn%i==0:returnFalsereturnTrue解析：-只需檢查到√n即可，因為若n有因子，必有一個≤√n。3.字符串分割代碼：pythondefword_break(s,words):word_set=set(words)dp=[False](len(s)+1)dp[0]=Trueforiinrange(1,len(s)+1):forjinrange(i):ifdp[j]ands[j:i]inword_set:dp[i]=Truebreakreturndp[-1]解析：-動態(tài)規(guī)劃，`dp[i]`表示前i個字符能否被分割。-時間復雜度：O(n2)，空間復雜度：O(n)。4.二叉樹節(jié)點之和代碼：pythondefsum_tree(root):ifnotroot:return0returnroot.val+sum_tree(root.left)+sum_tree(root.right)解析：-遞歸遍歷所有節(jié)點并累加。-時間復雜度：O(n)，空間復雜度：O(h)（遞歸棧）。5.格雷碼生成代碼：pythondefgray_code(n):return[i^(i>>1)foriinrange(1<<n)]解析：-格雷碼可通過`i^(i>>1)`生成，其中`i>>1`是i右移一位。-時間復雜度：O(2^n)，空間復雜度：O(2^n)。系統(tǒng)設計題答案與解析1.微博系統(tǒng)設計系統(tǒng)架構：-前端：Web/移動端（React/Vue+Flutter）-后端：API服務器（SpringBoot/Go+RESTfulAPI）-數(shù)據(jù)庫：MySQL（用戶信息、關系）、Redis（緩存、計數(shù)器）-消息隊列：Kafka/RabbitMQ（發(fā)布/訂閱）表結構：sql--用戶表CREATETABLEusers(idBIGINTAUTO_INCREMENTPRIMARYKEY,usernameVARCHAR(50)UNIQUE,passwordVARCHAR(255),create_timeTIMESTAMPDEFAULTCURRENT_TIMESTAMP);--關注關系表CREATETABLEfollows(follower_idBIGINT,followee_idBIGINT,PRIMARYKEY(follower_id,followee_id),FOREIGNKEY(follower_id)REFERENCESusers(id),FOREIGNKEY(followee_id)REFERENCESusers(id));關鍵接口：-`POST/api/status`（發(fā)布微博）-`GET/api/status/timeline`（獲取時間線）解析：-微博核心是關注關系