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

2026年美团技术面试题库及答案详解一、编程基础（5题，每题10分，共50分）1.题目（10分）：请编写一个函数，实现判断一个字符串是否为“回文串”。回文串是指正读和反读都相同的字符串，例如“level”、“上海自来水来自海上”等。要求不使用任何内置函数，仅用Python实现。答案：pythondefis_palindrome(s:str)->bool:s=''.join(cforcinsifc.isalnum()).lower()#去除非字母数字字符并转为小写left,right=0,len(s)-1whileleft<right:ifs[left]!=s[right]:returnFalseleft+=1right-=1returnTrue解析：首先对字符串进行预处理，去除空格和标点符号，并统一转为小写以忽略大小写差异。然后使用双指针法，从字符串两端向中间遍历，若任意字符不匹配则不是回文串。时间复杂度为O(n)，空间复杂度为O(1)。2.题目（10分）：请实现一个LRU（最近最少使用）缓存，要求支持get和put操作。缓存容量为固定值，超出容量时需淘汰最久未使用的元素。使用Python实现。答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeynotinself.cache:return-1self.order.remove(key)self.order.append(key)returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：使用哈希表`cache`存储键值对，列表`order`记录访问顺序。get操作时将访问的键移到列表末尾表示最近使用；put操作时若键已存在则更新顺序，若超出容量则删除最久未使用的元素（列表第一个）。时间复杂度为O(1)。3.题目（10分）：给定一个链表，请反转其结构，并返回反转后的头节点。假设链表节点定义如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next答案：pythondefreverse_list(head:ListNode)->ListNode:prev,curr=None,headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev解析：使用三指针法：prev为前驱节点，curr为当前节点，next_node暂存下一个节点。循环中逐个反转next指向，最终prev为反转后的头节点。时间复杂度为O(n)，空间复杂度为O(1)。4.题目（10分）：请实现快速排序算法，对任意整数数组进行排序。要求原地排序（不使用额外数组），并给出平均时间复杂度和最坏时间复杂度。答案：pythondefquick_sort(arr:list,left:int,right:int)->None:ifleft>=right:returnpivot=arr[left]low,high=left,rightwhilelow<high:whilelow<highandarr[high]>=pivot:high-=1arr[low]=arr[high]whilelow<highandarr[low]<=pivot:low+=1arr[high]=arr[low]arr[low]=pivotquick_sort(arr,left,low-1)quick_sort(arr,low+1,right)解析：选择基准值（pivot）后，通过双指针法将数组分为小于和大于基准的两部分，然后递归排序子数组。平均时间复杂度为O(nlogn)，最坏为O(n²)（如已排序数组）。原地排序避免额外空间。5.题目（10分）：请编写一个函数，统计一个二叉树中所有路径和为特定值（如8）的路径数量。假设二叉树节点定义如下：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right答案：pythondefpath_sum(root:TreeNode,target:int)->int:defdfs(node,current_sum,path_count):ifnotnode:returnpath_countcurrent_sum+=node.valifcurrent_sum==target:path_count+=1path_count=dfs(node.left,current_sum,path_count)path_count=dfs(node.right,current_sum,path_count)returnpath_countreturndfs(root,0,0)解析：采用深度优先搜索（DFS）遍历树，累加路径和。若当前路径和等于目标值则计数。递归左右子树并回溯。时间复杂度为O(n²)（最坏情况），空间复杂度为O(n)（递归栈）。二、系统设计（3题，每题20分，共60分）1.题目（20分）：美团外卖在高峰期（如11:00-12:00）订单量激增，请设计一个分布式限流系统，防止后端服务崩溃。要求支持预热、削峰和降级策略。答案：方案：1.预热阶段：提前（如提前30分钟）向缓存（Redis）预置令牌，按时间窗口（如每分钟）分配。2.削峰阶段：若流量超限，通过队列（Kafka）暂存请求，后续异步处理。3.降级阶段：当系统负载过高时，关闭非核心接口（如优惠券领取），优先保障核心路径（如下单）。技术选型：-限流：Redis分布式锁+令牌桶算法-异步处理：Kafka+车道队列（如RabbitMQ）-监控：Prometheus+Grafana解析：限流需兼顾平滑性和弹性。令牌桶算法可防突发，Redis缓存高并发读写。削峰通过消息队列平滑流量，降级需明确业务优先级。美团实际采用灰度发布和熔断器（Hystrix）实现。2.题目（20分）：设计美团骑手分配系统，要求在3秒内为每个新订单匹配最优骑手。假设输入为订单位置、骑手实时位置和状态。答案：方案：1.数据结构：-订单：`{id,lat,lng,created_at}`-骑手：`{id,lat,lng,status,last_assigned_time}`2.核心算法：-使用R-tree索引（PostGIS）快速筛选附近骑手。-结合距离（曼哈顿距离）+等待时长（优先未分配骑手）排序。3.优化：-骑手状态实时更新（WebSocket推送）。-冷启动优化：新骑手优先分配附近订单。解析：高并发场景下需平衡精度和效率。R-tree适合地理空间查询，但若骑手数量极大（如百万级）需分层（如先按区域分配）。美团实际采用多级调度：区域→网格→订单分配。3.题目（20分）：设计一个支持高并发的短链接系统，要求在用户访问时能快速解析为原URL。假设每日请求量达百万级。答案：方案：1.短链接生成：-使用62进制（a-z,A-Z,0-9）+哈希算法（如SHA256）生成短码。-缓存前缀（如`http://meituan.me/`）。2.解析流程：-HTTP请求命中本地缓存（Redis）。-若未命中，通过短码查数据库（分片表+索引）。3.性能优化：-负载均衡（Nginx反向代理）。-数据库预热（定时加载热点短码）。解析：需解决高并发下的缓存穿透和雪崩问题。分片表（如按短码首字母分表）可提升查询效率。美团实际使用Tengine+Redis+ShardingSphere实现，并监控短码生成冲突率。三、数据库与存储（2题，每题15分，共30分）1.题目（15分）：美团外卖订单表（`orders`）字段包括`order_id`（主键）、`user_id`、`total_amount`、`status`（如待支付、已支付）、`created_at`。请设计索引策略以优化以下查询：1)筛选某用户最近一个月的订单。2)统计不同状态的订单数量。答案：索引设计：1)`user_id+created_at`组合索引（左前缀原则）：sqlCREATEINDEXidx_user_timeONorders(user_id,created_at);2)`status`单独索引：sqlCREATEINDEXidx_statusONorders(status);解析：组合索引可同时加速范围查询和排序。美团实际采用覆盖索引（如`user_id+status+created_at`）进一步减少扫描。注意避免冗余索引（如`status`已隐含在组合索引中）。2.题目（15分）：设计美团点评的评论存储方案，要求支持：-用户发布评论时实时更新对应商户的评分。-支持分页查询（如每页10条）。答案：方案：1.数据表：sqlCREATETABLEcomments(idBIGINTAUTO_INCREMENTPRIMARYKEY,user_id,merchant_id,rating,content,created_atDATETIMEDEFAULTCURRENT_TIMESTAMP,INDEXidx_merchant_rating(merchant_id,ratingDESC,created_atDESC));2.评分计算：-使用RedisLua脚本计算加权平均分（防刷分）。lualocaltotal,count=redis.call('HGETALL',KEYS[1]);total=tonumber(total)or0;count=tonumber(count)or0;returnmath.floor((total+rating)/(count+1)100)/100;3.分页优化：-MySQLLIMIT10+offset，但offset不适用于大数据量。-可改用`WHEREid>last_id`的游标方式。解析：评分计算需原子性，RedisLua脚本可保证。分页场景下offset效率低，美团实际使用时间戳+ID范围。商户表需建立`merchant_id`索引以加速关联查询。四、分布式与中间件（2题，每题20分，共40分）1.题目（20分）：美团点评的秒杀活动涉及库存扣减，请设计一个防超卖、高并发的库存系统。要求支持分布式事务和异步补偿。答案：方案：1.库存表设计：sqlCREATETABLEstock(product_id,stockINT,versionINT,INDEXidx_product(product_id));2.扣减逻辑：-分布式锁（RedisSETNX+过期）。-使用CAS（Compare-And-Swap）更新库存和version。3.异步补偿：-若扣减失败，消息队列（RabbitMQ）记录失败订单，定时重试。解析：超卖核心在于原子性，Redis锁+CAS可避免。美团实际采用Seata分布式事务框架（2PC）+补偿任务。库存表version字段用于乐观锁检测。2.题目（20分）：设计美团外卖的实时推荐系统，要求用户打开App时在2秒内展示个性化菜品。假设输入为用户历史