微软技术部门面试题集及解答

2026年微软技术部门面试题集及解答一、编程算法题（共5题，每题15分）1.题目：给定一个包含重复元素的数组，返回所有不重复的全排列。例如，输入`[1,1,2]`，输出`[[1,1,2],[1,2,1],[2,1,1]]`。要求：时间复杂度优于O(n!)。答案：pythondefpermute_unique(nums):defbacktrack(path,used,res):iflen(path)==len(nums):res.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack(path,used,res)path.pop()used[i]=Falsenums.sort()res=[]used=[False]len(nums)backtrack([],used,res)returnres示例print(permute_unique([1,1,2]))解析：-先对数组排序，便于跳过重复元素。-使用`used`数组记录每个元素是否被使用，避免重复。-当遇到与前一个元素相同且前一个元素未被使用时，跳过以避免重复排列。-时间复杂度：O(n!n)，空间复杂度：O(n!n)。2.题目：实现一个LRU（最近最少使用）缓存，支持`get`和`put`操作。要求：`get`操作返回键对应的值，若不存在返回`-1`；`put`操作将键值对插入缓存，如果缓存已满则删除最久未使用的元素。答案：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)示例cache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#返回1cache.put(3,3)#去除键2print(cache.get(2))#返回-1解析：-使用字典`cache`存储键值对，列表`order`记录访问顺序。-`get`操作时，将访问的键移动到列表末尾。-`put`操作时，若键已存在则更新值并移动位置；若缓存已满，则删除列表第一个元素（最久未使用）。-时间复杂度：O(1)。3.题目：给定一个二叉树，返回其“锯齿形”层序遍历（即第一层从左到右，第二层从右到左，以此类推）。答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefzigzagLevelOrder(root:TreeNode)->List[List[int]]:ifnotroot:return[]res=[]queue=deque([root])left_to_right=Truewhilequeue:level=[]for_inrange(len(queue)):node=queue.popleft()ifleft_to_right:level.append(node.val)else:level.insert(0,node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)left_to_right=notleft_to_rightreturnres示例构建二叉树：3/\920/\157root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)print(zigzagLevelOrder(root))解析：-使用双端队列`queue`实现层序遍历。-使用布尔值`left_to_right`控制方向：True为从左到右，False为从右到左。-每层遍历后反转方向。-时间复杂度：O(n)，空间复杂度：O(n)。4.题目：给定一个非负整数数组，返回一个数组`answer`，其中`answer[i]`是数组中比`nums[i]`小的数字的个数。答案：pythondefsmallerNumbersThanCurrent(nums:List[int])->List[int]:sorted_nums=sorted(nums)rank={num:ifori,numinenumerate(sorted_nums)}return[rank[num]fornuminnums]示例print(smallerNumbersThanCurrent([8,1,2,2,3]))解析：-先对数组排序，记录每个数字的排名。-然后根据原数组数字的排名生成结果。-时间复杂度：O(nlogn)，空间复杂度：O(n)。5.题目：实现一个函数，判断一个字符串是否是有效的括号组合（只包含`()`,`[]`,`{}`）。答案：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack示例print(isValid("{[]}()"))#Trueprint(isValid("([)]"))#False解析：-使用栈存储左括号，遇到右括号时检查栈顶是否匹配。-若栈为空或栈顶不匹配，则无效。-时间复杂度：O(n)，空间复杂度：O(n)。二、系统设计题（共3题，每题20分）1.题目：设计一个短链接服务（如TinyURL），要求：-输入任意长链接，返回短链接。-支持通过短链接查询原始长链接。-高并发场景下仍能快速响应。答案：-数据结构：-使用哈希表存储短链接与长链接的映射。-使用自增ID或随机生成短码（如`a-z0-9`），确保唯一性。-高并发优化：-使用Redis高性能缓存存储映射关系。-使用分布式锁处理写入冲突。-分布式部署：-部署多个服务节点，使用负载均衡分配请求。-数据库使用分片或一致性哈希避免单点瓶颈。2.题目：设计一个实时微博发布系统，要求：-用户可以发布、关注、点赞微博。-实时显示用户关注者的最新动态（类似Twitter流）。-支持百万级用户和每秒千条动态。答案：-架构：-前端：WebSocket实现实时推流。-后端：微服务架构（发布、关注、点赞、流服务分离）。-数据库：-发布数据使用NoSQL（如MongoDB）存储，快速写入。-关注关系使用Redis存储用户关注列表。-实时流处理：-使用Kafka或Pulsar存储动态，流服务订阅并分发到关注者。-消息队列解耦写入和读取，避免性能瓶颈。3.题目：设计一个分布式URL缓存系统，要求：-用户访问URL时，先查询缓存，未命中再请求原始服务器。-缓存热点数据，减少重复请求。-支持缓存过期和淘汰策略。答案：-架构：-使用CDN边缘节点缓存静态资源。-后端使用分布式缓存（如RedisCluster）。-缓存策略：-使用LRU或LFU淘汰策略。-使用TTL机制自动过期。-负载均衡：-使用DNS或负载均衡器调度请求。-避免缓存雪崩（预热热点数据）。三、数据库与SQL题（共2题，每题15分）1.题目：给定表`Orders`（订单表）和`Customers`（客户表），编写SQL查询：-返回每个客户的订单总数，以及订单总金额。-客户名为"Alice"的数据单独列出。答案：sqlSELECTc.Name,COUNT(o.OrderID)ASTotalOrders,SUM(o.Amount)ASTotalAmountFROMOrdersoJOINCustomerscONo.CustomerID=c.CustomerIDGROUPBYc.NameUNIONALLSELECT'Alice'ASName,(SELECTCOUNT()FROMOrdersWHERECustomerID=(SELECTCustomerIDFROMCustomersWHEREName='Alice')),(SELECTSUM(Amount)FROMOrdersWHERECustomerID=(SELECTCustomerIDFROMCustomersWHEREName='Alice'))解析：-使用`JOIN`连接表并按客户分组统计。-使用`UNIONALL`单独查询Alice的数据。2.题目：表`Products`（产品表）有字段`Category`,`Price`，编写SQL：-返回每个分类的平均价格，且只保留价格中位数最高的分类。答案：sqlWITHRankedCategoriesAS(SELECTCategory,AVG(Price)ASAvgPrice,ROW_NUMBER()OVER(ORDERBYAVG(Price)DESC)ASRankFROMProductsGROUPBYCategory)SELECTCategory,AvgPriceFROMRankedCategoriesWHERERank=1解析：-使用窗口函数`ROW_NUMBER()`排序分类。-只返回排名第一的分类。四、网络与系统题（共2题，每题15分）1.题目：解释TCP的三次握手和四次挥手过程，并说明为什么不能省略任何一步。答案：-三次握手：1.客户端发送SYN包，进入`SYN_SENT`状态。2.服务器回复SYN-ACK包，进入`SYN_RCVD`状态。3.客户端发送ACK包，进入`ESTABLISHED`状态。-目的：双方确认双方都有发送和接收能力。-四次挥手：1.客户端发送FIN包，进入`FIN_WAIT_1`。2.服务器回复ACK包，进入`CLOSE_WAIT`。3.服务器发送FIN包，进入`LAST_ACK`。4.客户端回复ACK包，进入`TIME_WAIT`，等待2MSL后关闭。-目的：确保双方数据传输完成且没有遗漏。2.题目：如何优化网站首页加载速度？列举至少三种方法。答案：1.CDN加速：将静态资源（图片、JS、CSS）部署到CDN，减少服务器负载和延迟。2.图片优化：压缩图片（如WebP格式）、懒加载、使用CDN分片。3.代码优化：代码压缩、合并文件、使用HTTP/2多路复用。五、编程语言与并发题（共2题，每题15分）1.题目：解释Python中的GIL是什么，以及如何实现多线程并发计算？答案：-GIL（全局