2026年微软件工程师笔试题目解析

2026年微软件工程师笔试题目解析一、编程基础（共5题，每题4分，合计20分）考察内容：数据结构、算法、编程语言基础（C++/Java/Python）题目1（4分）：编写一个函数，实现将32位无符号整数反转。例如，输入`123456789`，输出`987654321`。假设环境不允许存储64位整数。答案：pythondefreverse_int(x:int)->int:INT_MAX=231-1INT_MIN=-231result=0whilex!=0:pop=x%10x//=10ifresult>INT_MAX//10or(result==INT_MAX//10andpop>7):return0ifresult<INT_MIN//10or(result==INT_MIN//10andpop<-8):return0result=result10+popreturnresult解析：-防止溢出：32位整数范围为`-2^31~2^31-1`，反转过程中需判断是否越界。-取余和除法：通过`x%10`获取最后一位，`x//=10`移除最后一位。-乘10加余数：逐步构建反转后的数字，注意前导零不影响结果。题目2（4分）：给定一个字符串`s`，判断其是否为有效的括号字符串（只包含`'('`和`')'`，且括号匹配）。答案：pythondefis_valid(s:str)->bool:stack=[]forcharins:ifchar=='(':stack.append(char)elifchar==')':ifnotstack:returnFalsestack.pop()returnnotstack解析：-栈的应用：左括号入栈，右括号时弹出对应左括号。-最终栈为空则匹配，否则不匹配。-时间复杂度O(n)，空间复杂度O(n)。题目3（4分）：实现一个`LRU缓存`（LeastRecentlyUsed）。支持`get`和`put`操作，容量为`capacity`。答案：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)解析：-哈希表+双向链表：哈希表存储`key-value`，双向链表维护访问顺序。-`get`操作：命中则移动到链表尾部，未命中返回-1。-`put`操作：已存在则更新并移动到尾部；若超出容量，删除链表头部（最久未使用）。题目4（4分）：给定一个数组`nums`，返回所有和为`target`的`nums[i]+nums[j]`组合（不重复）。答案：pythondeftwo_sum(nums:List[int],target:int)->List[List[int]]:seen={}res=[]fori,numinenumerate(nums):complement=target-numifcomplementinseen:res.append([complement,num])seen[num]=ireturnres解析：-哈希表记录已遍历数字，避免重复计算。-时间复杂度O(n)，空间复杂度O(n)。-题目要求不重复组合，因此遍历时仅添加`[complement,num]`（确保`complement`在前）。题目5（4分）：实现快速排序算法，要求使用递归方式。答案：pythondefquick_sort(arr:List[int])->List[int]:iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：-选择中位数作为基准（pivot），将数组分为`<pivot`、`==pivot`、`>pivot`三部分。-递归排序左右子数组，合并后返回。-平均时间复杂度O(nlogn)，最坏O(n^2)（基准选择不当）。二、系统设计（共3题，每题10分，合计30分）考察内容：分布式系统、数据库、缓存、负载均衡题目6（10分）：设计一个高并发的短链接系统。要求：1.输入长链接，输出短链接（如`/abc123`）。2.支持快速跳转（短链接解析为长链接）。3.高可用、分布式支持。答案：1.短链接生成：-使用`base62`编码（`a-z`、`A-Z`、`0-9`），将长链接哈希后映射为6位短码。-哈希算法：先用MD5/SHA256，再取前6位或映射到62进制。2.分布式存储：-使用Redis/ZooKeeper存储`short_code->long_url`映射，支持高并发读写。-每个节点独立处理请求，负载均衡器分发流量。3.解析跳转：-接收短链接，解析`short_code`，查询Redis返回长链接，重定向301。4.高可用：-Redis集群化部署，使用主从复制或哨兵机制。-短链接使用分布式ID生成器（如TwitterSnowflake）。解析：-base62编码：减少短链接长度，提高可读性。-Redis：高性能键值存储，适合高并发场景。-负载均衡：Nginx/HAProxy分发请求，避免单点瓶颈。题目7（10分）：设计一个高并发的新闻推荐系统。要求：1.用户实时点击新闻后更新推荐。2.支持个性化推荐（基于用户历史行为）。3.分布式架构，支持水平扩展。答案：1.数据存储：-用户行为：Redis存`user_id->click_history`（LIFO队列）。-新闻数据：Elasticsearch索引新闻内容，支持分词搜索。2.推荐算法：-协同过滤：基于用户相似度（如Jaccard相似度）。-内容推荐：新闻TF-IDF向量化，用户历史向量匹配。3.实时更新：-使用Kafka消息队列收集用户点击事件，流处理引擎（Flink/SparkStreaming）实时更新推荐结果。4.分布式架构：-推荐服务分片（按用户ID哈希），负载均衡器分发请求。-数据库使用分库分表（如MySQLCluster）。解析：-Redis：高性能存取用户行为。-Elasticsearch：全文检索加速新闻匹配。-流处理：实时更新推荐逻辑，避免冷启动延迟。题目8（10分）：设计一个分布式计数器系统，要求：1.支持高并发自增。2.分布式部署，不依赖中心节点。3.异常恢复机制。答案：1.基于Redis：-使用Redis`INCR`命令（原子操作），但单点依赖Redis。2.基于Raft/Paxos：-分布式共识算法保证计数器一致性，但实现复杂。3.基于本地存储+最终一致性：-每个节点本地计数（如文件/本地变量），定时异步同步到中心存储（如HBase/Cassandra）。-使用SnowflakeID生成唯一计数（结合时间戳和机器ID）。解析：-Redis：简单但依赖中心节点。-Raft：强一致性但工程成本高。-最终一致性：牺牲实时性换取可用性，适合非强一致性场景。三、数据库与SQL（共4题，每题5分，合计20分）考察内容：SQL查询、数据库设计题目9（5分）：给定表`Orders`（`order_id,customer_id,order_date,total_amount`），查询2023年每月总销售额。答案：sqlSELECTDATE_FORMAT(order_date,'%Y-%m')ASmonth,SUM(total_amount)AStotal_salesFROMOrdersWHEREYEAR(order_date)=2023GROUPBYmonthORDERBYmonth;解析：-`DATE_FORMAT`提取年月，`SUM`聚合销售额。-`GROUPBY`按月份分组，`ORDERBY`排序。题目10（5分）：表`Employees`（`id,name,department,salary`），查询各部门平均工资，并按平均工资降序排列。答案：sqlSELECTdepartment,AVG(salary)ASavg_salaryFROMEmployeesGROUPBYdepartmentORDERBYavg_salaryDESC;解析：-`AVG`计算部门平均工资，`ORDERBYDESC`降序。题目11（5分）：表`Students`（`id,name,course,score`），查询每门课程不及格（分数<60）的学生人数。答案：sqlSELECTcourse,COUNT()ASfail_countFROMStudentsWHEREscore<60GROUPBYcourse;解析：-`WHERE`筛选不及格学生，`COUNT()`统计人数。题目12（5分）：表`Products`（`id,name,category,price`），查询价格最高的3个产品。答案：sqlSELECTid,name,category,priceFROMProductsORDERBYpriceDESCLIMIT3;解析：-`ORDERBYDESC`排序，`LIMIT3`取前三。四、综合编程（共2题，每题10分，合计20分）考察内容：编码能力、问题解决题目13（10分）：实现一个简单的LRU缓存，要求：1.支持`get(key)`和`put(key,value)`。2.容量限制为3，超出时淘汰最久未使用项。答案：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)解析：-与编程基础中的题目3类似，但容量固定为3。-关键在于维护`order`列表的更新顺序。题目14（10分）：给定一个数组`nums`，返回所有`nums[i]+nums[j]`组合（不重复），且和小于目标`target`。答案：pythondeftwo_sum_less_than_target(nums:List[int],target:int)->List[List[int]]:nums.sort()res=[]left,right=0,len(nums)-1whileleft<right:total=nums[left]+nums[right]iftotal<target:res.extend([[nums[left],