2026年微軟公司軟件開(kāi)發(fā)面試題及答案詳解一、編程題（共5題，每題15分，總分75分）1.題目（15分）：編寫一個(gè)函數(shù)，輸入一個(gè)正整數(shù)`n`，返回`n`的所有因子（不包括`n`本身）的平方和。例如，輸入`12`，返回`1^2+2^2+3^2+4^2+6^2=1+4+9+16+36=66`。答案：pythondefsum_of_square_factors(n):ifn<=1:return0sum=0foriinrange(1,n):ifn%i==0:sum+=iireturnsum示例print(sum_of_square_factors(12))#輸出：66解析：-遍歷從`1`到`n-1`的所有數(shù)，檢查是否能整除`n`，若能則計(jì)算其平方并累加。-時(shí)間復(fù)雜度：`O(n)`，可通過(guò)優(yōu)化到`O(√n)`（遍歷到`√n`即可，因因子成對(duì)出現(xiàn)）。2.題目（15分）：給定一個(gè)字符串列表`words`，返回其中最長(zhǎng)的“回文子串”的長(zhǎng)度。例如，輸入`["abc","deed","cda","racecar"]`，返回`6`（"racecar"長(zhǎng)度為6）。答案：pythondeflongest_palindrome_substring(words):ifnotwords:return0max_len=0forwordinwords:ifword==word[::-1]:#判斷是否為回文max_len=max(max_len,len(word))returnmax_len示例print(longest_palindrome_substring(["abc","deed","cda","racecar"]))#輸出：6解析：-直接遍歷每個(gè)字符串，檢查是否為回文（正反相同）。-優(yōu)化方法：動(dòng)態(tài)規(guī)劃或中心擴(kuò)展法可降低時(shí)間復(fù)雜度至`O(n^2)`。3.題目（15分）：實(shí)現(xiàn)一個(gè)`LRU緩存`（LeastRecentlyUsed）的設(shè)計(jì)，支持`get`和`put`操作。`get(key)`返回`key`對(duì)應(yīng)的值，若不存在返回`-1`；`put(key,value)`插入或更新鍵值對(duì)，當(dāng)緩存容量滿時(shí)，刪除最久未使用的鍵。答案：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_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)示例lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#輸出：1lru.put(3,3)#去除鍵2print(lru.get(2))#輸出：-1解析：-使用字典`cache`存儲(chǔ)鍵值對(duì)，列表`order`記錄訪問(wèn)順序。-`get`操作將鍵移到末尾表示最近使用，`put`操作需處理容量滿的情況。-可使用`collections.OrderedDict`優(yōu)化實(shí)現(xiàn)。4.題目（15分）：設(shè)計(jì)一個(gè)算法，找出數(shù)組中重復(fù)次數(shù)超過(guò)`n/2`的元素。例如，輸入`[3,2,3,1,3,3,3]`，返回`3`。答案：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate示例print(majority_element([3,2,3,1,3,3,3]))#輸出：3解析：-Boyer-Moore投票算法：多數(shù)元素會(huì)抵消其他元素，最終保留候選者。-時(shí)間復(fù)雜度：`O(n)`，空間復(fù)雜度：`O(1)`。5.題目（15分）：給定一個(gè)二叉樹(shù)，判斷其是否為“完全二叉樹(shù)”（除最后一層外，每一層節(jié)點(diǎn)都滿，且最后一層節(jié)點(diǎn)從左到右連續(xù)）。例如：1/\23/\45答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_complete_binary_tree(root):ifnotroot:returnTruequeue=deque([root])flag=Falsewhilequeue:node=queue.popleft()ifnode:ifflag:returnFalsequeue.append(node.left)queue.append(node.right)else:flag=TruereturnTrue示例root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print(is_complete_binary_tree(root))#輸出：True解析：-層序遍歷：若遇到`None`后再出現(xiàn)非`None`節(jié)點(diǎn)，則不滿足完全二叉樹(shù)。-使用隊(duì)列實(shí)現(xiàn)BFS，通過(guò)`flag`標(biāo)記是否已遇到`None`。二、系統(tǒng)設(shè)計(jì)題（共2題，每題25分，總分50分）1.題目（25分）：設(shè)計(jì)一個(gè)短鏈接（TinyURL）服務(wù)，要求：-輸入任意長(zhǎng)URL，返回固定長(zhǎng)度短鏈接（如`/abcd`）。-支持通過(guò)短鏈接反查原始URL。-高并發(fā)場(chǎng)景下保證唯一性和快速響應(yīng)。答案：系統(tǒng)架構(gòu)：1.短鏈接生成：使用Base62編碼（`a-z`、`A-Z`、`0-9`）將ID映射為6位短碼。2.存儲(chǔ)：-使用Redis（緩存熱點(diǎn)數(shù)據(jù)）+數(shù)據(jù)庫(kù)（持久化）。-映射表：`{"abcd":"/long-url"}`。3.高并發(fā)處理：-請(qǐng)求先走負(fù)載均衡（如Nginx）。-Redis使用原子操作（如`INCR`）生成唯一ID。代碼示例（偽代碼）：pythonimportbase64importredisclassTinyURL:def__init__(self):self.redis=redis.Redis()self.base="/"defencode(self,long_url):生成唯一IDid=self.redis.incr("url_id")short_code=base64.urlsafe_b64encode(id.to_bytes(6,'big')).decode()[:6]self.redis.set(short_code,long_url)returnself.base+short_codedefdecode(self,short_url):short_code=short_url.split('/')[-1]returnself.redis.get(short_code)or"URLnotfound"解析：-Base62編碼：將ID轉(zhuǎn)為短碼（如`1000`→`1rw`）。-高并發(fā)優(yōu)化：Redis原子操作確保ID唯一，避免鎖。-擴(kuò)展性：可分片存儲(chǔ)（如按首字母分庫(kù)）。2.題目（25分）：設(shè)計(jì)一個(gè)實(shí)時(shí)消息推送系統(tǒng)，支持多用戶訂閱主題（Topic），發(fā)布消息時(shí)推送給所有訂閱者。要求：-支持“廣播”和“單播”（指定用戶）。-低延遲（毫秒級(jí)）。-高可用（支持集群）。答案：系統(tǒng)架構(gòu)：1.核心組件：-消息隊(duì)列（Kafka/RabbitMQ）：解耦發(fā)布與訂閱。-訂閱中心（Redis+發(fā)布訂閱）：存儲(chǔ)用戶-主題關(guān)系，實(shí)時(shí)推送。2.流程：-訂閱：用戶請(qǐng)求加入主題，Redis記錄`{topic:[user1,user2]}`。-發(fā)布：-廣播：將消息推送到Kafka，訂閱中心監(jiān)聽(tīng)主題，通知所有訂閱者。-單播：直接向指定用戶發(fā)送WebSocket消息。3.高可用：-消息隊(duì)列集群（如Kafka多副本）。-Redis集群（主從+哨兵）。代碼示例（偽代碼）：python訂閱邏輯defsubscribe(user,topic):redis.sadd(f"topic:{topic}",user)發(fā)布邏輯defpublish(topic,message):廣播kafka_producer.send(topic,message)通知訂閱者subscribed_users=redis.smembers(f"topic:{topic}")foruserinsubscribed_users:websocket.send(user,message)解析：-低延遲：消息隊(duì)列確保發(fā)布解耦，Redis實(shí)時(shí)推送。-高可用：Kafka保證消息不丟失，Redis集群防單點(diǎn)。-擴(kuò)展性：可增加限流（如令牌桶算法）防壓垮。答案與解析匯總編程題答案：1.因子平方和：遍歷除`n`外所有數(shù)，計(jì)算平方和。2.最長(zhǎng)回文子串：遍歷字符串檢查回文，或使用動(dòng)態(tài)規(guī)劃。3.LRU緩存：使用字典