2026年微软面试题及答案详解

2026年微软面试题及答案详解编程题（共5题，每题20分，总分100分）题目1（20分）：问题描述：给定一个字符串`s`和一个正整数`k`，请编写一个函数，返回所有长度为`k`的子串中，出现频率最高的子串。如果有多个子串频率相同，返回所有这些子串。示例：输入：`s="aabbcc",k=2`输出：`["aa","bb"]`提示：-字符串仅包含小写字母。-`1<=k<=s.length()`。答案：pythondefhighest_frequency_substrings(s:str,k:int)->list:fromcollectionsimportdefaultdict1.统计所有长度为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.统计子串频率：使用滑动窗口遍历所有长度为`k`的子串，并记录每个子串的出现次数。2.确定最大频率：遍历频率字典，找到最高频率值。3.收集结果：筛选出所有频率等于最大频率的子串，返回列表。时间复杂度：O(n·k)，其中n为字符串长度。题目2（20分）：问题描述：设计一个LRU（LeastRecentlyUsed）缓存数据结构，支持以下操作：-`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):添加节点到链表头部node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node:Node):删除链表中的节点prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node:Node):将节点移动到链表头部self._remove_node(node)self._add_node(node)def_pop_tail(self)->Node:弹出链表尾部节点res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1移动节点到头部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)时间查找节点。3.操作逻辑：-`get`：查找节点，移动到头部，返回值。-`put`：插入新节点到头部，如果超出容量，删除尾部节点。时间复杂度：O(1)。题目3（20分）：问题描述：给定一个二叉树，判断其是否为完全二叉树。完全二叉树定义：除最后一层外，每一层节点都尽可能满，且最后一层节点从左到右连续排列。示例：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#标记是否遇到过不完整的节点whilequeue:node=queue.popleft()ifnode:ifend:如果前面遇到过不完整节点，当前节点不能为非空returnFalsequeue.append(node.left)queue.append(node.right)else:end=True#标记遇到过不完整节点returnTrue解析：1.层序遍历：使用队列逐层遍历二叉树。2.判断逻辑：-遍历过程中，一旦遇到空节点，后续所有节点必须为空。-使用`end`标记是否遇到过空节点，若遇到空节点后仍有非空节点，则不是完全二叉树。时间复杂度：O(n)，n为节点数量。题目4（20分）：问题描述：设计一个算法，将一个无重复元素的数组`nums`随机打乱，使得每个元素以等概率出现。示例：输入：`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洗牌算法：-从后向前遍历数组，每次选择[0,i]的随机索引，交换当前元素与随机元素。-确保每个元素等概率被选中。时间复杂度：O(n)，空间复杂度：O(1)。题目5（20分）：问题描述：给定一个正整数`n`，生成所有可能的括号组合，其中左括号和右括号数量相同且有效。示例：输入：`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.递归回溯：-每次选择添加`'('`或`')'`：-添加`'('`，但左括号数量不超过`n`。-添加`')'`，但右括号数量不超过左括号。-当字符串长度达到`2n`时，记录结果。时间复杂度：O(C(2n,n))，组合数复杂度。系统设计题（共2题，每题50分，总分100分）题目6（50分）：问题描述：设计一个支持以下操作的实时消息系统：1.`publish(user_id,message)`：用户`user_id`发布一条消息。2.`subscribe(user_id,followee_id)`：用户`user_id`订阅`followee_id`。3.`get_messages(user_id)`：返回用户`user_id`收到的所有消息（按时间顺序）。要求：-支持高并发订阅和发布。-消息存储和分发需高效。示例：-`publish(1,"Hello")`-`subscribe(2,1)`-`publish(1,"World")`-`get_messages(2)`//输出["Hello","World"]答案：pythonfromcollectionsimportdefaultdict,dequeimportthreadingclassMessageSystem:def__init__(self):self.publish_lock=threading.Lock()#防止并发冲突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.数据结构：-`subscriptions`：记录每个用户的订阅关系。-`user_messages`：用队列存储每个用户的消息，确保按时间顺序返回。2.并发控制：-使用`publish_lock`保证发布操作时订阅关系不被其他线程修改。3.消息分发：-发布时，将消息推送到所有订阅者的消息队列中。优化建议：-使用发布-订阅模式（如RabbitMQ）减轻服务压力。-缓存热点用户消息，减少IO操作。题目7（50分）：问题描述：设计一个支持以下操作的社交网络好友推荐系统：1.`add_friend(user_id,friend_id)`：用户`user_id`添加`friend_id`为好友。2.`recommend(user_id,k)`：返回与`user_id`最相似的`k`个用户（相似度基于共同好友数量）。要求：-相似度计算需高效。-支持动态更新好友关系。示例：-`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->共同好友数defadd_friend(self,user_id:int,friend_id:int):self.friends[user_id].add(friend_id)self.friends[friend_id].add(user_id)更新共同好友数量forfinself.friends[user_id]:i