2026年微軟面試經(jīng)驗：面試題詳解編程題（共5題，每題15分，總分75分）1.字符串反轉（15分）題目：給定一個字符串`s`，請原地反轉字符串中的每個單詞，單詞之間由一個或多個空格分隔。注意：輸入字符串中可能存在前導、尾隨或多個連續(xù)空格。示例：輸入：`"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次（去空格、整體反轉、單詞反轉）?？臻g復雜度：O(1)，僅使用常數(shù)個額外變量。2.二叉樹的最大深度（15分）題目：給定一個二叉樹的根節(jié)點`root`，返回其最大深度。二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)。示例：輸入：[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（當前節(jié)點）。-基本情況：空節(jié)點的高度為0。-時間復雜度：O(n)，每個節(jié)點被訪問一次。-空間復雜度：O(h)，遞歸棧的深度等于二叉樹的高度。3.爬樓梯（15分）題目：假設你正在爬樓梯。需要每次爬1或2步，到達樓頂。給定一個整數(shù)`n`，返回到達樓頂?shù)牟煌椒ǖ目倲?shù)。示例：輸入：`n=3`輸出：`3`解釋：1.1,1,12.1,23.2,1要求：-可以使用動態(tài)規(guī)劃或數(shù)學方法解決。答案（動態(tài)規(guī)劃）：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;}解析：-動態(tài)規(guī)劃方程：`dp[i]=dp[i-1]+dp[i-2]`，因為到達第`i`階的方法數(shù)等于到達第`i-1`階和第`i-2`階的方法數(shù)之和。-初始條件：`dp[1]=1`（一步到達），`dp[2]=2`（兩步到達）。-時間復雜度：O(n)，需要遍歷到`n`。-空間復雜度：O(n)，使用數(shù)組存儲中間結果。4.數(shù)組中的重復數(shù)字（15分）題目：給定一個包含`n`個整數(shù)的數(shù)組`nums`，判斷數(shù)組中是否存在重復的數(shù)字。如果存在，返回`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;}解析：-排序后，重復的數(shù)字會相鄰出現(xiàn)。-遍歷排序后的數(shù)組，比較相鄰元素是否相等。-時間復雜度：O(nlogn)，主要來自排序。-空間復雜度：O(1)，如果排序是原地排序（如快速排序）。5.最長有效括號（15分）題目：給定一個字符串`s`，其中只包含字符`'('`和`')'`，返回最長有效（括號匹配）括號的長度。示例：輸入：`"(()"`輸出：`2`解釋：最長有效括號為`"()"`。要求：-可以使用?；騽討B(tài)規(guī)劃方法解決。答案（動態(tài)規(guī)劃）：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;}解析：-動態(tài)規(guī)劃方程：-如果`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)，使用數(shù)組存儲中間結果。系統(tǒng)設計題（共2題，每題30分，總分60分）1.設計URL短鏈接服務（30分）題目：設計一個URL短鏈接服務，如`tinyurl`。用戶輸入一個長URL，系統(tǒng)返回一個短URL；用戶訪問短URL時，系統(tǒng)返回原始的長URL。要求：-短URL應盡可能短且唯一。-支持高并發(fā)訪問。-提供基本的統(tǒng)計功能（如短鏈接被訪問的次數(shù)）。解析：1.數(shù)據(jù)結構設計：-使用哈希表（如Redis）存儲短URL與長URL的映射，確?？焖俨檎?。-使用自增ID或隨機生成短碼（如62進制編碼）作為短URL。2.短URL生成：-將自增ID或隨機碼編碼為短字符串（如`a-zA-Z0-9`）。-例如，ID1編碼為`"a"`，ID2編碼為`"b"`，ID1000編碼為`"z0"`。3.高并發(fā)處理：-使用分布式緩存（如RedisCluster）分片存儲數(shù)據(jù)。-短URL生成和查詢時使用鎖或CAS操作保證原子性。4.統(tǒng)計功能：-在哈希表中存儲短URL的訪問次數(shù)，每次訪問時更新計數(shù)。技術選型建議：-后端：Node.js/Go（高并發(fā)）-緩存：Redis（高性能）-數(shù)據(jù)庫：MongoDB（存儲長URL和統(tǒng)計信息）2.設計微博系統(tǒng)（30分）題目：設計一個微博系統(tǒng)，支持用戶發(fā)布、關注、點贊、評論等功能。要求：-支持百萬級用戶和動態(tài)（微博）。-支持實時關注動態(tài)（如使用WebSocket）。-提供基本的搜索功能（如按關鍵詞搜索微博）。解析：1.數(shù)據(jù)結構設計：-用戶表：存儲用戶基本信息（ID、昵稱、關注列表等）。-動態(tài)表：存儲微博內容（ID、用戶ID、內容、時間、點贊數(shù)等）。-關注關系表：存儲用戶關注關系（ID、關注者、被關注者）。-點贊表：存儲用戶對動態(tài)的點贊關系（ID、用戶ID、動態(tài)ID）。-評論表：存儲用戶對動態(tài)的評論（ID、用戶ID、動態(tài)ID、評論內容）。2.高并發(fā)處理：-使用分布式數(shù)據(jù)庫（如TiDB）支持讀寫分離。-動態(tài)發(fā)布時使用消息隊列（如Kafka）異步更新相關表。3.實時關注動態(tài)：-使用WebSocket或Server-SentEvents（SSE）推送新動態(tài)。-用戶關注列表存儲在內存中（如Redis），快速查詢。4.搜索功能：-使用Elasticsearch或Solr索引動態(tài)內容，支持全文搜索。-搜索時按時間、熱度等排序結果。技術選型建議：-后端：SpringBoot（Java）或Django（Python）-數(shù)據(jù)庫：TiDB（分布式事務）-緩存：Redis（用戶會話、關注列表）-消息隊列：Kafka（異步更新）-搜索：Elasticsearch答案和解析（單獨列出）編程題部分：1.字符串反轉：-答案見上方代碼。解析見上方。2.二叉樹的最大深度：-答案見上方代碼。解析見上方。3.爬樓梯：-答案見上方代碼。解析見上方。4.數(shù)組中的重復數(shù)字：-答案見上方代碼。解析見上方。5.最長有效括號：-答案見上方代碼。解析見上方。系統(tǒng)設計題部分：1.URL短鏈接服務：-數(shù)據(jù)結構：哈希表（Redis）+短URL編