美团技术部主管面试问题集

2026年美团技术部主管面试问题集一、编程能力与算法设计（共5题，每题10分）1.问题：给定一个包含重复元素的整数数组，返回所有不重复的全排列。要求：不允许使用递归，时间复杂度尽可能低。答案与解析：pythondefpermute_unique(nums):result=[]nums.sort()#排序以处理重复元素path,used=[],[False]len(nums)defbacktrack():iflen(path)==len(nums):result.append(path.copy())returnforiinrange(len(nums)):ifused[i]or(i>0andnums[i]==nums[i-1]andnotused[i-1]):continueused[i]=Truepath.append(nums[i])backtrack()path.pop()used[i]=Falsebacktrack()returnresult解析：-排序处理重复：通过排序，相同的数字会相邻，便于跳过重复排列。-used数组：记录每个数字是否被使用。-剪枝条件：若当前数字与前一个数字相同且前一个数字未被使用，则跳过，避免重复排列。-时间复杂度：O(N!N)，其中N为数字数量。2.问题：设计一个LRU（LeastRecentlyUsed）缓存，支持get和put操作，容量为capacity。要求：get操作返回值在O(1)时间内完成，put操作在O(1)时间内完成。答案与解析：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()defget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)#更新最近使用returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)#移除最久未使用项解析：-OrderedDict：记录键值对的同时维护插入顺序，move_to_end实现O(1)时间更新顺序。-get操作：若存在则移动到末尾，返回值。-put操作：若存在则更新，否则添加；超出容量时移除最久未使用项。3.问题：给定一个字符串s，找到其中最长的回文子串。要求：时间复杂度O(N^2)，空间复杂度O(N)。答案与解析：pythondeflongest_palindrome(s:str)->str:ifnots:return""start,end=0,0n=len(s)dp=[[False]nfor_inrange(n)]foriinrange(n):dp[i][i]=Trueifi<n-1ands[i]==s[i+1]:dp[i][i+1]=Truestart,end=i,i+1forlengthinrange(3,n+1):foriinrange(n-length+1):j=i+length-1ifs[i]==s[j]anddp[i+1][j-1]:dp[i][j]=Truestart,end=i,jreturns[start:end+1]解析：-动态规划：dp[i][j]表示s[i..j]是否为回文。-初始化：单个字符和相邻字符相同的情况。-状态转移：若s[i]==s[j]且dp[i+1][j-1]为真，则dp[i][j]为真。-时间复杂度：O(N^2)，空间复杂度：O(N^2)，可优化至O(N^2)空间。4.问题：实现一个函数，判断二叉树是否为平衡二叉树（左右子树高度差不超过1）。要求：时间复杂度O(N)。答案与解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root:TreeNode)->bool:defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]解析：-后序遍历：先计算左右子树高度，再判断平衡。-返回值：高度和是否平衡的布尔值。-时间复杂度：O(N)，每个节点访问一次。5.问题：设计一个算法，找出数组中第K大的元素。要求：不排序，时间复杂度O(N)。答案与解析：pythondeffind_kth_largest(nums,k):defpartition(left,right,pivot_index):pivot=nums[pivot_index]nums[pivot_index],nums[right]=nums[right],nums[pivot_index]store_index=leftforiinrange(left,right):ifnums[i]>pivot:nums[store_index],nums[i]=nums[i],nums[store_index]store_index+=1nums[right],nums[store_index]=nums[store_index],nums[right]returnstore_indexdefselect(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=random.randint(left,right)pivot_index=partition(left,right,pivot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnselect(left,pivot_index-1,k_smallest)else:returnselect(pivot_index+1,right,k_smallest)returnselect(0,len(nums)-1,len(nums)-k)解析：-快速选择算法：基于快速排序的分区思想，但仅递归处理包含第K大的部分。-随机化：选择随机枢轴降低最坏情况时间复杂度。-时间复杂度：平均O(N)，最坏O(N^2)。二、系统设计（共3题，每题15分）1.问题：设计一个高并发的短链接生成系统。要求：-支持秒级生成短链接，如/abc123。-支持分布式部署，避免冲突。-带有简单的访问统计功能。答案与解析：系统架构：1.短链接生成服务：-使用自增ID或Snowflake算法生成唯一ID。-ID映射为62进制短码（a-z,A-Z,0-9），如`id_to_base62`函数。-分布式部署时，使用Redis或ZooKeeper生成全局唯一ID。2.存储层：-关联短链接与原链接，使用Redis缓存热点数据。-数据库（如MySQL）持久化存储。3.访问统计：-每次访问时，Redis计数器累加。-定时同步到数据库。4.负载均衡：-Nginx分发请求到不同服务实例。5.防冲突设计：-使用分布式锁或原子操作生成ID。代码示例（ID生成）：pythonimportrandomimportstringdefid_to_base62(num):chars=string.ascii_letters+string.digitsbase=len(chars)result=""whilenum:result=chars[num%base]+resultnum//=basereturnresultor"0"defgenerate_unique_id():使用Snowflake算法生成IDtimestamp=int(time.time()1000)worker_id=random.randint(1,1023)sequence=random.randint(0,4095)return(timestamp<<22)|(worker_id<<12)|sequence2.问题：设计一个美团外卖骑手分配系统。要求：-实时分配订单给最近的骑手，考虑路况。-支持骑手手动优化分配结果。-带有超时未分配报警功能。答案与解析：系统架构：1.实时订单流：-接收新订单，包含起终点坐标、预计送达时间。-使用WebSocket或MQ（如Kafka）推送订单到调度中心。2.调度中心：-使用Greedy算法或Dijkstra算法匹配最近骑手。-地图服务（如高德地图API）计算骑行距离和预估时间。3.骑手端：-实时更新骑手位置，使用WebSocket同步。-允许骑手手动确认或拒绝订单。4.超时报警：-订单分配超时后，短信或邮件通知调度员。5.监控与优化：-统计分配效率，动态调整算法参数。代码示例（骑手匹配）：pythonfromtypingimportList,Tupleimportmathdeffind_nearest_rider(order_coord:Tuple[int,int],riders:List[Tuple[int,int,float]]):min_distance=float('inf')nearest_rider=Noneforriderinriders:rider_coord,idle_time=rider[:2],rider[2]ifidle_time>0andidle_time<5:#仅选择空闲5分钟内的骑手distance=math.sqrt((order_coord[0]-rider_coord[0])2+(order_coord[1]-rider_coord[1])2)ifdistance<min_distance:min_distance=distancenearest_rider=riderreturnnearest_rider3.问题：设计一个美团打车计费系统。要求：-支持起步价、里程费、时间费。-考虑拥堵系数动态调整费用。-支持空驶费和奖励费。答案与解析：计费规则：1.起步价：如3元（含3公里）。2.里程费：超出起步里程后，每公里0.5元。3.时间费：每分钟0.2元，拥堵时翻倍。4.空驶费：等待超过10分钟，每分钟加收0.5元。5.奖励费：绕路超10%里程，额外加收起步价50%。代码示例（计费计算）：pythondefcalculate_fare(distance:float,duration:int,is_congested:bool)->float:base_fare=3.0start_distance=3.0per_km_fare=0.5per_minute_fare=0.2ifnotis_congestedelse0.4empty_fare_rate=0.5reward_threshold=0.1#绕路10%ifdistance<=start_distance:returnbase_fareelse:extra_distance=distance-start_distancecongestion_multiplier=2ifis_congestedelse1fare=base_fare+extra_distanceper_km_farecongestion_multiplierfare+=durationper_minute_farecongestion_multiplierifduration>10:fare+=(duration-10)empty_fare_ratereturnfare三、数据库与存储（共4题，每题12分）1.问题：美团外卖订单数据量巨大，如何设计订单表的索引优化查询？答案与解析：-索引字段：-主键：订单ID（自增或UUID）。-覆盖索引：`(骑手ID,订单状态,创建时间)`，用于快速查询骑手待接单列表。-组合索引：`(用户ID,订单状态,创建时间)`，用于查找用户历史订单。-分区设计：-按时间分区（每日），便于DDL操作和备份。-按骑手ID分区，优化分配查询。-缓存策略：-Redis缓存热门订单（如30分钟内未取的订单）。2.问题：设计一个高并发的订单状态更新方案，支持骑手、用户、系统多端修改。答案与解析：-最终一致性：-订单状态变更先写入Redis（毫秒级），再异步同步到MySQL。-使用消息队列（如RocketMQ）确保一致性。-锁机制：-分布式锁（Redis或ZooKeeper）防止并发冲突。-幂等设计：-请求参数校验，避免重复操作。3.问题：如何优化美团外卖的实时库存扣减？答案与商家端：-本地库存扣减：商家系统先减库存，成功后再调用骑手端API。-分布式事务：-使用2PC或TCC模式，确保库存与订单一致。-超卖处理：-若库存不足，骑手端回滚订单，并通知用户重新下单。4.问题：设计一个高可用、高扩展的存储方案，存储用户画像数据。答案与解析：-多级存储：-热数据存Redis，冷数据存HBase或Ceph。-数据分片：-按用户ID哈希分片，避免单点压力。-读写分离：-读请求转发到从库，写请求主库处理。四、分布式与中间件（共4题，每题12分）1.问题：设计一个美团点评的实时推荐系统，要求毫秒级响应。答案与解析：-架构：-用户行为数据流入ES或HBase，实时计算用户画像。-推荐结果存Redis，前端请求直接命中缓存。-算法：-协同过滤+深度学习混合模型，冷启动用热门商品填充。-容灾设计：-推荐服务部署多副本，使用DNS轮询或负载均衡。2.问题：美团点评如何处理海量用户评论数据的实时审核？答案与解析：-流程：-用户提交评论后，先通过机器审核（关键词过滤）。-机器判定为敏感词时，人工审核介入。-技术：-NLP模型识别违规内容（如涉政、色情）。-使用消息队列分发审核任务，人工审核系