2026年微軟公司軟件開發(fā)面試題庫及參考答案一、編程基礎(chǔ)（5題，每題10分）說明：考察編程語言基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)和算法能力。1.題目：編寫一個(gè)函數(shù)，接收一個(gè)字符串，返回該字符串中所有唯一字符的列表（不區(qū)分大小寫）。示例：輸入：`"HelloWorld"`輸出：`['H','e','W','r','d']`要求：-時(shí)間復(fù)雜度O(n)-空間復(fù)雜度O(1)（不考慮輸入字符串占用的空間）2.題目：實(shí)現(xiàn)一個(gè)LRU（最近最少使用）緩存，支持get和put操作。要求：-get(key)：返回key對(duì)應(yīng)的值，如果不存在返回-1-put(key,value)：插入或更新key對(duì)應(yīng)的值，如果緩存容量已滿，則刪除最近最少使用的項(xiàng)示例：LRU緩存容量為2put(1,1)→緩存是{1=1}put(2,2)→緩存是{1=1,2=2}get(1)→返回1put(3,3)→去除鍵2，緩存是{1=1,3=3}get(2)→返回-1（未找到）3.題目：給定一個(gè)鏈表，判斷其是否為回文鏈表。示例：輸入：`1->2->2->1`輸出：`true`要求：-不使用額外空間4.題目：實(shí)現(xiàn)快速排序算法。要求：-手寫代碼，不調(diào)用庫函數(shù)-解釋時(shí)間復(fù)雜度和空間復(fù)雜度5.題目：編寫一個(gè)函數(shù)，判斷一個(gè)整數(shù)是否是UglyNumber（丑數(shù)，只包含質(zhì)因數(shù)2、3、5的數(shù)）。示例：輸入：`6`輸出：`true`要求：-時(shí)間復(fù)雜度O(logn)二、系統(tǒng)設(shè)計(jì)（3題，每題20分）說明：考察分布式系統(tǒng)、數(shù)據(jù)庫和高并發(fā)設(shè)計(jì)能力。1.題目：設(shè)計(jì)一個(gè)高并發(fā)的短鏈接系統(tǒng)（如tinyURL）。要求：-解釋URL編碼過程-如何保證生成的短鏈接唯一且可逆-如何應(yīng)對(duì)高并發(fā)訪問2.題目：設(shè)計(jì)一個(gè)微博系統(tǒng)，支持以下功能：-用戶發(fā)布/刪除/查看微博-關(guān)注/取消關(guān)注用戶-實(shí)時(shí)獲取關(guān)注用戶的最新動(dòng)態(tài)要求：-說明數(shù)據(jù)庫表設(shè)計(jì)-如何實(shí)現(xiàn)實(shí)時(shí)消息推送3.題目：設(shè)計(jì)一個(gè)分布式計(jì)數(shù)器，支持高并發(fā)更新。要求：-說明實(shí)現(xiàn)方案（如Redis、分布式鎖）-如何保證計(jì)數(shù)器的原子性三、算法題（4題，每題15分）說明：考察動(dòng)態(tài)規(guī)劃、貪心算法和圖論算法。1.題目：給定一個(gè)整數(shù)數(shù)組，返回三個(gè)數(shù)，使這三個(gè)數(shù)的和最接近給定的數(shù)target。示例：輸入：`[-1,2,1,-4]`,target=1輸出：`2(-1+2+1)`要求：-時(shí)間復(fù)雜度O(n^2)2.題目：在社交媒體中，有N個(gè)用戶，每個(gè)用戶可以互相關(guān)注。判斷是否存在一個(gè)用戶，可以通過關(guān)注其他用戶來覆蓋所有用戶（即形成一個(gè)傳遞閉包）。示例：輸入：`edges=[[1,2],[2,3],[3,4],[4,1]]`輸出：`false`要求：-使用圖論算法（如DFS/BFS）3.題目：給定一個(gè)非負(fù)整數(shù)數(shù)組，每個(gè)元素代表高度，計(jì)算由這些高度構(gòu)成的水桶能接多少雨水量。示例：輸入：`[0,1,0,2,1,0,1,3,2,1,2,1]`輸出：`6`要求：-使用雙指針法4.題目：實(shí)現(xiàn)一個(gè)LRU緩存，支持容量動(dòng)態(tài)調(diào)整。要求：-解釋如何處理容量變化對(duì)緩存的影響四、數(shù)據(jù)庫與存儲(chǔ)（2題，每題15分）說明：考察SQL、NoSQL和數(shù)據(jù)庫優(yōu)化能力。1.題目：編寫SQL查詢，找出在2023年1月入職且月薪高于公司平均月薪的員工列表。要求：-假設(shè)表結(jié)構(gòu)包括`employees(id,name,salary,hire_date)`2.題目：設(shè)計(jì)一個(gè)分布式數(shù)據(jù)庫分片方案，支持水平擴(kuò)展。要求：-說明分片鍵的選擇原則-如何解決分片鍵沖突問題五、編碼實(shí)現(xiàn)（3題，每題20分）說明：考察實(shí)際編碼能力和問題解決能力。1.題目：編寫一個(gè)函數(shù)，判斷一個(gè)字符串是否是有效的括號(hào)組合（如`"()[]{}"`）。要求：-使用棧實(shí)現(xiàn)-處理嵌套括號(hào)2.題目：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的LRU緩存，使用Python字典實(shí)現(xiàn)（不要求高效）。要求：-支持get和put操作-不考慮性能優(yōu)化3.題目：編寫一個(gè)函數(shù)，將一個(gè)BST（二叉搜索樹）轉(zhuǎn)換為排序的雙向鏈表。要求：-在原樹結(jié)構(gòu)上操作，不創(chuàng)建新節(jié)點(diǎn)-雙向鏈表支持前驅(qū)和后繼遍歷參考答案與解析一、編程基礎(chǔ)1.唯一字符列表答案：pythondefunique_chars(s:str):s=s.lower()freq={}forcharins:freq[char]=freq.get(char,0)+1return[charforcharinset(s)iffreq[char]==1]解析：-首先將字符串轉(zhuǎn)為小寫，忽略大小寫差異-使用字典統(tǒng)計(jì)字符頻率-返回頻率為1的字符（即唯一字符）2.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:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：-使用字典存儲(chǔ)緩存數(shù)據(jù)，列表維護(hù)訪問順序-get操作將訪問的key移到末尾-put操作先刪除最久未使用的key（列表頭部），再插入新數(shù)據(jù)3.回文鏈表答案：pythondefisPalindrome(head:ListNode)->bool:slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.next反轉(zhuǎn)后半部分prev=Nonewhileslow:tmp=slow.nextslow.next=prevprev=slowslow=tmp對(duì)比前后半部分left,right=head,prevwhileright:ifleft.val!=right.val:returnFalseleft=left.nextright=right.nextreturnTrue解析：-快慢指針找到中點(diǎn)，反轉(zhuǎn)后半部分-對(duì)比前后半部分是否相同4.快速排序答案：pythondefquicksort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquicksort(left)+middle+quicksort(right)解析：-時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(logn)（遞歸棧）5.丑數(shù)答案：pythondefisUgly(n:int)->bool:ifn<=0:returnFalseforprimein[2,3,5]:whilen%prime==0:n//=primereturnn==1解析：-不斷除以2、3、5，直到無法整除-最終n應(yīng)為1二、系統(tǒng)設(shè)計(jì)1.短鏈接系統(tǒng)答案：-URL編碼：使用62進(jìn)制（a-z,A-Z,0-9）將ID映射為短字符串pythondefencode(num:int)->str:chars="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"ifnum==0:returnchars[0]base=62result=[]whilenum:result.append(chars[num%base])num//=basereturn''.join(reversed(result))-唯一性：使用UUID生成唯一ID，或自增ID結(jié)合hash-高并發(fā)：使用Redis緩存熱點(diǎn)URL，分布式鎖防沖突2.微博系統(tǒng)表設(shè)計(jì)：sqlCREATETABLEtweets(idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINT,contentTEXT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP);CREATETABLEfollowers(follower_idBIGINT,followee_idBIGINT,PRIMARYKEY(follower_id,followee_id));實(shí)時(shí)推送：使用WebSocket或MQ（如Kafka）異步通知3.分布式計(jì)數(shù)器方案：-Redis：使用`INCR`命令redisINCRcounter_name-分布式鎖：pythonimportthreadinglock=threading.Lock()defincrement(counter):withlock:counter+=1三、算法題1.三數(shù)之和最接近答案：pythondefthreeSumClosest(nums,target):nums.sort()n=len(nums)closest=float('inf')foriinrange(n-2):left,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]ifabs(total-target)<abs(closest-target):closest=totaliftotal<target:left+=1else:right-=1returnclosest解析：-排序后固定一個(gè)數(shù)，雙指針找另外兩個(gè)數(shù)-時(shí)間復(fù)雜度O(n^2)2.傳遞閉包答案：pythondefis_possible(n,edges):fromcollectionsimportdefaultdictgraph=defaultdict(list)foru,vinedges:graph[u].append(v)graph[v].append(u)visited=[False](n+1)defdfs(node):visited[node]=Trueforneighboringraph[node]:ifnotvisited[neighbor]:dfs(neighbor)dfs(1)returnall(visited[1:])解析：-使用DFS判斷所有節(jié)點(diǎn)是否可達(dá)3.雨水量答案：pythondeftrap(height):left,right=0,len(height)-1left_max,right_max=0,0water=0whileleft<right:ifheight[left]<height[right]:ifheight[left]>=left_max:left_max=height[left]else:water+=left_max-height[left]left+=1else:ifheight[right]>=right_max:right_max=height[right]else:water+=right_max-height[right]right-=1returnwater解析：-雙指針法，維護(hù)左右最大高度4.動(dòng)態(tài)LRU緩存答案：pythonclassDynamicLRUCache:def__init__(self,initial_capacity=2):self.capacity=initial_capacityself.cache={}self.order=[]defresize(self,new_capacity):self.capacity=new_capacity移除多余項(xiàng)whilelen(self.cache)>self.capacity:oldest=self.order.pop(0)delself.cache[oldest]四、數(shù)據(jù)庫與存儲(chǔ)1.SQL查詢答案：sqlSELECTnameFROMemployeesWHEREhire_dateBETWEEN'2023-01-01'AND'2023-12-31'ANDsalary>(SELECTAVG(salary)FROMemployees);解析：-子查詢計(jì)算平均月薪，外層查詢篩選達(dá)標(biāo)員工2.分布式數(shù)據(jù)庫分片方案：-分片鍵選擇：-用戶ID（均勻分布）-地域ID（如省份）-解決沖突：-哈希取模（如`hash(key)%N`）-順序取模（如`key%N`）五、編碼實(shí)現(xiàn)1.有效括號(hào)答案：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack2.簡(jiǎn)易LRU緩存答案：pythonclassSimple