美团技术专家面试问题集及解析

2026年美团技术专家面试问题集及解析一、算法与数据结构（共5题，每题10分）1.题目：给定一个包含重复元素的数组，找出数组中不重复的子序列的所有可能。例如，输入`[1,2,2]`，输出`[1,2],[1,2],[1]`。请用递归和动态规划两种方法实现。2.题目：美团外卖系统中，用户常需要查询“附近3公里内有优惠的商家”。假设你有一个二维点集（经纬度），如何高效地找出距离用户最近的前K个商家？请设计算法并说明时间复杂度。3.题目：实现一个LRU（最近最少使用）缓存，支持`get`和`put`操作。缓存容量为固定值`capacity`。例如：-`LRU.put(1,1)`-`LRU.put(2,2)`-`LRU.get(1)`返回`1`-`LRU.put(3,3)`（此时缓存容量已满，需要淘汰最久未使用的`2`）请用双向链表和哈希表实现。4.题目：美团点评需要统计每个城市的“最活跃商家”（每天订单量最高的商家）。假设每天有数百万订单数据，订单包含用户ID、商家ID、时间戳，如何设计一个高效的数据结构和算法来支持每日快速统计？5.题目：实现一个Trie（前缀树），支持插入、搜索和前缀匹配功能。例如：-`Trie.insert("美团")`-`Trie.search("美")`返回`True`-`Trie.startsWith("美")`返回`[美团]`请说明如何优化空间复杂度。答案与解析1.答案：递归方法：pythondefsubsetsWithDup(nums):defbacktrack(start,path):res.append(path[:])foriinrange(start,len(nums)):ifi>startandnums[i]==nums[i-1]:continuepath.append(nums[i])backtrack(i+1,path)path.pop()nums.sort()res=[]backtrack(0,[])returnres解析：-先对数组排序，避免重复子序列。-使用`start`参数防止同一层重复选择相同元素。-时间复杂度O(N×2^N)，空间复杂度O(N)。动态规划方法：pythondefsubsetsWithDup(nums):nums.sort()dp=[[]]fornuminnums:ifdp[-1]anddp[-1][-1]==num:dp+=[i+[num]foriindp[-1:]]else:dp+=[i+[num]foriindp]returndp[1:]解析：-类似背包问题，通过动态构建子集列表避免重复。-时间复杂度O(N×2^N)，空间复杂度O(N×2^N)。2.答案：算法：使用优先队列（最小堆）+哈希表记录每个商家距离。pythonimportheapqdefnearest_k_shops(points,user):heap=[]forshopinpoints:dist=((shop[0]-user[0])2+(shop[1]-user[1])2)0.5heapq.heappush(heap,(dist,shop))iflen(heap)>k:heapq.heappop(heap)return[shopfor_,shopinheap]解析：-时间复杂度O(NlogK)，空间复杂度O(K)。-美团场景下，K通常较小（如10-100），此方法高效。3.答案：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head=ListNode(0,0)self.tail=ListNode(0,0)self.head.next=self.tailself.tail.prev=self.headclassListNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key):ifkeyinself.cache:node=self.cache[key]self._move_to_front(node)returnnode.valuereturn-1defput(self,key,value):ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_front(node)else:iflen(self.cache)==self.capacity:self._remove_LRU()new_node=self.ListNode(key,value)self.cache[key]=new_nodeself._add_to_front(new_node)def_move_to_front(self,node):self._remove_node(node)self._add_to_front(node)def_remove_node(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add_to_front(self,node):node.next=self.head.nextnode.next.prev=nodenode.prev=self.headself.head.next=nodedef_remove_LRU(self):lru=self.tail.prevself._remove_node(lru)解析：-双向链表维护访问顺序，哈希表快速定位节点。-时间复杂度O(1)，空间复杂度O(capacity)。4.答案：数据结构：-使用`hashmap<city,hashmap<shop_id,order_count>>`记录每个城市的商家订单量。算法：-每日订单处理时，更新对应城市商家的订单量。-每日统计时，遍历每个城市的商家订单量，找出最大值。pythonfromcollectionsimportdefaultdictclassCityShopStats:def__init__(self):self.stats=defaultdict(lambda:defaultdict(int))defprocess_order(self,user_id,shop_id,city,timestamp):self.stats[city][shop_id]+=1defget_most_active_shops(self,city):ifcitynotinself.stats:return[]returnsorted(self.stats[city].items(),key=lambdax:-x[1])[:100]解析：-美团场景下，城市和商家数量有限，此方法高效。-时间复杂度O(N+C×K)，空间复杂度O(C×M)，C为城市数，M为商家数。5.答案：pythonclassTrieNode:def__init__(self):self.children={}self.is_end=FalseclassTrie:def__init__(self):self.root=TrieNode()definsert(self,word):node=self.rootforcharinword:ifcharnotinnode.children:node.children[char]=TrieNode()node=node.children[char]node.is_end=Truedefsearch(self,word):node=self._find(word)returnnode.is_enddefstartsWith(self,prefix):node=self._find(prefix)returnself._collect(node,prefix)def_find(self,word):node=self.rootforcharinword:ifcharnotinnode.children:returnNonenode=node.children[char]returnnodedef_collect(self,node,prefix):res=[]ifnode.is_end:res.append(prefix)forchar,next_nodeinnode.children.items():res.extend(self._collect(next_node,prefix+char))returnres解析：-前缀树优化空间通过共享节点。-时间复杂度O(L)，空间复杂度O(N×L)，L为单词长度。二、系统设计（共3题，每题15分）1.题目：设计美团外卖的“优惠券秒杀”系统。要求：-支持同时处理10万用户并发抢购，优惠券数量有限（如100张）。-系统需高可用、低延迟（毫秒级）。-提供防刷单机制。2.题目：设计美团打车“实时路况”功能。输入：城市道路网络图、车辆实时位置和速度。输出：每个路段的拥堵状态（缓行、畅通）。请说明数据结构和算法。3.题目：设计美团闪购“即时配送”系统，要求：-支持100万级订单并发处理。-如何保证配送员接单公平性（如抢单算法）？-如何处理配送员取消订单的情况？答案与解析1.答案：系统架构：1.负载均衡层：使用F5或Nginx分流请求。2.缓存层：Redis存储优惠券剩余数量，设置过期时间。3.业务处理层：使用消息队列（Kafka）异步处理订单，防止超卖。4.数据库层：使用分库分表存储优惠券信息，读多写少可使用Redis。防刷单：-用户行为限制（如1秒内不能重复请求）。-IP限制和设备指纹识别。-人工审核异常订单。代码示例（抢购逻辑）：pythonfromredisimportRedisimportthreadingclassSecKillSystem:def__init__(self,total_coupons):self.redis=Redis()self.lock=threading.Lock()self.redis.set('coupons',total_coupons)deftry_get_coupon(self,user_id):whileTrue:current=self.redis.decr('coupons')ifcurrent<0:self.redis.incr('coupons')returnFalsewithself.lock:ifcurrent<0:continueself.redis.set('coupons',current)returnTrue解析：-Redis高性能实现原子扣减。-锁防止并发问题。-限流和防刷单机制保证公平性。2.答案：数据结构：-使用图+并行Dijkstra算法：-道路网络为图，节点为路口，边为道路。-车辆位置和速度为动态权重。算法：1.预处理：将道路网络建为图，存储每条路的长度。2.实时更新：车辆移动时，动态调整图权重（速度越低，权重越高）。3.拥堵计算：-对每个路口，使用Dijkstra算法计算到所有目的地的最短路径。-路径权重越高，判定为拥堵。伪代码：pythondefupdate_traffic(graph,vehicles):forvehicleinvehicles:update_edge_weight(graph,vehicle)forintersectioningraph.nodes:dijkstra(graph,intersection)解析：-并行计算提高效率，适合城市规模场景。-权重动态调整反映实时路况。3.答案：系统架构：1.订单分发中心：使用Kafka分发订单，防止单点故障。2.配送员端：移动端APP接收订单，支持抢单和手动接单。3.调度算法：-公平抢单：随机分配订单，避免头部效应。-距离优先：订单距离配送员越近优先分配。4.取消处理：-订单取消后，重新加入池中，重新分配。-惩罚恶意取消的配送员（降低权重）。代码示例（抢单算法）：pythonimportrandomclassOrderDispatcher:defdispatch_order(self,order,riders):returnrandom.choice(riders)解析：-Kafka保证高并发处理。-公平算法防止头部配送员垄断。-惩罚机制提高系统鲁棒性。三、数据库与存储（共3题，每题10分）1.题目：美团点评需要存储用户评价（评论文本、评分、时间戳），如何设计数据库表结构？考虑高并发写入和查询性能。2.题目：设计美团外卖的“用户画像”数据库表，包含用户消费习惯、偏好等。如何优化查询效率？3.题目：美团需要存储海量商家图片（如营业执照、环境照片），如何设计存储方案？使用关系型数据库还是对象存储？答案与解析1.答案：表结构：sqlCREATETABLEreviews(idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINTNOTNULL,shop_idBIGINTNOTNULL,ratingINTCHECK(ratingBETWEEN1AND5),contentTEXT,timestampDATETIMEDEFAULTCURRENT_TIMESTAMP,INDEX(shop_id),INDEX(timestamp));优化：-使用分区表（按时间分区）。-分库分表（按`shop_id`分片）。-异步写入（消息队列写入Elasticsearch）。解析：-分区减少单表数据量，提高写入性能。-索引优化查询速度。2.答案：表结构：sqlCREATETABLEuser_profiles(user_idBIGINTPRIMARYKEY,consumption_historyJSON,preferencesJSON,last_updatedTIMESTAMPDEFAULTCURRENT_TIMESTAMPONUPDATECURRENT_TIMESTAMP,INDEX(last_updated));优化：-使用JSON类型存储结构化数据。-缓存层（Redis）缓存热点用户画像。-ES搜索支持全文查询。解析：-JSON类型减少表关联，提高查询效率。-缓存降低数据库压力。3.答案：存储方案：-图片存储：使用对象存储（如OSS），适合海量文件。-数据库：存储图片元数据（URL、类型、关联商家ID）。sqlCREATETABLEmerchant_images(idBIGINTAUTO_INCREMENTPRIMARYKEY,merchant_idBIGINTNOTNULL,image_urlVARCHAR(512),image_typeVARCHAR(50),uploaded_atDATETIMEDEFAULTCURRENT_TIMESTAMP,INDEX(merchant_id));解析：-对象存储降低数据库负担，支持高并发访问。-元数据存入关系型数据库便于管理。四、分布式与中间件（共4题，每题10分）1.题目：设计美团外卖“实时订单更新”系统。输入：用户下单事件、配送员接单事件、送达事件。输出：订单状态实时同步给用户。如何保证一致性？2.题目：美团点评需要处理“用户评论”数据，如何设计消息队列（如Kafka）的Topic和Partition？考虑数据量、消费者并行度。3.题目：设计美团闪购“分布式锁”方案。如何防止死锁和超时？4.题目：美团需要设计“分布式事务”方案，如何保证跨服务的数据一致性（如订单支付、库存扣减）？答案与解析1.答案：系统架构：1.事件总线：使用Kafka收集订单事件。2.状态机：订单状态（待接单、配送中、已完成）通过状态机管理。3.订阅者：前端实时订阅订单状态变更，推送通知。一致性保证：-幂等性设计：确保事件重复处理不导致状态错误。-补偿事务：若状态同步失败，触发重试或人工介入。解析：-Kafka保证高吞吐，状态机避免逻辑混乱。2.答案：Topic设计：-按商家ID分区（如`shop_id-123评论`）。-每个商家一个Partition或按天分区。Partition设计：-每个Partition1000条消息。-消费者分组（ConsumerGroup）支持并行处理。解析：-分区提高吞吐，消费者并行处理加快处理速度。3.答案：分布式锁方案：pythonimportredisclassDistributedLock:def__init__(self,redis_client):self.redis=redis_clientdefacquire(self,lock_id,timeout=10):whiletimeout>0:ifself.redis.set(lock_id,"locked",nx=True,ex=timeout):returnTruetimeout-=1returnFalsedefrelease(self,lock_id):self.redis.delete(lock_id)防止死锁：-锁有序分配（按`lock_id`升序）。-超时机制防止资源占用。解析：-Redis高性能实现锁。-超时