2026年微軟技術(shù)部門面試題集及解答一、編程算法題（共5題，每題15分）1.題目：給定一個包含重復(fù)元素的數(shù)組，返回所有不重復(fù)的全排列。例如，輸入`[1,1,2]`，輸出`[[1,1,2],[1,2,1],[2,1,1]]`。要求：時間復(fù)雜度優(yōu)于O(n!)。答案：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()res=[]used=[False]len(nums)backtrack([],used,res)returnres示例print(permute_unique([1,1,2]))解析：-先對數(shù)組排序，便于跳過重復(fù)元素。-使用`used`數(shù)組記錄每個元素是否被使用，避免重復(fù)。-當遇到與前一個元素相同且前一個元素未被使用時，跳過以避免重復(fù)排列。-時間復(fù)雜度：O(n!n)，空間復(fù)雜度：O(n!n)。2.題目：實現(xiàn)一個LRU（最近最少使用）緩存，支持`get`和`put`操作。要求：`get`操作返回鍵對應(yīng)的值，若不存在返回`-1`；`put`操作將鍵值對插入緩存，如果緩存已滿則刪除最久未使用的元素。答案：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:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)示例cache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#返回1cache.put(3,3)#去除鍵2print(cache.get(2))#返回-1解析：-使用字典`cache`存儲鍵值對，列表`order`記錄訪問順序。-`get`操作時，將訪問的鍵移動到列表末尾。-`put`操作時，若鍵已存在則更新值并移動位置；若緩存已滿，則刪除列表第一個元素（最久未使用）。-時間復(fù)雜度：O(1)。3.題目：給定一個二叉樹，返回其“鋸齒形”層序遍歷（即第一層從左到右，第二層從右到左，以此類推）。答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefzigzagLevelOrder(root:TreeNode)->List[List[int]]:ifnotroot:return[]res=[]queue=deque([root])left_to_right=Truewhilequeue:level=[]for_inrange(len(queue)):node=queue.popleft()ifleft_to_right:level.append(node.val)else:level.insert(0,node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)left_to_right=notleft_to_rightreturnres示例構(gòu)建二叉樹：3/\920/\157root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)print(zigzagLevelOrder(root))解析：-使用雙端隊列`queue`實現(xiàn)層序遍歷。-使用布爾值`left_to_right`控制方向：True為從左到右，F(xiàn)alse為從右到左。-每層遍歷后反轉(zhuǎn)方向。-時間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)。4.題目：給定一個非負整數(shù)數(shù)組，返回一個數(shù)組`answer`，其中`answer[i]`是數(shù)組中比`nums[i]`小的數(shù)字的個數(shù)。答案：pythondefsmallerNumbersThanCurrent(nums:List[int])->List[int]:sorted_nums=sorted(nums)rank={num:ifori,numinenumerate(sorted_nums)}return[rank[num]fornuminnums]示例print(smallerNumbersThanCurrent([8,1,2,2,3]))解析：-先對數(shù)組排序，記錄每個數(shù)字的排名。-然后根據(jù)原數(shù)組數(shù)字的排名生成結(jié)果。-時間復(fù)雜度：O(nlogn)，空間復(fù)雜度：O(n)。5.題目：實現(xiàn)一個函數(shù)，判斷一個字符串是否是有效的括號組合（只包含`()`,`[]`,`{}`）。答案：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack示例print(isValid("{[]}()"))#Trueprint(isValid("([)]"))#False解析：-使用棧存儲左括號，遇到右括號時檢查棧頂是否匹配。-若棧為空或棧頂不匹配，則無效。-時間復(fù)雜度：O(n)，空間復(fù)雜度：O(n)。二、系統(tǒng)設(shè)計題（共3題，每題20分）1.題目：設(shè)計一個短鏈接服務(wù)（如TinyURL），要求：-輸入任意長鏈接，返回短鏈接。-支持通過短鏈接查詢原始長鏈接。-高并發(fā)場景下仍能快速響應(yīng)。答案：-數(shù)據(jù)結(jié)構(gòu)：-使用哈希表存儲短鏈接與長鏈接的映射。-使用自增ID或隨機生成短碼（如`a-z0-9`），確保唯一性。-高并發(fā)優(yōu)化：-使用Redis高性能緩存存儲映射關(guān)系。-使用分布式鎖處理寫入沖突。-分布式部署：-部署多個服務(wù)節(jié)點，使用負載均衡分配請求。-數(shù)據(jù)庫使用分片或一致性哈希避免單點瓶頸。2.題目：設(shè)計一個實時微博發(fā)布系統(tǒng)，要求：-用戶可以發(fā)布、關(guān)注、點贊微博。-實時顯示用戶關(guān)注者的最新動態(tài)（類似Twitter流）。-支持百萬級用戶和每秒千條動態(tài)。答案：-架構(gòu)：-前端：WebSocket實現(xiàn)實時推流。-后端：微服務(wù)架構(gòu)（發(fā)布、關(guān)注、點贊、流服務(wù)分離）。-數(shù)據(jù)庫：-發(fā)布數(shù)據(jù)使用NoSQL（如MongoDB）存儲，快速寫入。-關(guān)注關(guān)系使用Redis存儲用戶關(guān)注列表。-實時流處理：-使用Kafka或Pulsar存儲動態(tài)，流服務(wù)訂閱并分發(fā)到關(guān)注者。-消息隊列解耦寫入和讀取，避免性能瓶頸。3.題目：設(shè)計一個分布式URL緩存系統(tǒng)，要求：-用戶訪問URL時，先查詢緩存，未命中再請求原始服務(wù)器。-緩存熱點數(shù)據(jù)，減少重復(fù)請求。-支持緩存過期和淘汰策略。答案：-架構(gòu)：-使用CDN邊緣節(jié)點緩存靜態(tài)資源。-后端使用分布式緩存（如RedisCluster）。-緩存策略：-使用LRU或LFU淘汰策略。-使用TTL機制自動過期。-負載均衡：-使用DNS或負載均衡器調(diào)度請求。-避免緩存雪崩（預(yù)熱熱點數(shù)據(jù)）。三、數(shù)據(jù)庫與SQL題（共2題，每題15分）1.題目：給定表`Orders`（訂單表）和`Customers`（客戶表），編寫SQL查詢：-返回每個客戶的訂單總數(shù)，以及訂單總金額。-客戶名為"Alice"的數(shù)據(jù)單獨列出。答案：sqlSELECTc.Name,COUNT(o.OrderID)ASTotalOrders,SUM(o.Amount)ASTotalAmountFROMOrdersoJOINCustomerscONo.CustomerID=c.CustomerIDGROUPBYc.NameUNIONALLSELECT'Alice'ASName,(SELECTCOUNT()FROMOrdersWHERECustomerID=(SELECTCustomerIDFROMCustomersWHEREName='Alice')),(SELECTSUM(Amount)FROMOrdersWHERECustomerID=(SELECTCustomerIDFROMCustomersWHEREName='Alice'))解析：-使用`JOIN`連接表并按客戶分組統(tǒng)計。-使用`UNIONALL`單獨查詢Alice的數(shù)據(jù)。2.題目：表`Products`（產(chǎn)品表）有字段`Category`,`Price`，編寫SQL：-返回每個分類的平均價格，且只保留價格中位數(shù)最高的分類。答案：sqlWITHRankedCategoriesAS(SELECTCategory,AVG(Price)ASAvgPrice,ROW_NUMBER()OVER(ORDERBYAVG(Price)DESC)ASRankFROMProductsGROUPBYCategory)SELECTCategory,AvgPriceFROMRankedCategoriesWHERERank=1解析：-使用窗口函數(shù)`ROW_NUMBER()`排序分類。-只返回排名第一的分類。四、網(wǎng)絡(luò)與系統(tǒng)題（共2題，每題15分）1.題目：解釋TCP的三次握手和四次揮手過程，并說明為什么不能省略任何一步。答案：-三次握手：1.客戶端發(fā)送SYN包，進入`SYN_SENT`狀態(tài)。2.服務(wù)器回復(fù)SYN-ACK包，進入`SYN_RCVD`狀態(tài)。3.客戶端發(fā)送ACK包，進入`ESTABLISHED`狀態(tài)。-目的：雙方確認雙方都有發(fā)送和接收能力。-四次揮手：1.客戶端發(fā)送FIN包，進入`FIN_WAIT_1`。2.服務(wù)器回復(fù)ACK包，進入`CLOSE_WAIT`。3.服務(wù)器發(fā)送FIN包，進入`LAST_ACK`。4.客戶端回復(fù)ACK包，進入`TIME_WAIT`，等待2MSL后關(guān)閉。-目的：確保雙方數(shù)據(jù)傳輸完成且沒有遺漏。2.題目：如何優(yōu)化網(wǎng)站首頁加載速度？列舉至少三種方法。答案：1.CDN加速：將靜態(tài)資源（圖片、JS、CSS）部署到CDN，減少服務(wù)器負載和延遲。2.圖片優(yōu)化：壓縮圖片（如WebP格式）、懶加載、使用CDN分片。3.代碼優(yōu)化：代碼壓縮、合并文件、使用HTTP/2多路復(fù)用。五、編程語言與并發(fā)題（共2題，每題15分）1.題目：解釋Python中的GIL是什么，以及如何實現(xiàn)多線程并發(fā)計算？答案：-GIL（全局