2026年美團(tuán)技術(shù)團(tuán)隊(duì)面試題及答案參考編程能力測(cè)試（15題，共75分）題型說明：包括算法題、數(shù)據(jù)結(jié)構(gòu)題和代碼實(shí)現(xiàn)題，考察編程基礎(chǔ)、邏輯思維和編碼能力。1.數(shù)組與字符串（2題，每題15分）題目1（15分）：給定一個(gè)包含重復(fù)數(shù)字的數(shù)組`nums`和一個(gè)整數(shù)`k`，請(qǐng)返回所有和為`k`的不同子數(shù)組（子數(shù)組元素順序必須一致）。例如：輸入：`nums=[1,2,3,1],k=3`輸出：`[[1,2],[1,2,3,1],[3,1]]`答案：pythondeffind_subarrays(nums,k):fromcollectionsimportdefaultdictprefix_sum=defaultdict(list)prefix_sum[0].append(-1)#初始化前綴和0在索引-1的位置current_sum=0result=[]fori,numinenumerate(nums):current_sum+=numforjinprefix_sum[current_sum-k]:ifj+1<i:#確保子數(shù)組不重疊result.append(nums[j+1:i+1])prefix_sum[current_sum].append(i)returnresult解析：1.使用哈希表`prefix_sum`記錄前綴和及其對(duì)應(yīng)的索引列表。2.遍歷數(shù)組時(shí)，計(jì)算當(dāng)前前綴和`current_sum`，檢查`current_sum-k`是否存在于哈希表中。3.若存在，則將對(duì)應(yīng)的子數(shù)組加入結(jié)果列表，并確保子數(shù)組不重疊（`j+1<i`）。4.最后返回所有不重復(fù)的子數(shù)組。題目2（15分）：實(shí)現(xiàn)一個(gè)函數(shù)`compress(s)`，將字符串`s`中的連續(xù)重復(fù)字符合并，并返回合并后的字符串及合并次數(shù)。例如：輸入：`s="aabcccccaaa"`輸出：`("a2b1c5a3",1)`答案：pythondefcompress(s):ifnots:return"",0compressed=[]count=1foriinrange(1,len(s)):ifs[i]==s[i-1]:count+=1else:compressed.append(s[i-1]+str(count))count=1compressed.append(s[-1]+str(count))result=''.join(compressed)returnresult,len(compressed)-1解析：1.遍歷字符串，統(tǒng)計(jì)每個(gè)字符的連續(xù)重復(fù)次數(shù)。2.遇到不同字符時(shí)，將前一個(gè)字符及其計(jì)數(shù)加入結(jié)果列表。3.合并后返回壓縮字符串及合并次數(shù)（總字符數(shù)減去壓縮后的字符數(shù)）。2.鏈表（3題，每題15分）題目3（15分）：給定一個(gè)鏈表，請(qǐng)判斷其是否為回文鏈表。例如：輸入：`1->2->2->1`輸出：`True`答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefis_palindrome(head):ifnotheadornothead.next:returnTrue找到中點(diǎn)slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.next反轉(zhuǎn)后半部分prev=Nonewhileslow:next_node=slow.nextslow.next=prevprev=slowslow=next_node比較前后部分left,right=head,prevwhileright:#只需比較后半部分ifleft.val!=right.val:returnFalseleft=left.nextright=right.nextreturnTrue解析：1.使用快慢指針找到鏈表的中點(diǎn)。2.反轉(zhuǎn)后半部分鏈表，然后逐個(gè)比較前半部分和反轉(zhuǎn)后的后半部分。3.若完全一致，則為回文鏈表。題目4（15分）：合并`k`個(gè)排序鏈表，返回合并后的頭節(jié)點(diǎn)。例如：輸入：`[[1,4,5],[1,3,4],[2,6]]`輸出：`1->1->2->3->4->4->5->6`答案：pythonimportheapqfromtypingimportList,OptionalclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeKLists(lists:List[Optional[ListNode]])->Optional[ListNode]:min_heap=[]fori,headinenumerate(lists):ifhead:heapq.heappush(min_heap,(head.val,i,head))dummy=ListNode(0)current=dummywhilemin_heap:val,idx,node=heapq.heappop(min_heap)current.next=nodecurrent=current.nextifnode.next:heapq.heappush(min_heap,(node.next.val,idx,node.next))returndummy.next解析：1.使用最小堆（優(yōu)先隊(duì)列）存儲(chǔ)所有鏈表的頭節(jié)點(diǎn)，按值排序。2.每次彈出堆頂節(jié)點(diǎn)（最小值），并將其下一個(gè)節(jié)點(diǎn)加入堆中。3.重復(fù)直到堆為空，完成合并。題目5（15分）：給定一個(gè)單鏈表，請(qǐng)刪除鏈表的倒數(shù)第`n`個(gè)節(jié)點(diǎn)，并返回頭節(jié)點(diǎn)。例如：輸入：`1->2->3->4->5,n=2`輸出：`1->2->3->5`答案：pythondefremoveNthFromEnd(head:Optional[ListNode],n:int)->Optional[ListNode]:dummy=ListNode(0,head)left=right=dummy移動(dòng)right到第n+1個(gè)節(jié)點(diǎn)for_inrange(n+1):ifrightisNone:returnhead#n大于鏈表長(zhǎng)度right=right.next移動(dòng)left和right直到right到達(dá)末尾whileright:left=left.nextright=right.next刪除節(jié)點(diǎn)left.next=left.next.nextreturndummy.next解析：1.使用雙指針法，先讓`right`移動(dòng)`n+1`步，確保`left`和`right`之間有`n`個(gè)節(jié)點(diǎn)。2.然后同時(shí)移動(dòng)`left`和`right`，直到`right`到達(dá)末尾，此時(shí)`left`指向要?jiǎng)h除的前一個(gè)節(jié)點(diǎn)。3.刪除節(jié)點(diǎn)并返回頭節(jié)點(diǎn)。3.樹與圖（3題，每題15分）題目6（15分）：給定一個(gè)二叉樹，請(qǐng)判斷其是否是平衡二叉樹（左右子樹高度差不超過1）。例如：輸入：`root=[3,9,20,null,null,15,7]`輸出：`True`答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root:TreeNode)->bool:defcheck(node:TreeNode)->int:ifnotnode:return0left_height=check(node.left)right_height=check(node.right)ifleft_height==-1orright_height==-1orabs(left_height-right_height)>1:return-1returnmax(left_height,right_height)+1returncheck(root)!=-1解析：1.使用后序遍歷計(jì)算每個(gè)節(jié)點(diǎn)的高度。2.若左右子樹高度差大于1或子樹不平衡（返回-1），則整棵樹不平衡。3.否則返回最大高度。題目7（15分）：給定一個(gè)無向圖，請(qǐng)判斷其是否為二分圖（可染成兩種顏色，相鄰節(jié)點(diǎn)顏色不同）。例如：輸入：`[[1,3],[0,2],[1,3],[0,2]]`輸出：`True`答案：pythonfromtypingimportListdefis_bipartite(graph:List[List[int]])->bool:color={}defdfs(node,c):ifnodeincolor:returncolor[node]==ccolor[node]=cforneighboringraph[node]:ifnotdfs(neighbor,notc):returnFalsereturnTruefornodeinrange(len(graph)):ifnodenotincolor:ifnotdfs(node,True):returnFalsereturnTrue解析：1.使用深度優(yōu)先搜索（DFS）遍歷圖，嘗試用兩種顏色染色。2.若遇到相鄰節(jié)點(diǎn)顏色相同，則不是二分圖。3.若所有節(jié)點(diǎn)均滿足，則為二分圖。題目8（15分）：給定一個(gè)`n`皇后問題的棋盤大小`n`，請(qǐng)返回所有合法的解。例如：輸入：`n=4`輸出：`[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]`答案：pythondefsolve_n_queens(n:int)->List[List[str]]:defbacktrack(row,diagonals,anti_diagonals,cols,state):ifrow==n:board=[]fornuminstate:board.append("".join(['Q'ifc==numelse'.'forcinrange(n)]))result.append(board)returnforcolinrange(n):diag=row-colanti_diag=row+colif(colincolsordiagindiagonalsoranti_diaginanti_diagonals):continuecols.add(col)diagonals.add(diag)anti_diagonals.add(anti_diag)state.append(col)backtrack(row+1,diagonals,anti_diagonals,cols,state)state.pop()cols.remove(col)diagonals.remove(diag)anti_diagonals.remove(anti_diag)result=[]backtrack(0,set(),set(),set(),[])returnresult解析：1.使用回溯法，逐行放置皇后，并檢查沖突（列、主對(duì)角線、副對(duì)角線）。2.若不沖突則繼續(xù)放置下一行，否則回溯。3.最終返回所有合法解。4.系統(tǒng)設(shè)計(jì)（3題，每題25分）題目9（25分）：設(shè)計(jì)一個(gè)URL短鏈接服務(wù)，要求：1.支持將任意長(zhǎng)度的URL轉(zhuǎn)換為固定長(zhǎng)度的短鏈接。2.支持通過短鏈接快速反查原始URL。3.高并發(fā)場(chǎng)景下響應(yīng)時(shí)間小于100ms。答案：1.數(shù)據(jù)結(jié)構(gòu)：-使用哈希表存儲(chǔ)短鏈接與原始URL的映射。-使用自增ID或Base62編碼生成短鏈接。2.算法：-將原始URL記錄到數(shù)據(jù)庫(kù)（如Redis）中，并生成唯一ID。-將ID編碼為短鏈接（如`/a1b2c`）。3.高并發(fā)優(yōu)化：-使用CDN緩存短鏈接請(qǐng)求。-使用異步寫入數(shù)據(jù)庫(kù)。4.示例：-請(qǐng)求`/some/path`返回`/a1b2c`。-請(qǐng)求`/a1b2c`返回`/some/path`。解析：-哈希表提供O(1)查詢效率。-Base62編碼（如`a-z`,`A-Z`,`0-9`）可縮短鏈接長(zhǎng)度。-CDN可降低延遲，Redis可支持高并發(fā)讀寫。題目10（25分）：設(shè)計(jì)一個(gè)實(shí)時(shí)聊天系統(tǒng)，要求：1.支持單聊和群聊。2.支持消息的實(shí)時(shí)同步（延遲小于500ms）。3.支持離線消息推送。答案：1.架構(gòu)：-使用WebSocket實(shí)現(xiàn)實(shí)時(shí)通信。-使用消息隊(duì)列（如Kafka）處理離線消息。2.數(shù)據(jù)存儲(chǔ)：-用戶關(guān)系存儲(chǔ)在數(shù)據(jù)庫(kù)中（如Neo4j）。-消息存儲(chǔ)在時(shí)序數(shù)據(jù)庫(kù)（如InfluxDB）或關(guān)系型數(shù)據(jù)庫(kù)中。3.離線消息：-用戶離線時(shí)，消息寫入Kafka。-用戶上線時(shí)，消費(fèi)Kafka消息并推送。4.示例：-單聊：用戶A發(fā)送消息給用戶B，通過WebSocket直接推送。-群聊：用戶A發(fā)送消息給群組C，通過WebSocket推送給所有群成員。解析：-WebSocket保證實(shí)時(shí)性。-Kafka解耦消息生產(chǎn)和消費(fèi)，支持離線場(chǎng)景。-Neo4j可優(yōu)化關(guān)系查詢（如查找群成員）。題目11（25分）：設(shè)計(jì)一個(gè)分布式計(jì)數(shù)器服務(wù)，要求：1.支持高并發(fā)自增。2.數(shù)據(jù)一致性好，容錯(cuò)性強(qiáng)。3.支持分桶統(tǒng)計(jì)（如按分鐘統(tǒng)計(jì)請(qǐng)求量）。答案：1.架構(gòu)：-使用Redis的`INCR`命令實(shí)現(xiàn)原子自增。-使用Redis的`HINCRBY`實(shí)現(xiàn)分桶統(tǒng)計(jì)。2.數(shù)據(jù)存儲(chǔ)：-計(jì)數(shù)器ID存儲(chǔ)在Redis中。-分桶數(shù)據(jù)存儲(chǔ)在時(shí)序數(shù)據(jù)庫(kù)（如Prometheus）或Redis的Hash結(jié)構(gòu)中。3.容錯(cuò)性：-使用Redis集群或哨兵機(jī)制保證可用性。4.示例：-單點(diǎn)自增：`INCRcounter_id`。-分桶統(tǒng)計(jì)：`HINCRBYcounter_bucket1minute:1`。解析：-Redis原子操作保證并發(fā)安全。-集群和哨兵機(jī)制提高可用性。-時(shí)序數(shù)據(jù)庫(kù)優(yōu)化分桶數(shù)據(jù)的存儲(chǔ)和查詢。5.算法與數(shù)據(jù)結(jié)構(gòu)（3題，每題25分）題目12（25分）：給定一個(gè)數(shù)組`nums`，請(qǐng)返回所有唯一的子集（包含空集）。例如：輸入：`nums=[1,2,2]`輸出：`[[],[1],[1,2],[1,2,2],[2],[2,2]]`答案：pythondefsubsets_with_dup(nums:List[int])->List[List[int]]:nums.sort()#先排序去重result=[]subset=[]defbacktrack(start):result.append(subset.copy())foriinrange(start,len(nums)):ifi>startandnums[i]==nums[i-1]:continue#跳過重復(fù)元素subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult解析：1.先排序數(shù)組，去重。2.使用回溯法生成所有子集，跳過重復(fù)元素。3.`subset.copy()`防止引用問題。題目13（25分）：給定一個(gè)無重復(fù)元素的數(shù)組`nums`，請(qǐng)返回所有可能的排列。例如：輸入：`nums=[1,2,3]`輸出：`[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1