美团技术专家面试题及答案详解

2026年美团技术专家面试题及答案详解一、编程基础与数据结构（共5题，每题8分，总分40分）1.题目：给定一个包含重复元素的数组，请编写代码找出所有不重复的三元组，使得这三个数的和等于给定的目标值。例如，输入数组`[1,-1,0,1,2]`，目标值`0`，输出`[-1,0,1]`和`[1,1,-2]`。要求时间复杂度为`O(n^2)`。答案与解析：pythondefthree_sum(nums,target):nums.sort()n=len(nums)res=[]foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:res.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnres解析：1.首先对数组进行排序，便于使用双指针法。2.遍历数组，对于每个`nums[i]`，使用双指针`left`和`right`分别指向`i+1`和`n-1`，计算三数之和。3.如果和等于目标值，将三元组加入结果列表，并跳过重复的`left`和`right`值。4.如果和小于目标值，移动`left`指针；如果大于目标值，移动`right`指针。5.最终返回所有不重复的三元组。2.题目：设计一个LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。`get(key)`返回键对应的值，如果不存在返回`-1`；`put(key,value)`将键值对插入缓存，如果键已存在则更新值，如果缓存已满则删除最久未使用的键。要求实现空间复杂度为`O(n)`。答案与解析：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)解析：1.使用字典`cache`存储键值对，列表`order`记录访问顺序。2.`get`操作：如果键存在，将其移到`order`尾部（表示最近访问），返回值；否则返回`-1`。3.`put`操作：如果键已存在，更新值并移动到尾部；如果缓存已满，删除`order`头部元素（最久未使用），并从`cache`中删除对应键；否则直接添加到`cache`和`order`尾部。3.题目：给定一个二叉树，判断其是否是平衡二叉树（即任意节点的左右子树高度差不超过1）。例如，`[3,9,20,null,null,15,7]`是平衡二叉树。答案与解析：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=check(node.left)right=check(node.right)ifleft==-1orright==-1orabs(left-right)>1:return-1returnmax(left,right)+1returncheck(root)!=-1解析：1.定义递归函数`check`，返回节点的高度。如果任意节点不平衡（左右子树高度差>1或子树本身不平衡），返回`-1`。2.遍历每个节点，计算左右子树高度，判断是否满足平衡条件。3.如果所有节点都满足，返回`True`；否则`False`。4.题目：实现一个函数，判断一个字符串是否是回文串（忽略大小写和非字母字符）。例如，`"Aman,aplan,acanal:Panama"`是回文串。答案与解析：pythondefis_palindrome(s:str)->bool:s=''.join(c.lower()forcinsifc.isalnum())returns==s[::-1]解析：1.将字符串转换为小写，并过滤掉非字母数字字符。2.判断处理后的字符串是否与反转字符串相同。如果相同，是回文串；否则不是。5.题目：给定一个链表，反转其节点顺序。例如，`1->2->3->4->5`反转后为`5->4->3->2->1`。答案与解析：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head:ListNode)->ListNode:prev,curr=None,headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev解析：1.使用三个指针`prev`、`curr`和`next_node`。2.遍历链表，每次将`curr.next`指向`prev`，然后移动指针。3.最终`prev`成为新的头节点。二、算法设计（共3题，每题12分，总分36分）1.题目：美团外卖系统需要处理大量的订单，假设每个订单有一个唯一的`order_id`和一个`timestamp`。请设计一个算法，统计在某个时间窗口内（例如过去5分钟）的订单数量。要求时间复杂度为`O(1)`。答案与解析：pythonclassWindowCounter:def__init__(self):self.counts={}self.current_time=0defadd_order(self,order_id:int,timestamp:int):iftimestamp-self.current_time>300:#5分钟=300秒self.counts={}self.current_time=timestampself.counts[order_id]=timestampdefcount_in_window(self)->int:returnlen(self.counts)解析：1.使用字典`counts`存储订单的`order_id`和`timestamp`。2.添加订单时，如果当前时间与上次更新时间差超过5分钟，清空字典并更新时间。3.统计窗口内订单数量即为`counts`的长度。2.题目：美团点评需要推荐用户可能感兴趣的商品。给定用户历史行为数据（如购买记录），请设计一个简单的协同过滤算法，为用户推荐相似用户购买过的商品。要求实现步骤清晰。答案与解析：1.数据预处理：统计每个用户购买的商品，构建用户-商品矩阵。2.相似度计算：使用余弦相似度计算用户之间的相似度。3.推荐生成：对于目标用户，找到最相似的`k`个用户，推荐这些用户购买过但目标用户未购买的商品。pythonimportnumpyasnpdefcosine_similarity(vec1,vec2):dot_product=np.dot(vec1,vec2)norm1=np.linalg.norm(vec1)norm2=np.linalg.norm(vec2)returndot_product/(norm1norm2)defrecommend(user_id,user_item_matrix,k=5):user_vector=user_item_matrix[user_id]similarities={}forother_id,other_vectorinenumerate(user_item_matrix):ifother_id!=user_id:sim=cosine_similarity(user_vector,other_vector)similarities[other_id]=simtop_k_users=sorted(similarities,key=similarities.get,reverse=True)[:k]recommendations=set()foruserintop_k_users:foritem,boughtinenumerate(user_item_matrix[user]):ifboughtanditemnotinuser_item_matrix[user_id]:recommendations.add(item)returnrecommendations解析：1.余弦相似度计算用户行为的向量夹角，值越大越相似。2.推荐时忽略用户自己已购买的商品。3.题目：美团地图需要优化路径规划，给定起点和终点，以及可能的中间兴趣点（如餐厅、加油站），请设计一个算法，在保证最短路径的同时，尽可能覆盖更多兴趣点。要求时间复杂度合理。答案与解析：1.问题建模：将路径规划问题转化为图论中的路径覆盖问题，使用动态规划或回溯法。2.动态规划：定义`dp[mask][u]`表示从节点`u`出发，覆盖`mask`中的节点时最短路径长度。3.转移方程：枚举所有子集，更新`dp`值，最终选择覆盖最多兴趣点的最优路径。pythondefoptimal_path_with_interests(start,end,interests):fromitertoolsimportcombinationsn=len(interests)+2#起点和终点graph=[[float('inf')]nfor_inrange(n)]foriinrange(n):graph[i][i]=0填充图（简化示例）foriinrange(n):forjinrange(i+1,n):graph[i][j]=graph[j][i]=abs(interests[i][0]-interests[j][0])+abs(interests[i][1]-interests[j][1])dp=[[float('inf')]nfor_inrange(1<<n)]dp[1<<start][start]=0formaskinrange(1<<n):foruinrange(n):ifdp[mask][u]==float('inf'):continueforvinrange(n):ifnot(mask&(1<<v))andgraph[u][v]!=float('inf'):dp[mask|(1<<v)][v]=min(dp[mask|(1<<v)][v],dp[mask][u]+graph[u][v])returndp[(1<<n)-1][end]解析：1.使用状态压缩动态规划，`mask`表示已访问的节点集合。2.转移时枚举所有可能的下一个节点，更新`dp`值。3.最终返回覆盖所有兴趣点的最短路径。三、系统设计（共2题，每题20分，总分40分）1.题目：设计一个美团外卖的实时订单分配系统，要求系统能够高效地将新订单分配给距离用户最近的骑手，并支持骑手状态实时更新（如正在接单、已完成订单）。要求说明系统架构、关键模块和数据存储方案。答案与解析：1.系统架构：-订单模