微软件工程师面试题目

2026年微软件工程师面试题目一、编程基础（5题，每题10分，共50分）1.题目：编写一个函数，实现二叉树的层序遍历（广度优先遍历）。输入为二叉树的根节点，输出为按层顺序排列的节点值列表。示例输入：3/\920/\157示例输出：`[3,9,20,15,7]`答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevel_order(root):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解析：使用队列实现层序遍历，每次处理当前层的所有节点，并将其子节点加入队列。按层级依次输出节点值，最终得到`[3,9,20,15,7]`。2.题目：给定一个字符串，找出其中不重复的最长子串的长度。示例输入：`"abcabcbb"`示例输出：`3`（最长子串为"abc"）答案：pythondeflength_of_longest_substring(s):char_set=set()left=0max_length=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_length=max(max_length,right-left+1)returnmax_length解析：使用滑动窗口技术，`left`和`right`指针分别表示子串的左右边界。遇到重复字符时，移动`left`并更新字符集合。最终返回最长无重复子串的长度。3.题目：实现一个LRU（最近最少使用）缓存，支持`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_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)解析：使用哈希表存储键值对，链表维护使用顺序。`get`操作将访问的键移动到链表末尾，`put`操作先判断是否超出容量，若超出则删除最久未使用的元素。4.题目：给定一个整数数组，返回所有和为`target`的三个数的组合。示例输入：`[-1,0,1,2,-1,-4]`,`target=0`示例输出：`[[-1,-1,2],[-1,0,1]]`答案：pythondefthree_sum(nums,target):nums.sort()result=[]n=len(nums)foriinrange(n-2):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]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnresult解析：先排序数组，使用双指针法。对于每个`i`，使用`left`和`right`指针分别指向`i+1`和`n-1`，计算三数之和，根据结果调整指针位置。避免重复解通过跳过相同元素。5.题目：实现一个函数，检查一个字符串是否是回文串（忽略非字母数字字符，不区分大小写）。示例输入：`"Aman,aplan,acanal:Panama"`示例输出：`True`答案：pythondefis_palindrome(s:str)->bool:s=''.join(c.lower()forcinsifc.isalnum())left,right=0,len(s)-1whileleft<right:ifs[left]!=s[right]:returnFalseleft+=1right-=1returnTrue解析：先过滤非字母数字字符并转为小写，然后使用双指针法从两端向中间检查字符是否相等。若全部匹配则返回`True`。二、系统设计（2题，每题25分，共50分）1.题目：设计一个简单的微博系统，支持用户发布、关注、点赞和查看时间线。要求：-用户可以发布最多500字符的微博。-用户可以关注/取消关注其他用户。-用户的时间线包含自己发布的微博和所有关注用户的最新微博，按时间倒序排列。-点赞操作记录用户对某条微博的点赞状态。解析：系统架构：1.用户模块：存储用户信息（ID、昵称等）。2.微博模块：存储微博内容、发布时间、发布者ID、点赞数等。3.关系模块：存储关注关系（用户ID、关注者ID）。4.点赞模块：存储点赞记录（用户ID、微博ID）。数据存储：-用户：`users`表（`user_id`,`name`）。-微博：`tweets`表（`tweet_id`,`user_id`,`content`,`timestamp`）。-关注关系：`follows`表（`follower_id`,`followee_id`）。-点赞：`likes`表（`user_id`,`tweet_id`）。时间线实现：使用SQL查询或Redis实现。例如，SQL查询可按时间倒序获取用户发布的微博和所有关注者的最新微博。2.题目：设计一个高并发的短链接生成系统，要求：-支持快速生成和解析短链接。-链接长度尽可能短（如`/abc123`）。-高可用、高并发（支持每秒百万级请求）。解析：系统架构：1.短链接生成：使用自增ID或哈希算法（如Base62）映射为短码。2.分布式存储：使用Redis或Memcached缓存热点链接。3.数据库：存储长链接和短链接映射关系。4.负载均衡：使用Nginx或HAProxy分发请求。技术选型：-短码生成：-自增ID+Base62编码（`a-z`,`A-Z`,`0-9`，6位可覆盖`64^6`种组合）。-或Snowflake算法生成唯一ID。-缓存策略：-Redis设置过期时间（如24小时），热点链接优先缓存。-高并发处理：-使用消息队列（如Kafka）削峰填谷。-数据库读写分离，使用分库分表（如ShardingSphere）。示例代码（短码生成）：pythonimportstringimportrandomCHARSET=string.ascii_letters+string.digitsCHARSET_LEN=len(CHARSET)defencode_base62(num):ifnum==0:returnCHARSET[0]result=[]whilenum>0:num,rem=divmod(num,CHARSET_LEN)result.append(CHARSET[rem])return''.join(reversed(result))defdecode_base62(short_code):num=0forcharinshort_code:num=numCHARSET_LEN+CHARSET.index(char)returnnum三、数据库与SQL（3题，每题15分，共45分）1.题目：一个电商数据库包含`orders`（订单表）和`order_items`（订单项表），结构如下：sqlCREATETABLEorders(order_idINTPRIMARYKEY,user_idINT,total_amountDECIMAL(10,2),order_dateDATE);CREATETABLEorder_items(order_item_idINTPRIMARYKEY,order_idINT,product_idINT,quantityINT,priceDECIMAL(10,2),FOREIGNKEY(order_id)REFERENCESorders(order_id));问题：查询每个用户的总订单金额，并按金额降序排列。答案：sqlSELECTo.user_id,SUM(o.total_amount)AStotal_spentFROMordersoGROUPBYo.user_idORDERBYtotal_spentDESC;解析：使用`GROUPBY`按用户ID分组，`SUM`计算总金额，`ORDERBY`降序排列。2.题目：在`orders`表中，统计最近30天内订单数量最多的3个用户。答案：sqlSELECTuser_id,COUNT()ASorder_countFROMordersWHEREorder_date>=DATE_SUB(CURDATE(),INTERVAL30DAY)GROUPBYuser_idORDERBYorder_countDESCLIMIT3;解析：使用`WHERE`过滤最近30天的订单，`GROUPBY`统计每个用户的订单数，`ORDERBY`和`LIMIT`获取前三名。3.题目：查询所有订单中，每个产品的总销量（数量）。答案：sqlSELECTduct_id,SUM(oi.quantity)AStotal_quantityFROMorder_itemsoiGROUPBYduct_id;解析：`SUM`计算每个产品的总销量，`GROUPBY`按产品ID分组。四、分布式与中间件（2题，每题20分，共40分）1.题目：设计一个高并发的秒杀系统，要求：-限制每个用户每秒只能购买1件商品。-防止超卖和并发问题。-支持分布式部署。解析：解决方案：1.数据库锁：-使用`SELECT...FORUPDATE`锁住库存表，减少超卖。-但在高并发下可能死锁。2.Redis分布式锁：-使用`SETNX`实现锁，设置过期时间防止死锁。-示例代码：pythonimportredisr=redis.Redis()lock_key="product_1000_lock"product_id=1000user_id=123deftry_lock():ifr.setnx(lock_