2026年微软公司软件开发面试题及答案详解

2026年微软公司软件开发面试题及答案详解一、编程题（共5题，每题15分，总分75分）1.题目（15分）：编写一个函数，输入一个正整数`n`，返回`n`的所有因子（不包括`n`本身）的平方和。例如，输入`12`，返回`1^2+2^2+3^2+4^2+6^2=1+4+9+16+36=66`。答案：pythondefsum_of_square_factors(n):ifn<=1:return0sum=0foriinrange(1,n):ifn%i==0:sum+=iireturnsum示例print(sum_of_square_factors(12))#输出：66解析：-遍历从`1`到`n-1`的所有数，检查是否能整除`n`，若能则计算其平方并累加。-时间复杂度：`O(n)`，可通过优化到`O(√n)`（遍历到`√n`即可，因因子成对出现）。2.题目（15分）：给定一个字符串列表`words`，返回其中最长的“回文子串”的长度。例如，输入`["abc","deed","cda","racecar"]`，返回`6`（"racecar"长度为6）。答案：pythondeflongest_palindrome_substring(words):ifnotwords:return0max_len=0forwordinwords:ifword==word[::-1]:#判断是否为回文max_len=max(max_len,len(word))returnmax_len示例print(longest_palindrome_substring(["abc","deed","cda","racecar"]))#输出：6解析：-直接遍历每个字符串，检查是否为回文（正反相同）。-优化方法：动态规划或中心扩展法可降低时间复杂度至`O(n^2)`。3.题目（15分）：实现一个`LRU缓存`（LeastRecentlyUsed）的设计，支持`get`和`put`操作。`get(key)`返回`key`对应的值，若不存在返回`-1`；`put(key,value)`插入或更新键值对，当缓存容量满时，删除最久未使用的键。答案：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)示例lru=LRUCache(2)lru.put(1,1)lru.put(2,2)print(lru.get(1))#输出：1lru.put(3,3)#去除键2print(lru.get(2))#输出：-1解析：-使用字典`cache`存储键值对，列表`order`记录访问顺序。-`get`操作将键移到末尾表示最近使用，`put`操作需处理容量满的情况。-可使用`collections.OrderedDict`优化实现。4.题目（15分）：设计一个算法，找出数组中重复次数超过`n/2`的元素。例如，输入`[3,2,3,1,3,3,3]`，返回`3`。答案：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate示例print(majority_element([3,2,3,1,3,3,3]))#输出：3解析：-Boyer-Moore投票算法：多数元素会抵消其他元素，最终保留候选者。-时间复杂度：`O(n)`，空间复杂度：`O(1)`。5.题目（15分）：给定一个二叉树，判断其是否为“完全二叉树”（除最后一层外，每一层节点都满，且最后一层节点从左到右连续）。例如：1/\23/\45答案：pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_complete_binary_tree(root):ifnotroot:returnTruequeue=deque([root])flag=Falsewhilequeue:node=queue.popleft()ifnode:ifflag:returnFalsequeue.append(node.left)queue.append(node.right)else:flag=TruereturnTrue示例root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)print(is_complete_binary_tree(root))#输出：True解析：-层序遍历：若遇到`None`后再出现非`None`节点，则不满足完全二叉树。-使用队列实现BFS，通过`flag`标记是否已遇到`None`。二、系统设计题（共2题，每题25分，总分50分）1.题目（25分）：设计一个短链接（TinyURL）服务，要求：-输入任意长URL，返回固定长度短链接（如`/abcd`）。-支持通过短链接反查原始URL。-高并发场景下保证唯一性和快速响应。答案：系统架构：1.短链接生成：使用Base62编码（`a-z`、`A-Z`、`0-9`）将ID映射为6位短码。2.存储：-使用Redis（缓存热点数据）+数据库（持久化）。-映射表：`{"abcd":"/long-url"}`。3.高并发处理：-请求先走负载均衡（如Nginx）。-Redis使用原子操作（如`INCR`）生成唯一ID。代码示例（伪代码）：pythonimportbase64importredisclassTinyURL:def__init__(self):self.redis=redis.Redis()self.base="/"defencode(self,long_url):生成唯一IDid=self.redis.incr("url_id")short_code=base64.urlsafe_b64encode(id.to_bytes(6,'big')).decode()[:6]self.redis.set(short_code,long_url)returnself.base+short_codedefdecode(self,short_url):short_code=short_url.split('/')[-1]returnself.redis.get(short_code)or"URLnotfound"解析：-Base62编码：将ID转为短码（如`1000`→`1rw`）。-高并发优化：Redis原子操作确保ID唯一，避免锁。-扩展性：可分片存储（如按首字母分库）。2.题目（25分）：设计一个实时消息推送系统，支持多用户订阅主题（Topic），发布消息时推送给所有订阅者。要求：-支持“广播”和“单播”（指定用户）。-低延迟（毫秒级）。-高可用（支持集群）。答案：系统架构：1.核心组件：-消息队列（Kafka/RabbitMQ）：解耦发布与订阅。-订阅中心（Redis+发布订阅）：存储用户-主题关系，实时推送。2.流程：-订阅：用户请求加入主题，Redis记录`{topic:[user1,user2]}`。-发布：-广播：将消息推送到Kafka，订阅中心监听主题，通知所有订阅者。-单播：直接向指定用户发送WebSocket消息。3.高可用：-消息队列集群（如Kafka多副本）。-Redis集群（主从+哨兵）。代码示例（伪代码）：python订阅逻辑defsubscribe(user,topic):redis.sadd(f"topic:{topic}",user)发布逻辑defpublish(topic,message):广播kafka_producer.send(topic,message)通知订阅者subscribed_users=redis.smembers(f"topic:{topic}")foruserinsubscribed_users:websocket.send(user,message)解析：-低延迟：消息队列确保发布解耦，Redis实时推送。-高可用：Kafka保证消息不丢失，Redis集群防单点。-扩展性：可增加限流（如令牌桶算法）防压垮。答案与解析汇总编程题答案：1.因子平方和：遍历除`n`外所有数，计算平方和。2.最长回文子串：遍历字符串检查回文，或使用动态规划。3.LRU缓存：使用字典