2026年微軟工程師面試攻略與經(jīng)典題目一、編程基礎(chǔ)（共5題，每題10分，總分50分）1.題目：給定一個(gè)整數(shù)數(shù)組，返回?cái)?shù)組中所有唯一元素的對(duì)的數(shù)量。例如，輸入`[1,2,3,4,5]`，輸出應(yīng)為`10`（所有兩兩組合）。要求：時(shí)間復(fù)雜度O(n)。2.題目：實(shí)現(xiàn)一個(gè)函數(shù)，檢查一個(gè)字符串是否為有效的括號(hào)組合。例如，輸入`"(())"`應(yīng)返回`true`，輸入`"(()"`應(yīng)返回`false`。3.題目：給定一個(gè)鏈表，反轉(zhuǎn)鏈表并返回反轉(zhuǎn)后的頭節(jié)點(diǎn)。例如，輸入`1->2->3->4`，輸出應(yīng)為`4->3->2->1`。4.題目：實(shí)現(xiàn)一個(gè)二叉樹(shù)的前序遍歷（根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)），要求使用遞歸和迭代兩種方法。5.題目：給定一個(gè)字符串，統(tǒng)計(jì)其中每個(gè)字符的出現(xiàn)次數(shù)，并按字符順序返回一個(gè)數(shù)組。例如，輸入`"hello"`，輸出應(yīng)為`[1,1,2,1,1]`（對(duì)應(yīng)h,e,l,l,o）。二、算法設(shè)計(jì)（共3題，每題15分，總分45分）1.題目：設(shè)計(jì)一個(gè)LRU（最近最少使用）緩存系統(tǒng)，支持`get`和`put`操作。`get`返回鍵對(duì)應(yīng)的值，若不存在返回`-1`；`put`插入或更新鍵值對(duì)，如果緩存已滿，則刪除最近最少使用的項(xiàng)。假設(shè)緩存容量為`3`。要求：使用哈希表和雙向鏈表實(shí)現(xiàn)，時(shí)間復(fù)雜度O(1)。2.題目：給定一個(gè)無(wú)序數(shù)組，找到數(shù)組中第k大的元素。例如，輸入`[3,2,1,5,6,4]`，k=`2`，輸出應(yīng)為`5`。要求：時(shí)間復(fù)雜度O(n)。3.題目：實(shí)現(xiàn)一個(gè)函數(shù)，判斷一個(gè)數(shù)是否為完全平方數(shù)。例如，輸入`16`，輸出`true`；輸入`14`，輸出`false`。要求：不使用內(nèi)置函數(shù)，時(shí)間復(fù)雜度O(logn)。三、系統(tǒng)設(shè)計(jì)（共2題，每題25分，總分50分）1.題目：設(shè)計(jì)一個(gè)簡(jiǎn)單的微博系統(tǒng)，支持以下功能：-用戶注冊(cè)和登錄。-發(fā)布微博（限制長(zhǎng)度為280字符）。-關(guān)注/取消關(guān)注用戶。-瀏覽關(guān)注用戶的最新微博（按時(shí)間倒序）。要求：說(shuō)明核心數(shù)據(jù)結(jié)構(gòu)和主要接口設(shè)計(jì)。2.題目：設(shè)計(jì)一個(gè)分布式任務(wù)隊(duì)列系統(tǒng)，支持以下功能：-添加任務(wù)到隊(duì)列。-消費(fèi)者從隊(duì)列中獲取任務(wù)并執(zhí)行。-任務(wù)失敗后可重新入隊(duì)。-支持任務(wù)優(yōu)先級(jí)。要求：說(shuō)明系統(tǒng)架構(gòu)、數(shù)據(jù)存儲(chǔ)方式（如Redis）和核心流程。答案與解析一、編程基礎(chǔ)1.答案：pythondefcount_unique_pairs(arr):count=0n=len(arr)foriinrange(n):forjinrange(i+1,n):ifarr[i]!=arr[j]:count+=1returncount解析：雙重循環(huán)遍歷所有可能的對(duì)，統(tǒng)計(jì)唯一對(duì)的數(shù)量。時(shí)間復(fù)雜度O(n2)，但題目要求O(n)可優(yōu)化為哈希表統(tǒng)計(jì)頻率。2.答案：pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：使用棧匹配括號(hào)，遇到右括號(hào)時(shí)檢查棧頂是否匹配。3.答案：pythondefreverseList(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：迭代反轉(zhuǎn)鏈表節(jié)點(diǎn)指針。4.答案：-遞歸：pythondefpreorder_recursive(root):ifnotroot:return[]return[root.val]+preorder_recursive(root.left)+preorder_recursive(root.right)-迭代：pythondefpreorder_iterative(root):ifnotroot:return[]stack,output=[root],[]whilestack:node=stack.pop()output.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnoutput解析：遞歸直接按根左右順序；迭代使用棧模擬遞歸過(guò)程。5.答案：pythondefcount_chars(s):return[s.count(c)forcinsorted(set(s))]解析：先排序去重，再統(tǒng)計(jì)每個(gè)字符頻率。二、算法設(shè)計(jì)1.答案：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key):ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key,value):ifkeyinself.cache:self._remove(self.cache[key])node=self.Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodenode.prev=self.headself.head.next=node解析：雙向鏈表+哈希表，鏈表頭部為最近使用，尾部為最久未使用。2.答案：pythondeffindKthLargest(nums,k):defpartition(left,right,pivot_index):pivot=nums[pivot_index]nums[pivot_index],nums[right]=nums[right],nums[pivot_index]store_index=leftforiinrange(left,right):ifnums[i]>pivot:nums[store_index],nums[i]=nums[i],nums[store_index]store_index+=1nums[right],nums[store_index]=nums[store_index],nums[right]returnstore_indexdefselect(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=random.randint(left,right)pivot_index=partition(left,right,pivot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnselect(left,pivot_index-1,k_smallest)else:returnselect(pivot_index+1,right,k_smallest)returnselect(0,len(nums)-1,len(nums)-k)解析：快速選擇算法，時(shí)間復(fù)雜度平均O(n)。3.答案：pythondefisPerfectSquare(num):left,right=1,numwhileleft<=right:mid=left+(right-left)//2ifmidmid==num:returnTrueelifmidmid<num:left=mid+1else:right=mid-1returnFalse解析：二分查找平方根，時(shí)間復(fù)雜度O(logn)。三、系統(tǒng)設(shè)計(jì)1.答案：-數(shù)據(jù)結(jié)構(gòu)：-用戶表：`id`,`username`,`password`,`follows`（用戶關(guān)注列表）。-微博表：`id`,`user_id`,`content`,`timestamp`。-接口：-注冊(cè)：`POST/register`（`username`,`password`）。-登錄：`POST/login`（`username`,`password`）。-發(fā)布：`POST/tweet`（`content`）。-關(guān)注：`POST/follow`（`followee_id`）。-瀏覽：`GET/timeline`（返回關(guān)注用戶微博）。解析：關(guān)系型數(shù)據(jù)庫(kù)存儲(chǔ)用戶和微博，關(guān)注關(guān)系維護(hù)在用戶表中。2.答案：