2026年微軟技術面試題目及答案參考編程題（5題，每題15分，共75分）1.題目（15分）：編寫一個函數(shù)，輸入一個正整數(shù)`n`，返回`n`的“數(shù)字翻轉(zhuǎn)”結(jié)果。例如，輸入`123`返回`321`，輸入`120`返回`21`（注意：翻轉(zhuǎn)后前導零應被忽略）。要求不使用內(nèi)置的字符串反轉(zhuǎn)函數(shù)，僅用整數(shù)操作實現(xiàn)。答案與解析：pythondefreverse_integer(n:int)->int:INT_MAX=231-1INT_MIN=-231result=0sign=-1ifn<0else1n=abs(n)whilen!=0:pop=n%10n=n//10檢查溢出ifresult>(INT_MAX-pop)//10:return0result=result10+popreturnsignresult解析：-整數(shù)反轉(zhuǎn)時需處理符號位，先取絕對值處理，最后再還原符號。-逐位取余數(shù)（`n%10`）得到當前最低位，然后除以10（`n//10`）去掉該位。-翻轉(zhuǎn)時需檢查是否溢出，即`result10+pop`是否超過`INT_MAX`或`INT_MIN`。-時間復雜度O(logn)，空間復雜度O(1)。2.題目（15分）：給定一個無重復元素的數(shù)組`nums`和一個目標值`target`，找出`nums`中所有和為`target`的不重復四元組。例如，輸入`[1,0,-1,0]`和`target=0`，返回`[[-1,0,0,1],[0,0,0,0]]`。答案與解析：pythondeffour_sum(nums,target):nums.sort()n=len(nums)res=[]foriinrange(n-3):ifi>0andnums[i]==nums[i-1]:continueforjinrange(i+1,n-2):ifj>i+1andnums[j]==nums[j-1]:continueleft,right=j+1,n-1whileleft<right:total=nums[i]+nums[j]+nums[left]+nums[right]iftotal==target:res.append([nums[i],nums[j],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnres解析：-先排序，避免重復解。-固定前兩個指針`i`和`j`，用雙指針`left`和`right`查找剩余的兩個數(shù)。-避免重復解：跳過與前一個相同的元素。-時間復雜度O(n3)，空間復雜度O(1)。3.題目（15分）：實現(xiàn)一個LRU（LeastRecentlyUsed）緩存，支持`get`和`put`操作。LRU緩存最多容納`capacity`個元素，超出時淘汰最久未使用的元素。例如：-初始化`capacity=2`：-`put(1,1)`→緩存為`{1:1}`-`put(2,2)`→緩存為`{1:1,2:2}`-`get(1)`→返回`1`（訪問1，更新使用順序）-`put(3,3)`→剩余空間不足，淘汰`2`，緩存為`{1:1,3:3}`-`get(2)`→返回`-1`（未命中）答案與解析：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`維護元素使用順序，`move_to_end`用于更新訪問順序。-`get`時若命中則移動到末尾，返回值；否則返回`-1`。-`put`時若已存在則更新值并移動到末尾；若超出容量則彈出第一個元素（最久未使用）。-時間復雜度O(1)，空間復雜度O(capacity)。4.題目（15分）：給定一個二叉樹，判斷其是否為平衡二叉樹。平衡二叉樹定義：對于任意節(jié)點，其左右子樹高度差不超過1。例如：3/\920/\157是平衡二叉樹。答案與解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root:TreeNode)->bool:defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]解析：-遞歸檢查每個節(jié)點的高度，同時判斷左右子樹是否平衡。-返回值：當前節(jié)點的高度，以及當前子樹是否平衡。-若任意節(jié)點不平衡（高度差>1），則整棵樹不平衡。-時間復雜度O(n)，空間復雜度O(h)（h為樹高）。5.題目（15分）：實現(xiàn)一個“合并區(qū)間”函數(shù)，輸入一個區(qū)間列表（每個區(qū)間為`[start,end]`），合并所有重疊的區(qū)間，并返回合并后的區(qū)間列表。例如：輸入`[[1,3],[2,6],[8,10],[15,18]]`，輸出`[[1,6],[8,10],[15,18]]`。答案與解析：pythondefmerge_intervals(intervals):ifnotintervals:return[]intervals.sort(key=lambdax:x[0])merged=[intervals[0]]forcurrentinintervals[1:]:last=merged[-1]ifcurrent[0]<=last[1]:#重疊last[1]=max(last[1],current[1])else:merged.append(current)returnmerged解析：-先按區(qū)間起始位置排序。-遍歷區(qū)間，若當前區(qū)間與前一個區(qū)間重疊（`current[0]<=last[1]`），則合并（更新`last[1]`）。-若不重疊，則直接添加到結(jié)果中。-時間復雜度O(nlogn)，空間復雜度O(n)。系統(tǒng)設計題（2題，每題25分，共50分）1.題目（25分）：設計一個簡單的微博“實時推文”系統(tǒng)。要求：-用戶發(fā)布推文時，其他用戶能近乎實時看到該推文（延遲不超過1秒）。-系統(tǒng)需支持至少10,000個并發(fā)用戶，推文數(shù)每日增長約1億條。-提供兩種查看方式：按用戶查看（關注列表）、按時間查看（最新推文）。答案與解析：系統(tǒng)架構(gòu)：1.數(shù)據(jù)存儲：-推文存儲：使用分布式數(shù)據(jù)庫（如Cassandra或RocksDB）存儲推文，按用戶ID或時間索引，支持快速寫入和讀取。-用戶關注關系：使用Redis哈希表存儲用戶關注關系（`user:follows:{userId}`），支持快速查詢。2.實時推文分發(fā)：-發(fā)布流程：-用戶發(fā)布推文時，寫入數(shù)據(jù)庫并廣播給該用戶的所有關注者（使用RedisPub/Sub或Kafka）。-優(yōu)化：-使用“流式拉取”而非“全量推送”，每個用戶維護一個輕量級訂閱隊列，僅接收增量更新。-異步寫入磁盤，保證寫入性能。-訂閱優(yōu)化：-使用“布隆過濾器”預判用戶是否關注某賬號，減少無效推送。-按用戶分組推送，避免單節(jié)點壓力過大。3.讀取服務：-按用戶查看：直接查詢數(shù)據(jù)庫，支持緩存熱點用戶推文（如Redis）。-按時間查看：使用LevelDB或時間序列數(shù)據(jù)庫（如InfluxDB）按時間索引推文，支持分頁查詢。4.高可用與擴展：-推文服務分片（Sharding），按用戶ID哈希分配到不同節(jié)點。-使用負載均衡器（如Nginx）分發(fā)請求。-監(jiān)控系統(tǒng)（如Prometheus+Grafana）實時監(jiān)控延遲、QPS等指標。技術選型理由：-Redis：高性能鍵值存儲，適合存儲關注關系和流式隊列。-分布式數(shù)據(jù)庫：支持海量寫入和水平擴展。-流式架構(gòu)：保證低延遲，避免阻塞主線程。2.題目（25分）：設計一個支持高并發(fā)的“短鏈接生成與解析”系統(tǒng)。要求：-輸入任意長鏈接，生成6位短鏈接（如`/a1b2c`）。-短鏈接解析時，能快速定位原始長鏈接（延遲<100ms）。-系統(tǒng)需支持日均1000萬次訪問，且短鏈接唯一性要求極高。答案與解析：系統(tǒng)架構(gòu)：1.短鏈接生成：-編碼算法：-使用62進制（`a-z`、`A-Z`、`0-9`）對ID進行編碼，6位可表示62?=56.8億個ID。-映射關系：`{0:a,1:b,...,61:zA0}`。-ID生成：-使用分布式唯一ID生成器（如TwitterSnowflake算法），確保全局唯一。-寫入Redis或分布式數(shù)據(jù)庫，支持快速查詢。2.短鏈接解析：-用戶訪問短鏈接時，DNS解析至負載均衡器（如HAProxy）。-負載均衡器將請求轉(zhuǎn)發(fā)至服務集群。-服務端通過短鏈接的6位ID快速查詢單個長鏈接（Redis緩存熱點ID）。-若未命中緩存，則查詢數(shù)據(jù)庫，并緩存結(jié)