2026年微软笔试题库及解析

2026年微软笔试题库及解析一、编程题（共5题，每题10分）1.题目：编写一个函数，输入一个字符串，返回该字符串中所有唯一字符的列表。例如，输入"abaccde"，返回['b','d','e']。答案：pythondefunique_chars(s):count={}result=[]forcharins:count[char]=count.get(char,0)+1forcharins:ifcount[char]==1:result.append(char)returnresult示例print(unique_chars("abaccde"))#输出:['b','d','e']解析：-使用字典统计每个字符的出现次数，遍历字符串时记录出现次数为1的字符。-时间复杂度O(n)，空间复杂度O(1)（假设字符集固定）。2.题目：给定一个链表，删除其中的重复元素，使得每个元素只出现一次。返回删除后的链表。答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefdelete_duplicates(head):current=headwhilecurrentandcurrent.next:ifcurrent.val==current.next.val:current.next=current.next.nextelse:current=current.nextreturnhead示例defprint_list(head):whilehead:print(head.val,end='')head=head.nextprint_list(delete_duplicates(ListNode(1,ListNode(1,ListNode(2,ListNode(3,ListNode(3))))))输出:123解析：-使用双指针遍历链表，当前节点与下一个节点值相同则删除下一个节点。-时间复杂度O(n)，空间复杂度O(1)。3.题目：实现一个二叉树的前序遍历（根-左-右），要求使用递归和迭代两种方法。答案：递归方法：pythondefpreorder_recursive(root):ifnotroot:return[]return[root.val]+preorder_recursive(root.left)+preorder_recursive(root.right)示例classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightprint(preorder_recursive(TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3)))输出:[1,2,4,5,3]迭代方法：pythondefpreorder_iterative(root):ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresultprint(preorder_iterative(TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5)),TreeNode(3)))输出:[1,2,4,5,3]解析：-递归方法直接调用自身，迭代方法使用栈模拟递归过程。-两种方法时间复杂度O(n)，空间复杂度O(h)（h为树的高度）。4.题目：设计一个LRU（最近最少使用）缓存，支持get和put操作。答案：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.order=[]defget(self,key):ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key,value):ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:self.cache.pop(self.order.pop(0))self.cache[key]=valueself.order.append(key)示例lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#返回1lru.put(3,3)#去除键2print(lru.get(2))#返回-1解析：-使用哈希表存储键值对，双向链表维护访问顺序。-get时移动元素到链表末尾，put时按需删除最久未使用元素。-时间复杂度O(1)，空间复杂度O(capacity)。5.题目：给定一个包含n个整数的数组，返回所有和为target的三元组数量。答案：pythondefthree_sum(nums,target):nums.sort()n=len(nums)count=0foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:s=nums[i]+nums[left]+nums[right]ifs==target:count+=1left+=1right-=1whileleft<rightandnums[left]==nums[left-1]:left+=1whileleft<rightandnums[right]==nums[right+1]:right-=1elifs<target:left+=1else:right-=1returncount示例print(three_sum([-1,0,1,2,-1,-4],0))#输出:2解析：-排序后使用双指针，固定一个数，另两个数用双指针遍历。-时间复杂度O(n²)，空间复杂度O(1)。二、算法题（共5题，每题10分）1.题目：给定一个数组，返回其中缺失的最小正整数。例如，输入[3,4,-1,1,2]，返回1。答案：pythondefmissing_number(nums):n=len(nums)nums=sorted(set(nums))foriinrange(len(nums)):ifnums[i]!=i+1:returni+1returnn+1示例print(missing_number([3,4,-1,1,2]))#输出:1解析：-排序后检查每个位置是否等于索引+1，第一个不匹配的即为答案。-时间复杂度O(nlogn)，空间复杂度O(1)。2.题目：实现一个有效的括号匹配，例如输入"()[]{}",返回True；输入"(]",返回False。答案：pythondefvalid_parentheses(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack示例print(valid_parentheses("()[]{}"))#Trueprint(valid_parentheses("(]"))#False解析：-使用栈匹配括号，遍历字符串时将左括号入栈，右括号与栈顶比较。-时间复杂度O(n)，空间复杂度O(n)。3.题目：给定一个无重复字符的数组，返回其所有子集。答案：pythondefsubsets(nums):result=[]subset=[]defbacktrack(start):result.append(subset.copy())foriinrange(start,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult示例print(subsets([1,2,3]))输出:[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]解析：-回溯算法枚举所有可能的子集，每次选择或不选择当前元素。-时间复杂度O(2^n)，空间复杂度O(n)。4.题目：设计一个LRU缓存，支持get和put操作，但使用数组实现（不考虑空间换时间）。答案：pythonclassLRUCacheArray:def__init__(self,capacity):self.capacity=capacityself.cache={}self.order=[]defget(self,key):ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key,value):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)示例lru=LRUCacheArray(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#返回1lru.put(3,3)#去除键2print(lru.get(2))#返回-1解析：-使用哈希表记录键值对，数组维护顺序。-get时移动元素到数组末尾，put时按需删除最久未使用元素。-时间复杂度O(n)，空间复杂度O(capacity)。5.题目：给定一个字符串，判断是否可以通过删除一些字符使其变为回文串。例如，输入"cabababcbc"，返回True。答案：pythondefvalid_palindrome(s):left,right=0,len(s)-1whileleft<right:ifs[left]!=s[right]:skip_left=s[left+1:right+1]skip_right=s[left:right]ifskip_left==skip_left[::-1]orskip_right==skip_right[::-1]:returnTrueelse:returnFalseleft+=1right-=1returnTrue示例print(valid_palindrome("cabababcbc"))#True解析：-双指针从两端向中间遍历，遇到不匹配时尝试跳过左右字符之一，检查剩余部分是否为回文。-时间复杂度O(n²)，空间复杂度O(1)。三、系统设计题（共2题，每题15分）1.题目：设计一个高并发的短链接系统，要求支持秒级生成和查询。答案：-核心组件：1.短链接生成服务：-使用哈希函数（如CRC32或自定义算法）将长链接映射为短链接（如6位随机字符）。-缓存常用映射关系，减少数据库查询。2.数据库：-存储长链接与短链接的映射关系，索引短链接以加速查询。3.负载均衡：-使用DNS轮询或负载均衡器分配请求到多个生成服务实例。4.缓存层：-Redis缓存热点短链接的映射关系，降低数据库压力。解析：-关键在于高并发下的快速映射和查询，通过缓存和负载均衡提升性能。2.题目：设计一个实时消息推送系统，支持单聊和群聊，要求低延迟和高可用。答案：-核心组件：1.消息存储：-使用分布式数据库（如Cassandra）存储消息历史，支持高并发写入。2.消息队列：-Kafka或RabbitMQ处理消息分发，确保不丢消息。3.推送服务：-根据用户设备信息（WebSocket或长轮询）实时推送消息。4.用