2026年軟件工程師面試編程能力測試題一、算法與數(shù)據(jù)結構（共5題，每題10分，總分50分）1.（10分）題目：給定一個非空整數(shù)數(shù)組`nums`，其中元素范圍在`[1,n]`（`n`為數(shù)組長度），數(shù)組中存在重復元素。請找出數(shù)組中第一個重復的元素，并返回其索引。如果沒有重復元素，返回`-1`。示例：-輸入：`nums=[2,3,1,0,2,5]`，輸出：`2`（第一個重復的元素是`2`，索引為`2`）-輸入：`nums=[1,2,3,4,5]`，輸出：`-1`（無重復元素）要求：-時間復雜度：O(n)-空間復雜度：O(n)答案與解析：答案：pythondeffind_first_duplicate(nums):seen=set()forindex,numinenumerate(nums):ifnuminseen:returnindexseen.add(num)return-1解析：使用哈希集合`seen`記錄已遍歷的元素。遍歷數(shù)組時，若當前元素已存在于`seen`中，則返回其索引；否則將其加入`seen`。這樣確保了時間復雜度為O(n)，空間復雜度也為O(n)。2.（10分）題目：設計一個LRU（LeastRecentlyUsed）緩存，支持以下操作：-`get(key)`:獲取鍵`key`對應的值，若鍵不存在返回`-1`。獲取后，將該鍵值對移動到緩存最前面（最常用）。-`put(key,value)`:插入或更新鍵值對。如果緩存已滿，則移除最久未使用的鍵值對，再插入新的鍵值對。要求：-時間復雜度：O(1)-空間復雜度：O(capacity)答案與解析：答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()defget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)解析：使用`OrderedDict`實現(xiàn)LRU緩存。`get`操作時，若鍵存在則將其移動到最前面；`put`操作時，若鍵已存在則更新值并移動到最前面，否則直接插入。當緩存超過`capacity`時，移除最久未使用的元素（`popitem(last=False)`）。這樣確保了所有操作的時間復雜度為O(1)。3.（10分）題目：給定一個字符串`s`，其中包含字母、數(shù)字、符號等字符。請統(tǒng)計并返回字符串中每種字符的出現(xiàn)次數(shù)。結果可以按字符順序返回。示例：-輸入：`s="Hello,World!123"`，輸出：`{'H':1,'e':1,'l':3,'o':2,',':1,'':2,'W':1,'r':1,'d':1,'!':1,'1':1,'2':1,'3':1}`要求：-時間復雜度：O(n)-空間復雜度：O(1)（假設字符集固定）答案與解析：答案：pythondefcount_characters(s:str)->dict:count={}forcharins:ifcharincount:count[char]+=1else:count[char]=1returncount解析：遍歷字符串，使用字典`count`記錄每個字符的出現(xiàn)次數(shù)。由于字符集固定（如ASCII字符集），空間復雜度可視為O(1)。時間復雜度為O(n)，其中n為字符串長度。4.（10分）題目：給定一個二叉樹，判斷其是否為完全二叉樹。完全二叉樹的定義：除最后一層外，每一層節(jié)點都滿，且最后一層節(jié)點從左到右連續(xù)排列。示例：-輸入：`[1,2,3,4,5,6]`（二叉樹），輸出：`True`-輸入：`[1,2,3,4,None,6]`，輸出：`False`（右子節(jié)點缺失）要求：-時間復雜度：O(n)-空間復雜度：O(n)（使用隊列）答案與解析：答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_complete_binary_tree(root:TreeNode)->bool:ifnotroot:returnTruequeue=deque([root])flag=False#標記是否遇到過Nonewhilequeue:node=queue.popleft()ifnode:ifflag:returnFalse#如果之前遇到過None，當前節(jié)點不能為非空queue.append(node.left)queue.append(node.right)else:flag=True#遇到None，后續(xù)節(jié)點必須全為NonereturnTrue解析：使用隊列層序遍歷二叉樹。遍歷過程中，若遇到`None`，則設置`flag`為`True`，后續(xù)節(jié)點必須全為`None`。若在`flag`為`True`后遇到非空節(jié)點，則返回`False`。這樣確保了完全二叉樹的特性。5.（10分）題目：給定一個正整數(shù)`n`，生成所有可能的`n`皇后問題的解。皇后問題是指在8×8棋盤上放置n個皇后，使得任何兩個皇后不在同一行、同一列或同一對角線上。示例：-輸入：`n=4`，輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]要求：-時間復雜度：O(n!)-空間復雜度：O(n)答案與解析：答案：pythondefsolve_n_queens(n:int)->List[List[str]]:defbacktrack(row,diagonals,anti_diagonals,cols,state):ifrow==n:board=["".join(row)forrowinstate]result.append(board)returnforcolinrange(n):diag=row-colanti_diag=row+colifcolincolsordiagindiagonalsoranti_diaginanti_diagonals:continuecols.add(col)diagonals.add(diag)anti_diagonals.add(anti_diag)state[row][col]='Q'backtrack(row+1,diagonals,anti_diagonals,cols,state)cols.remove(col)diagonals.remove(diag)anti_diagonals.remove(anti_diag)state[row][col]='.'result=[]state=[["."for_inrange(n)]for_inrange(n)]backtrack(0,set(),set(),set(),state)returnresult解析：使用回溯法解決N皇后問題。定義三個集合分別記錄列、主對角線、副對角線的占用情況。遞歸遍歷每一行，嘗試在該行的每一列放置皇后，若不沖突則繼續(xù)遞歸下一行。若沖突則跳過當前列。最終將所有合法解加入`result`。二、數(shù)據(jù)庫與SQL（共3題，每題10分，總分30分）1.（10分）題目：假設有一個名為`employees`的表，結構如下：sqlCREATETABLEemployees(idINTPRIMARYKEY,nameVARCHAR(50),departmentVARCHAR(50),salaryDECIMAL(10,2));請編寫SQL查詢，返回每個部門的平均工資（`salary`），且只顯示平均工資高于公司平均工資的部門。要求：-使用子查詢或窗口函數(shù)均可。答案與解析：答案：sqlSELECTdepartment,AVG(salary)ASavg_salaryFROMemployeesGROUPBYdepartmentHAVINGAVG(salary)>(SELECTAVG(salary)FROMemployees);解析：外層查詢計算每個部門的平均工資，內(nèi)層查詢計算公司總平均工資。`HAVING`子句過濾出平均工資高于公司平均工資的部門。2.（10分）題目：假設有一個名為`orders`的表，結構如下：sqlCREATETABLEorders(idINTPRIMARYKEY,customer_idINT,order_dateDATE,total_amountDECIMAL(10,2));請編寫SQL查詢，返回每個客戶的訂單數(shù)量，且只顯示訂單數(shù)量超過10的客戶的客戶ID和訂單數(shù)量。要求：-使用分組和過濾。答案與解析：答案：sqlSELECTcustomer_id,COUNT()ASorder_countFROMordersGROUPBYcustomer_idHAVINGCOUNT()>10;解析：`GROUPBY`子句按`customer_id`分組，`COUNT()`統(tǒng)計每個客戶的訂單數(shù)量，`HAVING`子句過濾出訂單數(shù)量超過10的客戶。3.（10分）題目：假設有兩個表：-`orders`表（訂單表）：`id`（訂單ID），`customer_id`（客戶ID），`order_date`（訂單日期）-`order_items`表（訂單項表）：`order_id`（訂單ID），`product_id`（產(chǎn)品ID），`quantity`（數(shù)量）請編寫SQL查詢，返回每個客戶的總訂單金額（`order_items`表中的`quantity`乘以單價，假設單價存儲在`order_items`表中），并按總金額降序排列。要求：-使用連接和聚合函數(shù)。答案與解析：答案：sqlSELECTo.customer_id,SUM(oi.quantityoi.unit_price)AStotal_amountFROMordersoJOINorder_itemsoiONo.id=oi.order_idGROUPBYo.customer_idORDERBYtotal_amountDESC;解析：使用`JOIN`將`orders`和`order_items`表連接，通過`GROUPBY`按`customer_id`分組，計算每個客戶的總訂單金額（`SUM(oi.quantityoi.unit_price)`），最后按總金額降序排列。三、系統(tǒng)設計（共2題，每題10分，總分20分）1.（10分）題目：設計一個簡單的短鏈接服務。用戶輸入長鏈接，服務返回一個短鏈接，點擊短鏈接后自動跳轉(zhuǎn)到原始長鏈接。要求：-短鏈接應易于記憶且唯一。-支持高并發(fā)訪問。-提供基本的統(tǒng)計功能（如點擊次數(shù)）。答案與解析：答案：1.數(shù)據(jù)存儲：-使用數(shù)據(jù)庫表存儲：`id`（自增主鍵），`long_url`（長鏈接），`short_code`（短鏈接碼），`click_count`（點擊次數(shù)）。-短鏈接碼生成：使用隨機或哈希算法生成（如`a-z`和`0-9`的6位字符）。2.服務流程：-生成短鏈接碼，檢查是否唯一，若重復則重新生成。-存儲長鏈接、短鏈接碼和初始點擊次數(shù)。-返回短鏈接（如`/{short_code}`）。3.高并發(fā)處理：-使用緩存（如Redis）緩存熱門短鏈接，減少數(shù)據(jù)庫查詢。-數(shù)據(jù)庫讀寫分離，主庫負責寫入，從庫負責查詢。4.統(tǒng)計功能：-每次點擊短鏈接時，更新`click_count`。解析：核心是短鏈接碼的生成和存儲。使用隨機碼或哈希算法確保唯一性，高并發(fā)下通過緩存和數(shù)據(jù)庫優(yōu)化提升性能。統(tǒng)計功能通過數(shù)據(jù)庫表記錄點擊次數(shù)實現(xiàn)。2.（10分）題目：設計一個簡單的消息隊列服務（如Kafka或RabbitMQ的簡化版）。用戶可以發(fā)布消息，消費者可以訂閱并消費消息。要求：-支持至少一個生產(chǎn)者和多個消費者。-消息必須按發(fā)送順序消費。-支持至少一次交付（即消息可能重復，但至少交付一次）。答案與解析：答案：1.數(shù)據(jù)存儲：-使用消息隊列存儲消息，如RabbitMQ或Kafka。-消息表：`id`（消息ID），`topic`（主題），`message`（消息內(nèi)容），`timestamp`（時間戳）。2.生產(chǎn)者（Producer）：-用戶發(fā)布消息到指定主題。-消息寫入數(shù)據(jù)庫或消息隊列，并返回確認。3.消費者（Consumer）：-消費者訂閱主題，按順序拉取消息。-消息消費后，記錄狀態(tài)（如`is_consumed`）。-若消費失敗，重新入隊或記錄重試次數(shù)。4.至少一次交付：-生產(chǎn)者確認消息寫入成功。-消費者消費失敗時，消息重新入隊。解析：核心是消息的存儲和順序保證。使用數(shù)據(jù)庫或消息隊列實現(xiàn)消息存儲，消費者按順序拉取消息。至少一次交付通過生產(chǎn)者確認和消費者重試實現(xiàn)。四、網(wǎng)絡編程與分布式系統(tǒng)（共2題，每題10分，總分20分）1.（10分）題目：設計一個簡單的分布式緩存系統(tǒng)。節(jié)點間通過RPC（遠程過程調(diào)用）通信，支持以下操作：-`get(key)`:獲取鍵值對-`set(key,value)`:設置鍵值對要求：-支持節(jié)點故障自動恢復。-緩存數(shù)據(jù)在節(jié)點間同步。答案與解析：答案：1.架構設計：-使用一致性哈希算法分配節(jié)點，確保鍵值對均勻分布。-每個節(jié)點維護本地緩存，通過RPC同步數(shù)據(jù)。2.RPC通信：-生產(chǎn)者節(jié)點通過RPC調(diào)用其他節(jié)點的`get`或`set`方法。-使用gRPC或RESTAPI實現(xiàn)RPC。3.故障恢復：-使用心跳檢測節(jié)點狀態(tài)，若節(jié)點超時則重新分配其鍵值對到其他節(jié)點。-使用多副本機制，確保數(shù)據(jù)不丟失。解析：核心是節(jié)點分配和RPC通信。一致性哈希保證鍵值對均勻分布，RPC實現(xiàn)節(jié)點間同步，心跳檢測和副本機制保證高可用性。2.（10分）題目：設計一個簡單的分布式計數(shù)器服務。多個客戶端可以并發(fā)地增加計數(shù)器，服務需要保證計數(shù)器值的準確性。要求：-支持高并發(fā)訪問。-計數(shù)器值準確，無重復或丟失。答案與解析：答案：1.數(shù)據(jù)存儲：-使用Redis或分布式數(shù)據(jù)庫存儲計數(shù)器值。-使用Redis的`INCR`命令實現(xiàn)原子增加。2.高并發(fā)處理：-客戶端通過RPC調(diào)用服務器的`increment`方法。-服務器使用鎖或原子操作保證計數(shù)器準確性。3.分布式鎖：-使用分布式鎖（如Redis鎖）確保同一時間只有一個客戶端修改計數(shù)器。解析：核心是原子操作和鎖機制。Redis的`INCR`命令保證原子性，分布式鎖防止并發(fā)沖突。高并發(fā)下通過Redis優(yōu)化性能。五、編程語言與編碼實踐（共2題，每題10分，總分20分）1.（10分）題目：給定一個字符串`s`，請編寫代碼將其反轉(zhuǎn)，但不能使用內(nèi)置的