微软面试经验面试题详解

2026年微软面试经验：面试题详解编程题（共5题，每题15分，总分75分）1.字符串反转（15分）题目：给定一个字符串`s`，请原地反转字符串中的每个单词，单词之间由一个或多个空格分隔。注意：输入字符串中可能存在前导、尾随或多个连续空格。示例：输入：`"helloworld!"`输出：`"world!hello"`要求：-不能使用额外的内存空间（除了几个变量）。-时间复杂度：O(n)，空间复杂度：O(1)。答案：cppinclude<iostream>include<string>include<algorithm>voidreverseWords(std::string&s){//Step1:去除首尾空格intstart=0,end=s.size()-1;while(start<=end&&s[start]=='')start++;while(end>=start&&s[end]=='')end--;s=s.substr(start,end-start+1);//Step2:反转整个字符串std::reverse(s.begin(),s.end());//Step3:反转每个单词intn=s.size();inti=0;while(i<n){//找到单词的起始和结束位置while(i<n&&s[i]=='')i++;//跳过前导空格intj=i;while(j<n&&s[j]!='')j++;//找到单词的结束位置std::reverse(s.begin()+i,s.begin()+j);i=j;}}intmain(){std::strings="helloworld!";reverseWords(s);std::cout<<s<<std::endl;//输出："world!hello"return0;}解析：1.去除首尾空格：通过双指针从两端向中间移动，跳过前导和尾随空格，然后截取有效部分。2.反转整个字符串：将整个字符串翻转，此时单词顺序正确但单词内部字符顺序颠倒。3.反转每个单词：再次遍历字符串，找到每个单词的起始和结束位置，然后逐个翻转单词内部的字符。时间复杂度：O(n)，每个字符被访问3次（去空格、整体反转、单词反转）。空间复杂度：O(1)，仅使用常数个额外变量。2.二叉树的最大深度（15分）题目：给定一个二叉树的根节点`root`，返回其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。示例：输入：[3,9,20,null,null,15,7]输出：3解释：3/\920/\157要求：-可以使用递归或迭代方法解决。答案（递归方法）：cppinclude<iostream>include<vector>include<queue>//Definitionforabinarytreenode.structTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};classSolution{public:intmaxDepth(TreeNoderoot){if(!root)return0;return1+std::max(maxDepth(root->left),maxDepth(root->right));}};intmain(){//构建示例二叉树TreeNoderoot=newTreeNode(3);root->left=newTreeNode(9);root->right=newTreeNode(20);root->right->left=newTreeNode(15);root->right->right=newTreeNode(7);Solutionsol;std::cout<<sol.maxDepth(root)<<std::endl;//输出：3return0;}解析：-递归方法的核心是“分治”思想：二叉树的最大深度=左子树最大深度+右子树最大深度+1（当前节点）。-基本情况：空节点的高度为0。-时间复杂度：O(n)，每个节点被访问一次。-空间复杂度：O(h)，递归栈的深度等于二叉树的高度。3.爬楼梯（15分）题目：假设你正在爬楼梯。需要每次爬1或2步，到达楼顶。给定一个整数`n`，返回到达楼顶的不同方法的总数。示例：输入：`n=3`输出：`3`解释：1.1,1,12.1,23.2,1要求：-可以使用动态规划或数学方法解决。答案（动态规划）：cppinclude<iostream>include<vector>classSolution{public:intclimbStairs(intn){if(n==1)return1;std::vector<int>dp(n+1,0);dp[1]=1;dp[2]=2;for(inti=3;i<=n;++i){dp[i]=dp[i-1]+dp[i-2];}returndp[n];}};intmain(){Solutionsol;std::cout<<sol.climbStairs(3)<<std::endl;//输出：3return0;}解析：-动态规划方程：`dp[i]=dp[i-1]+dp[i-2]`，因为到达第`i`阶的方法数等于到达第`i-1`阶和第`i-2`阶的方法数之和。-初始条件：`dp[1]=1`（一步到达），`dp[2]=2`（两步到达）。-时间复杂度：O(n)，需要遍历到`n`。-空间复杂度：O(n)，使用数组存储中间结果。4.数组中的重复数字（15分）题目：给定一个包含`n`个整数的数组`nums`，判断数组中是否存在重复的数字。如果存在，返回`true`；否则返回`false`。示例：输入：`[1,2,3,1]`输出：`true`要求：-不能使用额外的内存空间（除了几个变量）。答案（排序方法）：cppinclude<iostream>include<vector>include<algorithm>classSolution{public:boolcontainsDuplicate(std::vector<int>&nums){std::sort(nums.begin(),nums.end());for(inti=1;i<nums.size();++i){if(nums[i]==nums[i-1])returntrue;}returnfalse;}};intmain(){Solutionsol;std::vector<int>nums={1,2,3,1};std::cout<<std::boolalpha<<sol.containsDuplicate(nums)<<std::endl;//输出：truereturn0;}解析：-排序后，重复的数字会相邻出现。-遍历排序后的数组，比较相邻元素是否相等。-时间复杂度：O(nlogn)，主要来自排序。-空间复杂度：O(1)，如果排序是原地排序（如快速排序）。5.最长有效括号（15分）题目：给定一个字符串`s`，其中只包含字符`'('`和`')'`，返回最长有效（括号匹配）括号的长度。示例：输入：`"(()"`输出：`2`解释：最长有效括号为`"()"`。要求：-可以使用栈或动态规划方法解决。答案（动态规划）：cppinclude<iostream>include<vector>classSolution{public:intlongestValidParentheses(std::strings){intn=s.size();std::vector<int>dp(n,0);intmaxLen=0;for(inti=1;i<n;++i){if(s[i]==')'){if(s[i-1]=='('){dp[i]=(i>=2?dp[i-2]:0)+2;}elseif(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='('){dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;}maxLen=std::max(maxLen,dp[i]);}}returnmaxLen;}};intmain(){Solutionsol;std::cout<<sol.longestValidParentheses("(()")<<std::endl;//输出：2return0;}解析：-动态规划方程：-如果`s[i]==')'`且`s[i-1]=='('`，则`dp[i]=dp[i-2]+2`。-如果`s[i]==')'`且`s[i-1]==')'`，且`s[i-dp[i-1]-1]=='('`，则`dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2`。-初始化：`dp[0]=0`。-时间复杂度：O(n)，每个字符被访问一次。-空间复杂度：O(n)，使用数组存储中间结果。系统设计题（共2题，每题30分，总分60分）1.设计URL短链接服务（30分）题目：设计一个URL短链接服务，如`tinyurl`。用户输入一个长URL，系统返回一个短URL；用户访问短URL时，系统返回原始的长URL。要求：-短URL应尽可能短且唯一。-支持高并发访问。-提供基本的统计功能（如短链接被访问的次数）。解析：1.数据结构设计：-使用哈希表（如Redis）存储短URL与长URL的映射，确保快速查找。-使用自增ID或随机生成短码（如62进制编码）作为短URL。2.短URL生成：-将自增ID或随机码编码为短字符串（如`a-zA-Z0-9`）。-例如，ID1编码为`"a"`，ID2编码为`"b"`，ID1000编码为`"z0"`。3.高并发处理：-使用分布式缓存（如RedisCluster）分片存储数据。-短URL生成和查询时使用锁或CAS操作保证原子性。4.统计功能：-在哈希表中存储短URL的访问次数，每次访问时更新计数。技术选型建议：-后端：Node.js/Go（高并发）-缓存：Redis（高性能）-数据库：MongoDB（存储长URL和统计信息）2.设计微博系统（30分）题目：设计一个微博系统，支持用户发布、关注、点赞、评论等功能。要求：-支持百万级用户和动态（微博）。-支持实时关注动态（如使用WebSocket）。-提供基本的搜索功能（如按关键词搜索微博）。解析：1.数据结构设计：-用户表：存储用户基本信息（ID、昵称、关注列表等）。-动态表：存储微博内容（ID、用户ID、内容、时间、点赞数等）。-关注关系表：存储用户关注关系（ID、关注者、被关注者）。-点赞表：存储用户对动态的点赞关系（ID、用户ID、动态ID）。-评论表：存储用户对动态的评论（ID、用户ID、动态ID、评论内容）。2.高并发处理：-使用分布式数据库（如TiDB）支持读写分离。-动态发布时使用消息队列（如Kafka）异步更新相关表。3.实时关注动态：-使用WebSocket或Server-SentEvents（SSE）推送新动态。-用户关注列表存储在内存中（如Redis），快速查询。4.搜索功能：-使用Elasticsearch或Solr索引动态内容，支持全文搜索。-搜索时按时间、热度等排序结果。技术选型建议：-后端：SpringBoot（Java）或Django（Python）-数据库：TiDB（分布式事务）-缓存：Redis（用户会话、关注列表）-消息队列：Kafka（异步更新）-搜索：Elasticsearch答案和解析（单独列出）编程题部分：1.字符串反转：-答案见上方代码。解析见上方。2.二叉树的最大深度：-答案见上方代码。解析见上方。3.爬楼梯：-答案见上方代码。解析见上方。4.数组中的重复数字：-答案见上方代码。解析见上方。5.最长有效括号：-答案见上方代码。解析见上方。系统设计题部分：1.URL短链接服务：-数据结构：哈希表（Redis）+短URL编