美团技术团队面试题及答案参考

2026年美团技术团队面试题及答案参考编程能力测试（15题，共75分）题型说明：包括算法题、数据结构题和代码实现题，考察编程基础、逻辑思维和编码能力。1.数组与字符串（2题，每题15分）题目1（15分）：给定一个包含重复数字的数组`nums`和一个整数`k`，请返回所有和为`k`的不同子数组（子数组元素顺序必须一致）。例如：输入：`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:#确保子数组不重叠result.append(nums[j+1:i+1])prefix_sum[current_sum].append(i)returnresult解析：1.使用哈希表`prefix_sum`记录前缀和及其对应的索引列表。2.遍历数组时，计算当前前缀和`current_sum`，检查`current_sum-k`是否存在于哈希表中。3.若存在，则将对应的子数组加入结果列表，并确保子数组不重叠（`j+1<i`）。4.最后返回所有不重复的子数组。题目2（15分）：实现一个函数`compress(s)`，将字符串`s`中的连续重复字符合并，并返回合并后的字符串及合并次数。例如：输入：`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.遍历字符串，统计每个字符的连续重复次数。2.遇到不同字符时，将前一个字符及其计数加入结果列表。3.合并后返回压缩字符串及合并次数（总字符数减去压缩后的字符数）。2.链表（3题，每题15分）题目3（15分）：给定一个链表，请判断其是否为回文链表。例如：输入：`1->2->2->1`输出：`True`答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefis_palindrome(head):ifnotheadornothead.next:returnTrue找到中点slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.next反转后半部分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.使用快慢指针找到链表的中点。2.反转后半部分链表，然后逐个比较前半部分和反转后的后半部分。3.若完全一致，则为回文链表。题目4（15分）：合并`k`个排序链表，返回合并后的头节点。例如：输入：`[[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.使用最小堆（优先队列）存储所有链表的头节点，按值排序。2.每次弹出堆顶节点（最小值），并将其下一个节点加入堆中。3.重复直到堆为空，完成合并。题目5（15分）：给定一个单链表，请删除链表的倒数第`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移动right到第n+1个节点for_inrange(n+1):ifrightisNone:returnhead#n大于链表长度right=right.next移动left和right直到right到达末尾whileright:left=left.nextright=right.next删除节点left.next=left.next.nextreturndummy.next解析：1.使用双指针法，先让`right`移动`n+1`步，确保`left`和`right`之间有`n`个节点。2.然后同时移动`left`和`right`，直到`right`到达末尾，此时`left`指向要删除的前一个节点。3.删除节点并返回头节点。3.树与图（3题，每题15分）题目6（15分）：给定一个二叉树，请判断其是否是平衡二叉树（左右子树高度差不超过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.使用后序遍历计算每个节点的高度。2.若左右子树高度差大于1或子树不平衡（返回-1），则整棵树不平衡。3.否则返回最大高度。题目7（15分）：给定一个无向图，请判断其是否为二分图（可染成两种颜色，相邻节点颜色不同）。例如：输入：`[[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.使用深度优先搜索（DFS）遍历图，尝试用两种颜色染色。2.若遇到相邻节点颜色相同，则不是二分图。3.若所有节点均满足，则为二分图。题目8（15分）：给定一个`n`皇后问题的棋盘大小`n`，请返回所有合法的解。例如：输入：`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.使用回溯法，逐行放置皇后，并检查冲突（列、主对角线、副对角线）。2.若不冲突则继续放置下一行，否则回溯。3.最终返回所有合法解。4.系统设计（3题，每题25分）题目9（25分）：设计一个URL短链接服务，要求：1.支持将任意长度的URL转换为固定长度的短链接。2.支持通过短链接快速反查原始URL。3.高并发场景下响应时间小于100ms。答案：1.数据结构：-使用哈希表存储短链接与原始URL的映射。-使用自增ID或Base62编码生成短链接。2.算法：-将原始URL记录到数据库（如Redis）中，并生成唯一ID。-将ID编码为短链接（如`/a1b2c`）。3.高并发优化：-使用CDN缓存短链接请求。-使用异步写入数据库。4.示例：-请求`/some/path`返回`/a1b2c`。-请求`/a1b2c`返回`/some/path`。解析：-哈希表提供O(1)查询效率。-Base62编码（如`a-z`,`A-Z`,`0-9`）可缩短链接长度。-CDN可降低延迟，Redis可支持高并发读写。题目10（25分）：设计一个实时聊天系统，要求：1.支持单聊和群聊。2.支持消息的实时同步（延迟小于500ms）。3.支持离线消息推送。答案：1.架构：-使用WebSocket实现实时通信。-使用消息队列（如Kafka）处理离线消息。2.数据存储：-用户关系存储在数据库中（如Neo4j）。-消息存储在时序数据库（如InfluxDB）或关系型数据库中。3.离线消息：-用户离线时，消息写入Kafka。-用户上线时，消费Kafka消息并推送。4.示例：-单聊：用户A发送消息给用户B，通过WebSocket直接推送。-群聊：用户A发送消息给群组C，通过WebSocket推送给所有群成员。解析：-WebSocket保证实时性。-Kafka解耦消息生产和消费，支持离线场景。-Neo4j可优化关系查询（如查找群成员）。题目11（25分）：设计一个分布式计数器服务，要求：1.支持高并发自增。2.数据一致性好，容错性强。3.支持分桶统计（如按分钟统计请求量）。答案：1.架构：-使用Redis的`INCR`命令实现原子自增。-使用Redis的`HINCRBY`实现分桶统计。2.数据存储：-计数器ID存储在Redis中。-分桶数据存储在时序数据库（如Prometheus）或Redis的Hash结构中。3.容错性：-使用Redis集群或哨兵机制保证可用性。4.示例：-单点自增：`INCRcounter_id`。-分桶统计：`HINCRBYcounter_bucket1minute:1`。解析：-Redis原子操作保证并发安全。-集群和哨兵机制提高可用性。-时序数据库优化分桶数据的存储和查询。5.算法与数据结构（3题，每题25分）题目12（25分）：给定一个数组`nums`，请返回所有唯一的子集（包含空集）。例如：输入：`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#跳过重复元素subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult解析：1.先排序数组，去重。2.使用回溯法生成所有子集，跳过重复元素。3.`subset.copy()`防止引用问题。题目13（25分）：给定一个无重复元素的数组`nums`，请返回所有可能的排列。例如：输入：`nums=[1,2,3]`输出：`[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1