美团技术大牛面试题集

2026年美团技术大牛面试题集一、编程基础与数据结构（共5题，每题10分，总分50分）1.题目：给定一个字符串，请编写一个函数，判断该字符串是否是“变位词”（即由相同字母重新排列组成的字符串）。例如，"listen"和"silent"是变位词。要求时间复杂度O(n)，空间复杂度O(1)。答案：pythondefis_anagram(s1,s2):iflen(s1)!=len(s2):returnFalsecount=[0]26foriinrange(len(s1)):count[ord(s1[i])-ord('a')]+=1count[ord(s2[i])-ord('a')]-=1foriincount:ifi!=0:returnFalsereturnTrue解析：通过统计每个字母的频率差异来判断是否为变位词。如果两个字符串的字母频率完全一致，则它们是变位词。时间复杂度为O(n)，空间复杂度为O(1)。2.题目：实现一个LRU（LeastRecentlyUsed）缓存，使用双向链表和哈希表实现，支持get和put操作。要求get和put的时间复杂度均为O(1)。答案：pythonclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=Node(0,0)self.tail=Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._remove(node)self._add(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self._remove(self.cache[key])node=Node(key,value)self.cache[key]=nodeself._add(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove(lru)delself.cache[lru.key]def_remove(self,node):delself.cache[node.key]node.prev.next=node.nextnode.next.prev=node.prevdef_add(self,node):node.next=self.head.nextnode.next.prev=nodeself.head.next=nodenode.prev=self.head解析：LRU缓存通过双向链表和哈希表实现。链表维护最近使用的顺序，哈希表实现O(1)的get和put操作。当缓存容量超出限制时，删除最久未使用的节点。3.题目：给定一个链表，判断链表是否存在环。如果存在环，返回进入环的第一个节点；否则返回None。答案：pythondefdetect_cycle(head):slow=fast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone解析：使用快慢指针判断链表是否存在环。如果快慢指针相遇，则链表存在环。通过移动慢指针到头节点，再次与快指针移动相同的步数，可以找到环的入口节点。4.题目：实现一个函数，将一个非负整数转换为罗马数字。例如，123->"CLXXIII"。答案：pythondefint_to_roman(num):val=[1000,900,500,400,100,90,50,40,10,9,5,4,1]syms=["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]roman_num=""i=0whilenum>0:for_inrange(num//val[i]):roman_num+=syms[i]num-=val[i]i+=1returnroman_num解析：通过罗马数字的符号和对应的数值进行匹配，从最大的数值开始匹配，逐步构建罗马数字表示。时间复杂度为O(1)。5.题目：给定一个数组，找出数组中第三大的数。如果数组中没有第三大的数，返回最大的数。例如，[1,2,-2147483648]->1。答案：pythondefthird_max(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:first,second,third=num,first,secondeliffirst>num>second:second,third=num,secondelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirst解析：通过维护三个变量first、second、third来记录当前最大的三个数。遍历数组时，更新这三个变量的值。如果third始终为初始值，则返回first。二、算法与设计（共5题，每题10分，总分50分）1.题目：美团外卖系统中，用户评价一个订单需要考虑评价的时效性。请设计一个算法，评价权重随时间衰减。例如，订单完成后1天内评价权重为1，之后每天权重衰减50%。答案：pythonimportmathdefevaluation_weight(order_completed_time,current_time):elapsed_days=(current_time-order_completed_time)/(243600)ifelapsed_days<=1:return1.0else:returnmath.exp(-0.693(elapsed_days-1))解析：使用指数衰减函数来计算评价权重。时间越长，权重衰减越快。初始权重为1，衰减率约为每天50%。2.题目：美团打车系统需要计算从起点到终点的最短路径。请设计一个算法，支持动态更新边的权重（例如，实时路况导致部分路段拥堵）。答案：pythonimportheapqclassEdge:def__init__(self,to,weight):self.to=toself.weight=weightclassGraph:def__init__(self):self.adj={}defadd_edge(self,from_node,to_node,weight):iffrom_nodenotinself.adj:self.adj[from_node]=[]self.adj[from_node].append(Edge(to_node,weight))defdijkstra(self,start):distances={node:float('inf')fornodeinself.adj}distances[start]=0pq=[(0,start)]whilepq:current_dist,current_node=heapq.heappop(pq)ifcurrent_dist>distances[current_node]:continueforedgeinself.adj[current_node]:new_dist=current_dist+edge.weightifnew_dist<distances[edge.to]:distances[edge.to]=new_distheapq.heappush(pq,(new_dist,edge.to))returndistancesdefupdate_edge(self,from_node,to_node,new_weight):foredgeinself.adj[from_node]:ifedge.to==to_node:edge.weight=new_weightbreak解析：使用Dijkstra算法计算最短路径，支持动态更新边的权重。通过维护优先队列（最小堆）来高效获取当前最短路径的节点，并在边权重更新时重新计算最短路径。3.题目：美团外卖配送路线优化问题：给定多个订单的起终点和预计送达时间，请设计一个算法，将订单分配给配送员，使得总配送时间最小。答案：pythonfromtypingimportListimportheapqclassOrder:def__init__(self,id,start,end,delivery_time):self.id=idself.start=startself.end=endself.delivery_time=delivery_timeclassDeliveryOptimizer:def__init__(self):self.orders=[]self.heap=[]defadd_order(self,order):self.orders.append(order)heapq.heappush(self.heap,(order.delivery_time,order))defoptimize_deliveries(self):deliveries=[]whileself.heap:_,order=heapq.heappop(self.heap)deliveries.append(order)returndeliveries示例用法optimizer=DeliveryOptimizer()optimizer.add_order(Order(1,(0,0),(1,1),30))optimizer.add_order(Order(2,(1,1),(2,2),45))optimizer.add_order(Order(3,(2,2),(3,3),25))deliveries=optimizer.optimize_deliveries()fordeliveryindeliveries:print(f"Order{delivery.id}:Start{delivery.start},End{delivery.end},DeliveryTime{delivery.delivery_time}")解析：通过优先队列（最小堆）按预计送达时间排序订单，依次分配给配送员。时间复杂度为O(nlogn)，适用于订单数量较多的情况。4.题目：美团点评系统需要推荐附近的热门商家，请设计一个算法，综合考虑商家的评分、销量、距离等因素。答案：pythonclassBusiness:def__init__(self,id,latitude,longitude,rating,sales):self.id=idself.latitude=latitudeself.longitude=longitudeself.rating=ratingself.sales=salesdefhaversine(lat1,lon1,lat2,lon2):R=6371#地球半径，单位kmphi1,phi2=math.radians(lat1),math.radians(lat2)delta_phi=math.radians(lat2-lat1)delta_lambda=math.radians(lon2-lon1)a=math.sin(delta_phi/2)2+math.cos(phi1)math.cos(phi2)math.sin(delta_lambda/2)2c=2math.atan2(math.sqrt(a),math.sqrt(1-a))returnRcdefrecommend_businesses(user_location,businesses):user_lat,user_lon=user_locationbusinesses_with_distance=[]forbusinessinbusinesses:distance=haversine(user_lat,user_lon,business.latitude,business.longitude)score=business.rating0.6+business.sales0.4-distance0.1businesses_with_distance.append((business,score))businesses_with_distance.sort(key=lambdax:x[1],reverse=True)return[businessforbusiness,_inbusinesses_with_distance]解析：综合考虑商家的评分、销量和距离，通过加权求和计算得分。距离越近、评分和销量越高，得分越高。使用Haversine公式计算地理距离。5.题目：美团共享单车调度系统：请设计一个算法，根据骑行热点区域和车辆分布，动态调整车辆调度策略，以平衡供需关系。答案：pythonclassBikeStation:def__init__(self,id,latitude,longitude,bikes):self.id=idself.latitude=latitudeself.longitude=longitudeself.bikes=bikesclassBikeScheduler:def__init__(self):self.stations=[]defadd_station(self,station):self.stations.append(station)defschedule_bikes(self):hotspots=self.detect_hotspots()forhotspotinhotspots:self.balance_bikes(hotspot)defdetect_hotspots(self):简单示例：假设热点区域为骑行次数最多的站点hotspot=max(self.stations,key=lambdax:x.bikes)return[hotspot]defbalance_bikes(self,hotspot):forstationinself.stations:ifstation!=hotspot:transfer=min(station.bikes,(hotspot.bikes//2))station.bikes-=transferhotspot.bikes+=transfer示例用法scheduler=BikeScheduler()scheduler.add_station(BikeStation(1,0,0,50))scheduler.add_station(BikeStation(2,1,1,10))scheduler.schedule_bikes()forstationinscheduler.stations:print(f"Station{station.id}:Bikes{station.bikes}")解析：通过检测骑行热点区域（假设为骑行次数最多的站点），将其他站点的车辆转移到热点区域，以平衡供需关系。实际应用中，热点区域可以通过用户骑行数据动态检测。三、系统设计（共5题，每题10分，总分50分）1.题目：设计一个美团外卖订单管理系统，支持高并发场景下的订单创建、查询和更新。答案：plaintext1.系统架构：-前端：用户界面（Web/App），负责订单提交和查询。-后端：订单服务，处理订单创建、查询和更新。使用无状态服务，支持水平扩展。-数据库：分布式数据库（如TiDB），支持高并发读写。-缓存：Redis，缓存热点订单数据，减少数据库压力。-消息队列：Kafka，异步处理订单相关事件（如配送、评价）。2.关键模块：-订单创建：-用户提交订单时，订单服务生成订单ID，写入数据库，并缓存订单数据。-通过消息队列通知配送服务、评价服务等。-订单查询：-先查询缓存，缓存无命中则查询数据库。-支持分页查询，缓存热点订单数据。-订单更新：-订单状态变更（如已支付、配送中、已完成）通过订单服务更新数据库和缓存。-通过消息队列通知相关服务。3.技术选型：-数据库：TiDB，支持分布式事务和高并发读写。-缓存：Redis，高并发读写，支持持久化。-消息队列：Kafka，高吞吐量，支持异步处理。-服务框架：SpringCloud，微服务架构，支持服务发现和负载均衡。解析：通过分布式数据库、缓存和消息队列实现高并发下的订单管理。订单服务无状态，支持水平扩展；缓存减少数据库压力；消息队列异步处理事件，提高系统吞吐量。2.题目：设计一个美团打车实时匹配系统，支持乘客和司机的实时匹配。答案：plaintext1.系统架构：-前端：乘客/司机App，负责位置上报和匹配请求。-后端：匹配服务，处理乘客和司机的匹配请求。-数据库：Redis，缓存乘客和司机信息。-地理位置服务：高德地图/百度地图，提供地理围栏和距离计算。2.关键模块：-乘客请求：-乘客提交打车请求，包含起终点、期望价格等信息。-匹配服务根据乘客位置和需求，查询附近司机。-司机请求：-司机提交接单请求，包含位置和期望价格等信息。-匹配服务根据司机位置和乘客需求，进行匹配。-实时匹配：-使用地理位置服务计算乘客和司机之间的距离。-根据距离、价格等因素进行匹配，通过App推送匹配结果。3.技术选型：-数据库：Redis，高并发读写，支持地理位置数据结构。-地理位置服务：高德地图/百度地图，提供地理围栏和距离计算。-消息队列：Kafka，异步处理匹配事件。-服务框架：SpringCloud，微服务架构，支持服务发现和负载均衡。解析：通过地理位置服务和实时匹配算法实现乘客和司机的实时匹配。使用Redis缓存乘客和司机信息，提高匹配效率；消息队列异步处理匹配事件，提高系统吞吐量。3.题目：设计一个美团点评商家评价系统，支持用户评价和商家回复。答案：plaintext1.系统架构：-前端：用户界面（Web/App），支持评价提交和商家回复。-后端：评价服务，处理评价提交和商家回复。-数据库：分布式数据库（如TiDB），支持高并发读写。-缓存：Redis，缓存热门评价数据，减少数据库压力。2.关键模块：-评价提交：-用户提交评价时，评价服务生成评价ID，写入数据库，并缓存评价数据。-支持文本、图片、视频等多种评价形式。-评价查询：-先查询缓存，缓存无命中则查询数据库。-支持分页查询，缓存热点评价数据。-商家回复：-商家回复评价时，评价服务更新数据库和缓存。-通过App推送商家回复给用户。3.技术选型：-数据库：TiDB，支持分布式事务和高并发读写。-缓存：Redis，高并发读写，支持持久化。-消息队列：Kafka，异步处理评价相关事件（如推送）。-服务框架：SpringCloud，微服务架构，支持服务发现和负载均衡。解析：通过分布式数据库和缓存实现高并发下的评价管理。评价服务无状态，支持水平扩展；缓存减少数据库压力；消息队列异步处理事件，提高系统吞吐量。4.题目：设计一个美团外卖配送员调度系统，支持动态订单分配和路径优化。答案：plaintext1.系统架构：-前端：配送员App，负责订单接收和路径导航。-