2026年微软工程师面试攻略与经典题目

2026年微软工程师面试攻略与经典题目一、编程基础（共5题，每题10分，总分50分）1.题目：给定一个整数数组，返回数组中所有唯一元素的对的数量。例如，输入`[1,2,3,4,5]`，输出应为`10`（所有两两组合）。要求：时间复杂度O(n)。2.题目：实现一个函数，检查一个字符串是否为有效的括号组合。例如，输入`"(())"`应返回`true`，输入`"(()"`应返回`false`。3.题目：给定一个链表，反转链表并返回反转后的头节点。例如，输入`1->2->3->4`，输出应为`4->3->2->1`。4.题目：实现一个二叉树的前序遍历（根节点->左子树->右子树），要求使用递归和迭代两种方法。5.题目：给定一个字符串，统计其中每个字符的出现次数，并按字符顺序返回一个数组。例如，输入`"hello"`，输出应为`[1,1,2,1,1]`（对应h,e,l,l,o）。二、算法设计（共3题，每题15分，总分45分）1.题目：设计一个LRU（最近最少使用）缓存系统，支持`get`和`put`操作。`get`返回键对应的值，若不存在返回`-1`；`put`插入或更新键值对，如果缓存已满，则删除最近最少使用的项。假设缓存容量为`3`。要求：使用哈希表和双向链表实现，时间复杂度O(1)。2.题目：给定一个无序数组，找到数组中第k大的元素。例如，输入`[3,2,1,5,6,4]`，k=`2`，输出应为`5`。要求：时间复杂度O(n)。3.题目：实现一个函数，判断一个数是否为完全平方数。例如，输入`16`，输出`true`；输入`14`，输出`false`。要求：不使用内置函数，时间复杂度O(logn)。三、系统设计（共2题，每题25分，总分50分）1.题目：设计一个简单的微博系统，支持以下功能：-用户注册和登录。-发布微博（限制长度为280字符）。-关注/取消关注用户。-浏览关注用户的最新微博（按时间倒序）。要求：说明核心数据结构和主要接口设计。2.题目：设计一个分布式任务队列系统，支持以下功能：-添加任务到队列。-消费者从队列中获取任务并执行。-任务失败后可重新入队。-支持任务优先级。要求：说明系统架构、数据存储方式（如Redis）和核心流程。答案与解析一、编程基础1.答案：pythondefcount_unique_pairs(arr):count=0n=len(arr)foriinrange(n):forjinrange(i+1,n):ifarr[i]!=arr[j]:count+=1returncount解析：双重循环遍历所有可能的对，统计唯一对的数量。时间复杂度O(n²)，但题目要求O(n)可优化为哈希表统计频率。2.答案：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：使用栈匹配括号，遇到右括号时检查栈顶是否匹配。3.答案：pythondefreverseList(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：迭代反转链表节点指针。4.答案：-递归：pythondefpreorder_recursive(root):ifnotroot:return[]return[root.val]+preorder_recursive(root.left)+preorder_recursive(root.right)-迭代：pythondefpreorder_iterative(root):ifnotroot:return[]stack,output=[root],[]whilestack:node=stack.pop()output.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnoutput解析：递归直接按根左右顺序；迭代使用栈模拟递归过程。5.答案：pythondefcount_chars(s):return[s.count(c)forcinsorted(set(s))]解析：先排序去重，再统计每个字符频率。二、算法设计1.答案：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key):ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key,value):ifkeyinself.cache:self._remove(self.cache[key])node=self.Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodenode.prev=self.headself.head.next=node解析：双向链表+哈希表，链表头部为最近使用，尾部为最久未使用。2.答案：pythondeffindKthLargest(nums,k):defpartition(left,right,pivot_index):pivot=nums[pivot_index]nums[pivot_index],nums[right]=nums[right],nums[pivot_index]store_index=leftforiinrange(left,right):ifnums[i]>pivot:nums[store_index],nums[i]=nums[i],nums[store_index]store_index+=1nums[right],nums[store_index]=nums[store_index],nums[right]returnstore_indexdefselect(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=random.randint(left,right)pivot_index=partition(left,right,pivot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnselect(left,pivot_index-1,k_smallest)else:returnselect(pivot_index+1,right,k_smallest)returnselect(0,len(nums)-1,len(nums)-k)解析：快速选择算法，时间复杂度平均O(n)。3.答案：pythondefisPerfectSquare(num):left,right=1,numwhileleft<=right:mid=left+(right-left)//2ifmidmid==num:returnTrueelifmidmid<num:left=mid+1else:right=mid-1returnFalse解析：二分查找平方根，时间复杂度O(logn)。三、系统设计1.答案：-数据结构：-用户表：`id`,`username`,`password`,`follows`（用户关注列表）。-微博表：`id`,`user_id`,`content`,`timestamp`。-接口：-注册：`POST/register`（`username`,`password`）。-登录：`POST/login`（`username`,`password`）。-发布：`POST/tweet`（`content`）。-关注：`POST/follow`（`followee_id`）。-浏览：`GET/timeline`（返回关注用户微博）。解析：关系型数据库存储用户和微博，关注关系维护在用户表中。2.答案：