微软技术面试要点及面试题

2026年微软技术面试要点及面试题1.编程基础（5题，每题10分，总分50分）题目1：编写一个函数，判断一个字符串是否是有效的括号组合（只考虑`()`、`[]`、`{}`）。答案：pythondefis_valid_brackets(s:str)->bool:stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：使用栈结构，遍历字符串，遇到右括号时检查栈顶元素是否匹配。若不匹配或栈为空，则返回`False`。最后栈为空则有效。题目2：实现一个无重复字符的最长子串函数。答案：pythondeflength_of_longest_substring(s:str)->int:char_map={}left=0max_len=0forright,charinenumerate(s):ifcharinchar_mapandchar_map[char]>=left:left=char_map[char]+1char_map[char]=rightmax_len=max(max_len,right-left+1)returnmax_len解析：使用滑动窗口技术，`left`和`right`分别表示窗口的左右边界。若遇到重复字符，移动`left`到重复字符的下一个位置。记录最大窗口长度。题目3：给定一个数组，返回所有和为target的三元组。答案：pythondefthree_sum(nums:list,target:int)->list:nums.sort()result=[]n=len(nums)foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:result.append([nums[i],nums[left],nums[right]])left+=1right-=1whileleft<rightandnums[left]==nums[left-1]:left+=1whileleft<rightandnums[right]==nums[right+1]:right-=1eliftotal<target:left+=1else:right-=1returnresult解析：先排序，然后固定一个数，用双指针找另外两个数。去重避免重复三元组。题目4：实现一个LRU（LeastRecentlyUsed）缓存。答案：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_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)解析：使用哈希表存储键值对，双向链表维护访问顺序。`get`时移动到链表尾部，`put`时先删除旧值，若容量满则删除最久未使用项。题目5：反转一个链表。答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：迭代法，逐个反转节点指针，`prev`和`current`逐步移动。2.算法与数据结构（5题，每题10分，总分50分）题目6：合并两个有序链表，返回合并后的有序链表。答案：pythondefmerge_two_lists(l1:ListNode,l2:ListNode)->ListNode:dummy=ListNode()current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1orl2returndummy.next解析：使用虚拟头节点，比较两个链表节点值，逐个合并。题目7：实现二叉树的层序遍历（BFS）。答案：pythonfromcollectionsimportdequedeflevel_order(root:TreeNode)->list:ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult解析：使用队列实现BFS，按层遍历节点，记录每层值。题目8：给定一个整数数组，判断是否存在三个元素a,b,c，使得a+b+c=0。找出所有不重复的三元组。答案：pythondefthree_sum(nums:list)->list:nums.sort()result=[]n=len(nums)foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:result.append([nums[i],nums[left],nums[right]])left+=1right-=1whileleft<rightandnums[left]==nums[left-1]:left+=1whileleft<rightandnums[right]==nums[right+1]:right-=1eliftotal<0:left+=1else:right-=1returnresult解析：排序后固定一个数，用双指针找另外两个数。去重避免重复三元组。题目9：实现快速排序算法。答案：pythondefquick_sort(arr:list)->list:iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：选择基准值，将数组分为小于、等于、大于三部分，递归排序左右子数组。题目10：给定一个字符串，找到最长的回文子串。答案：pythondeflongest_palindrome(s:str)->str:ifnots:return""start,end=0,0foriinrange(len(s)):len1=expand_from_center(s,i,i)len2=expand_from_center(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]defexpand_from_center(s:str,left:int,right:int)->int:whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：遍历每个字符，向两边扩展找最长回文子串。奇偶长度均考虑。3.系统设计（3题，每题20分，总分60分）题目11：设计一个URL短链接系统（如tinyURL）。答案：1.数据结构：-哈希表：`long_to_short`（长URL到短URL）和`short_to_long`（短URL到长URL）。-短URL生成：使用随机6位字符（如`a-z`、`0-9`）。2.流程：-用户请求短链接时，生成随机短码，存入哈希表，返回短URL。-用户访问短URL时，查哈希表，返回长URL。3.高可用性：-分布式存储（如Redis），负载均衡。-缓存热点短链接。解析：核心是哈希映射，确保长URL唯一映射到短URL，且反向查找快速。题目12：设计一个简单的微博系统（支持发帖、关注、取关、点赞）。答案：1.数据结构：-用户：`user_id`、`followings`（关注列表）、`followers`（粉丝列表）、`tweets`（发布帖子）。-帖子：`tweet_id`、`user_id`、`content`、`likes`（点赞数）。2.功能实现：-发帖：用户添加帖子到自己的`tweets`，存入数据库。-关注/取关：更新`followings`和`followers`。-点赞：更新帖子的`likes`。3.性能优化：-关注列表使用倒排索引加速查询。-实时更新使用消息队列（如Kafka）。解析