2026年微軟面試題及答案詳解編程題（共5題，每題20分，總分100分）題目1（20分）：問題描述：給定一個字符串`s`和一個正整數(shù)`k`，請編寫一個函數(shù)，返回所有長度為`k`的子串中，出現(xiàn)頻率最高的子串。如果有多個子串頻率相同，返回所有這些子串。示例：輸入：`s="aabbcc",k=2`輸出：`["aa","bb"]`提示：-字符串僅包含小寫字母。-`1<=k<=s.length()`。答案：pythondefhighest_frequency_substrings(s:str,k:int)->list:fromcollectionsimportdefaultdict1.統(tǒng)計所有長度為k的子串頻率count=defaultdict(int)foriinrange(len(s)-k+1):substring=s[i:i+k]count[substring]+=12.找到最大頻率max_freq=max(count.values())3.收集所有最大頻率的子串result=[keyforkey,valincount.items()ifval==max_freq]returnresult解析：1.統(tǒng)計子串頻率：使用滑動窗口遍歷所有長度為`k`的子串，并記錄每個子串的出現(xiàn)次數(shù)。2.確定最大頻率：遍歷頻率字典，找到最高頻率值。3.收集結果：篩選出所有頻率等于最大頻率的子串，返回列表。時間復雜度：O(n·k)，其中n為字符串長度。題目2（20分）：問題描述：設計一個LRU（LeastRecentlyUsed）緩存數(shù)據(jù)結構，支持以下操作：-`get(key)`:獲取鍵`key`對應的值，如果不存在返回-1。獲取后，將鍵值對移動到緩存最前面（表示最近使用）。-`put(key,value)`:插入或更新鍵值對。如果緩存已滿，刪除最久未使用的鍵值對，然后插入或更新。示例：LRU=LRUCache(2)LRU.put(1,1)LRU.put(2,2)LRU.get(1)#返回1LRU.put(3,3)#去除鍵2LRU.get(2)#返回-1(未找到)提示：-緩存容量`capacity`恒定。-支持O(1)時間復雜度的操作。答案：pythonclassNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}初始化雙向鏈表頭尾self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node:Node):添加節(jié)點到鏈表頭部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node:Node):刪除鏈表中的節(jié)點prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node:Node):將節(jié)點移動到鏈表頭部self._remove_node(node)self._add_node(node)def_pop_tail(self)->Node:彈出鏈表尾部節(jié)點res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1移動節(jié)點到頭部self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnode:node.value=valueself._move_to_head(node)else:newNode=Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]解析：1.雙向鏈表：維護最近使用順序，頭部為最近使用，尾部為最久未使用。2.哈希表：O(1)時間查找節(jié)點。3.操作邏輯：-`get`：查找節(jié)點，移動到頭部，返回值。-`put`：插入新節(jié)點到頭部，如果超出容量，刪除尾部節(jié)點。時間復雜度：O(1)。題目3（20分）：問題描述：給定一個二叉樹，判斷其是否為完全二叉樹。完全二叉樹定義：除最后一層外，每一層節(jié)點都盡可能滿，且最后一層節(jié)點從左到右連續(xù)排列。示例：1/\23/\\456輸出：`True`提示：-可以使用層序遍歷判斷。答案：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])end=False#標記是否遇到過不完整的節(jié)點whilequeue:node=queue.popleft()ifnode:ifend:如果前面遇到過不完整節(jié)點，當前節(jié)點不能為非空returnFalsequeue.append(node.left)queue.append(node.right)else:end=True#標記遇到過不完整節(jié)點returnTrue解析：1.層序遍歷：使用隊列逐層遍歷二叉樹。2.判斷邏輯：-遍歷過程中，一旦遇到空節(jié)點，后續(xù)所有節(jié)點必須為空。-使用`end`標記是否遇到過空節(jié)點，若遇到空節(jié)點后仍有非空節(jié)點，則不是完全二叉樹。時間復雜度：O(n)，n為節(jié)點數(shù)量。題目4（20分）：問題描述：設計一個算法，將一個無重復元素的數(shù)組`nums`隨機打亂，使得每個元素以等概率出現(xiàn)。示例：輸入：`nums=[1,2,3,4,5]`輸出：`[1,4,3,2,5]`（隨機打亂）提示：-不能使用額外空間。答案：pythonimportrandomdefshuffle(nums:list)->list:n=len(nums)foriinrange(n):生成[0,i]的隨機索引，交換當前元素與隨機元素rand_idx=random.randint(0,i)nums[i],nums[rand_idx]=nums[rand_idx],nums[i]returnnums解析：1.Fisher-Yates洗牌算法：-從后向前遍歷數(shù)組，每次選擇[0,i]的隨機索引，交換當前元素與隨機元素。-確保每個元素等概率被選中。時間復雜度：O(n)，空間復雜度：O(1)。題目5（20分）：問題描述：給定一個正整數(shù)`n`，生成所有可能的括號組合，其中左括號和右括號數(shù)量相同且有效。示例：輸入：`n=3`輸出：`["((()))","(()())","(())()","()(())","()()()"]`提示：-可以使用遞歸回溯解決。答案：pythondefgenerate_parentheses(n:int)->list:defbacktrack(s='',left=0,right=0):iflen(s)==2n:res.append(s)returnifleft<n:backtrack(s+'(',left+1,right)ifright<left:backtrack(s+')',left,right+1)res=[]backtrack()returnres解析：1.遞歸回溯：-每次選擇添加`'('`或`')'`：-添加`'('`，但左括號數(shù)量不超過`n`。-添加`')'`，但右括號數(shù)量不超過左括號。-當字符串長度達到`2n`時，記錄結果。時間復雜度：O(C(2n,n))，組合數(shù)復雜度。系統(tǒng)設計題（共2題，每題50分，總分100分）題目6（50分）：問題描述：設計一個支持以下操作的實時消息系統(tǒng)：1.`publish(user_id,message)`：用戶`user_id`發(fā)布一條消息。2.`subscribe(user_id,followee_id)`：用戶`user_id`訂閱`followee_id`。3.`get_messages(user_id)`：返回用戶`user_id`收到的所有消息（按時間順序）。要求：-支持高并發(fā)訂閱和發(fā)布。-消息存儲和分發(fā)需高效。示例：-`publish(1,"Hello")`-`subscribe(2,1)`-`publish(1,"World")`-`get_messages(2)`//輸出["Hello","World"]答案：pythonfromcollectionsimportdefaultdict,dequeimportthreadingclassMessageSystem:def__init__(self):self.publish_lock=threading.Lock()#防止并發(fā)沖突self.subscriptions=defaultdict(set)#user_id->followee_setself.user_messages=defaultdict(deque)#user_id->消息隊列defpublish(self,user_id:int,message:str):withself.publish_lock:廣播消息給所有訂閱者forfolloweeinself.subscriptions:self.user_messages[followee].append((user_id,message))defsubscribe(self,user_id:int,followee_id:int):self.subscriptions[user_id].add(followee_id)defget_messages(self,user_id:int)->list:returnlist(self.user_messages[user_id])解析：1.數(shù)據(jù)結構：-`subscriptions`：記錄每個用戶的訂閱關系。-`user_messages`：用隊列存儲每個用戶的消息，確保按時間順序返回。2.并發(fā)控制：-使用`publish_lock`保證發(fā)布操作時訂閱關系不被其他線程修改。3.消息分發(fā)：-發(fā)布時，將消息推送到所有訂閱者的消息隊列中。優(yōu)化建議：-使用發(fā)布-訂閱模式（如RabbitMQ）減輕服務壓力。-緩存熱點用戶消息，減少IO操作。題目7（50分）：問題描述：設計一個支持以下操作的社交網(wǎng)絡好友推薦系統(tǒng)：1.`add_friend(user_id,friend_id)`：用戶`user_id`添加`friend_id`為好友。2.`recommend(user_id,k)`：返回與`user_id`最相似的`k`個用戶（相似度基于共同好友數(shù)量）。要求：-相似度計算需高效。-支持動態(tài)更新好友關系。示例：-`add_friend(1,2)`-`add_friend(1,3)`-`add_friend(2,3)`-`recommend(1,2)`//輸出[2,3]（相似度：1和3各與1有2個共同好友）答案：pythonfromcollectionsimportdefaultdict,dequeimportheapqclassFriendRecommendationSystem:def__init__(self):self.friends=defaultdict(set)#user_id->friend_mon_friends=defaultdict(lambda:defaultdict(int))#user1->user2->共同好友數(shù)defadd_friend(self,user_id:int,friend_id:int):self.friends[user_id].add(friend_id)self.friends[friend_id].add(user_id)更新共同好友數(shù)量forfinself.friends[user_id]:i