微软技术面试题目及答案参考

2026年微软技术面试题目及答案参考编程题（5题，每题15分，共75分）1.题目（15分）：编写一个函数，输入一个正整数`n`，返回`n`的“数字翻转”结果。例如，输入`123`返回`321`，输入`120`返回`21`（注意：翻转后前导零应被忽略）。要求不使用内置的字符串反转函数，仅用整数操作实现。答案与解析：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解析：-整数反转时需处理符号位，先取绝对值处理，最后再还原符号。-逐位取余数（`n%10`）得到当前最低位，然后除以10（`n//10`）去掉该位。-翻转时需检查是否溢出，即`result10+pop`是否超过`INT_MAX`或`INT_MIN`。-时间复杂度O(logn)，空间复杂度O(1)。2.题目（15分）：给定一个无重复元素的数组`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`查找剩余的两个数。-避免重复解：跳过与前一个相同的元素。-时间复杂度O(n³)，空间复杂度O(1)。3.题目（15分）：实现一个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分）：给定一个二叉树，判断其是否为平衡二叉树。平衡二叉树定义：对于任意节点，其左右子树高度差不超过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]解析：-递归检查每个节点的高度，同时判断左右子树是否平衡。-返回值：当前节点的高度，以及当前子树是否平衡。-若任意节点不平衡（高度差>1），则整棵树不平衡。-时间复杂度O(n)，空间复杂度O(h)（h为树高）。5.题目（15分）：实现一个“合并区间”函数，输入一个区间列表（每个区间为`[start,end]`），合并所有重叠的区间，并返回合并后的区间列表。例如：输入`[[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解析：-先按区间起始位置排序。-遍历区间，若当前区间与前一个区间重叠（`current[0]<=last[1]`），则合并（更新`last[1]`）。-若不重叠，则直接添加到结果中。-时间复杂度O(nlogn)，空间复杂度O(n)。系统设计题（2题，每题25分，共50分）1.题目（25分）：设计一个简单的微博“实时推文”系统。要求：-用户发布推文时，其他用户能近乎实时看到该推文（延迟不超过1秒）。-系统需支持至少10,000个并发用户，推文数每日增长约1亿条。-提供两种查看方式：按用户查看（关注列表）、按时间查看（最新推文）。答案与解析：系统架构：1.数据存储：-推文存储：使用分布式数据库（如Cassandra或RocksDB）存储推文，按用户ID或时间索引，支持快速写入和读取。-用户关注关系：使用Redis哈希表存储用户关注关系（`user:follows:{userId}`），支持快速查询。2.实时推文分发：-发布流程：-用户发布推文时，写入数据库并广播给该用户的所有关注者（使用RedisPub/Sub或Kafka）。-优化：-使用“流式拉取”而非“全量推送”，每个用户维护一个轻量级订阅队列，仅接收增量更新。-异步写入磁盘，保证写入性能。-订阅优化：-使用“布隆过滤器”预判用户是否关注某账号，减少无效推送。-按用户分组推送，避免单节点压力过大。3.读取服务：-按用户查看：直接查询数据库，支持缓存热点用户推文（如Redis）。-按时间查看：使用LevelDB或时间序列数据库（如InfluxDB）按时间索引推文，支持分页查询。4.高可用与扩展：-推文服务分片（Sharding），按用户ID哈希分配到不同节点。-使用负载均衡器（如Nginx）分发请求。-监控系统（如Prometheus+Grafana）实时监控延迟、QPS等指标。技术选型理由：-Redis：高性能键值存储，适合存储关注关系和流式队列。-分布式数据库：支持海量写入和水平扩展。-流式架构：保证低延迟，避免阻塞主线程。2.题目（25分）：设计一个支持高并发的“短链接生成与解析”系统。要求：-输入任意长链接，生成6位短链接（如`/a1b2c`）。-短链接解析时，能快速定位原始长链接（延迟<100ms）。-系统需支持日均1000万次访问，且短链接唯一性要求极高。答案与解析：系统架构：1.短链接生成：-编码算法：-使用62进制（`a-z`、`A-Z`、`0-9`）对ID进行编码，6位可表示62⁶=56.8亿个ID。-映射关系：`{0:a,1:b,...,61:zA0}`。-ID生成：-使用分布式唯一ID生成器（如TwitterSnowflake算法），确保全局唯一。-写入Redis或分布式数据库，支持快速查询。2.短链接解析：-用户访问短链接时，DNS解析至负载均衡器（如HAProxy）。-负载均衡器将请求转发至服务集群。-服务端通过短链接的6位ID快速查询单个长链接（Redis缓存热点ID）。-若未命中缓存，则查询数据库，并缓存结