2026年微软笔试模拟题及答案

2026年微软笔试模拟题及答案一、编程题（共3题，每题20分，总计60分）1.题目（20分）：编写一个函数，实现将给定字符串中的所有相邻重复字符合并为单个字符。例如，输入`"aaabbbcccaaa"`，输出`"abcaaa"`。要求时间复杂度为O(n)，空间复杂度为O(1)。示例代码（Python）：pythondefmerge_adjacent_duplicates(s:str)->str:你的代码pass2.题目（20分）：给定一个包含n个整数的数组，设计一个算法找出数组中的“旋转峰”（即左边严格递增，右边严格递减的元素）。假设数组中至少存在一个旋转峰。例如，输入`[1,2,3,5,4,0,1]`，输出`5`（或`4`，顺序不限）。要求时间复杂度为O(logn)。示例代码（Python）：pythondeffind_rotation_peak(nums:list)->int:你的代码pass3.题目（20分）：实现一个数据结构，支持以下操作：-`add(x)`：向集合中添加元素x。-`remove(x)`：从集合中删除元素x（如果不存在则忽略）。-`check(x)`：检查元素x是否存在于集合中，返回布尔值。要求所有操作的平均时间复杂度为O(1)。示例代码（Python）：pythonclassCustomSet:def__init__(self):你的代码passdefadd(self,x):你的代码passdefremove(self,x):你的代码passdefcheck(self,x):你的代码pass二、算法题（共3题，每题15分，总计45分）1.题目（15分）：假设你正在设计一个文件压缩算法，要求：-输入：一个字符串，包含字母和空格。-输出：使用行程长度编码（RLE）压缩后的字符串。例如，输入`"aabcccccaaa"`，输出`"a2b1c5a3"`。-要求：如果输入字符串为空或长度小于等于1，直接返回原字符串。2.题目（15分）：给定一个mxn的矩阵，每一步可以选择向右或向下移动。设计一个算法计算从左上角到右下角的最短路径（路径长度为移动步数之和）。例如，输入`[[1,3,1],[1,5,1],[4,2,1]]`，输出`7`（路径`1→3→1→1→1`）。3.题目（15分）：实现一个函数，统计一个字符串中所有唯一字符的数量。例如，输入`"leetcode"`，输出`8`（唯一字符为`l`,`e`,`t`,`c`,`o`,`d`）。要求不使用额外的数据结构（如哈希表）。三、系统设计题（共2题，每题25分，总计50分）1.题目（25分）：设计一个简单的URL缓存系统，要求：-支持缓存最多100个URL。-当新URL访问时，如果已缓存则返回缓存内容，否则从远程服务器获取并缓存（缓存满时需淘汰最早访问的URL）。-提供接口：`get(url)`和`set(url,content)`。-要求：说明数据结构选择及淘汰策略。2.题目（25分）：假设你要设计一个实时消息推送系统（如微信通知），要求：-支持最多1亿用户。-用户可以订阅多个主题（如股票、新闻），每个主题实时更新。-提供接口：`subscribe(user_id,topic)`、`publish(topic,message)`、`unsubscribe(user_id,topic)`。-要求：说明系统架构、数据存储方案及高并发处理策略。答案及解析一、编程题1.答案（Python）：pythondefmerge_adjacent_duplicates(s:str)->str:ifnots:return""result=[s[0]]forcharins[1:]:ifchar!=result[-1]:result.append(char)return''.join(result)解析：-使用双指针或列表模拟栈，遍历字符串时，当前字符与结果列表最后一个字符比较，若不同则添加到结果中。-时间复杂度O(n)，空间复杂度O(1)（忽略返回值占用的空间）。2.答案（Python）：pythondeffind_rotation_peak(nums:list)->int:left,right=0,len(nums)-1whileleft<right:mid=(left+right)//2ifnums[mid]>nums[mid+1]:right=midelse:left=mid+1returnnums[left]解析：-二分查找的变种，旋转峰一定是局部最大值。-每次比较mid与mid+1，若mid>mid+1则左边递增，峰在左边；否则在右边。3.答案（Python）：pythonclassCustomSet:def__init__(self):self.set=set()defadd(self,x):self.set.add(x)defremove(self,x):self.set.discard(x)defcheck(self,x):returnxinself.set解析：-使用Python内置set实现，add、remove、check均为O(1)平均时间复杂度。二、算法题1.答案：pythondefrle_encode(s:str)->str:ifnots:return""result=[]count=1foriinrange(1,len(s)):ifs[i]==s[i-1]:count+=1else:result.append(s[i-1]+str(count))count=1result.append(s[-1]+str(count))return''.join(result)解析：-遍历字符串，统计连续字符数量，遇到不同字符时记录字符和数量。-特殊情况：空字符串或单字符直接返回原字符串。2.答案：pythondefmin_path_sum(grid:list)->int:ifnotgridornotgrid[0]:return0m,n=len(grid),len(grid[0])dp=[[0]nfor_inrange(m)]dp[0][0]=grid[0][0]foriinrange(1,m):dp[i][0]=dp[i-1][0]+grid[i][0]forjinrange(1,n):dp[0][j]=dp[0][j-1]+grid[0][j]foriinrange(1,m):forjinrange(1,n):dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]returndp[-1][-1]解析：-动态规划，dp[i][j]表示到达(i,j)的最小路径和。-初始化第一行和第一列，然后填充dp表。3.答案：pythondefcount_unique_chars(s:str)->int:ifnots:return0count=[0]26#假设只含小写字母forcharins:count[ord(char)-ord('a')]+=1returnsum(1forcincountifc==1)解析：-使用固定长度的计数数组，统计每个字符的出现次数。-最后统计出现次数为1的字符数量。三、系统设计题1.答案：数据结构：使用`LRUCache`（最近最少使用淘汰策略）。实现：-使用`OrderedDict`（Python3.7+保持插入顺序）或自定义双向链表+哈希表。-`get`和`set`操作时更新访问顺序。2.答案：架构：-分布式消