美团系统工程师面试经验与答案解析

2026年美团系统工程师面试经验与答案解析一、编程题（共3题，每题15分，总分45分）1.题目（15分）：编写一个函数，实现LRU（LeastRecentlyUsed）缓存机制。缓存容量为固定值，当缓存满时，需要淘汰最久未使用的元素。函数应支持添加和查询操作，并返回相关结果。要求：-使用Python或Java实现。-时间复杂度为O(1)。-提供代码实现，并说明时间复杂度分析。答案解析：（1）思路分析LRU缓存的核心是记录元素的访问顺序，当缓存满时淘汰最久未使用的元素。为达到O(1)时间复杂度，需要结合哈希表（记录key和node的映射）和双向链表（记录访问顺序）。-哈希表：快速定位元素，O(1)时间查找到对应链表节点。-双向链表：头部为最近使用，尾部为最久未使用，O(1)时间添加、删除节点。（2）代码实现（Python）pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}#key:Node(key,value)self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:iflen(self.cache)==self.capacity:tail=self.tail.prevdelself.cache[tail.key]self._remove_node(tail)new_node=self.Node(key,value)self.cache[key]=new_nodeself._add_node(new_node)def_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_node（3）时间复杂度分析-get：O(1)，通过哈希表查找到节点，再移动到头部。-put：O(1)，同样通过哈希表查找到节点（若存在），或直接添加新节点，并调整链表。-空间复杂度：O(capacity)，哈希表和链表总空间为capacity。2.题目（15分）：美团外卖系统中有大量订单数据，订单状态会随时间变化（如待支付、已支付、配送中、已完成等）。现需设计一个高效的数据结构，支持以下操作：-查询当前活跃订单数（状态为“配送中”或“已支付”）。-批量更新订单状态（如将所有“待支付”订单标记为“已支付”）。要求：-数据结构应支持高并发场景，考虑线程安全。-描述数据结构设计，并说明如何优化查询和更新性能。答案解析：（1）思路分析订单状态变化高频，需要支持高并发更新。核心思路是：-状态聚合：用枚举管理状态，减少字符串比较开销。-分表存储：将订单按状态分表（如“配送中”表、“已支付”表），查询时直接查对应表，更新时仅修改相关表。-锁机制：使用读写锁（RWLock）优化并发控制，读操作不阻塞，写操作互斥。（2）数据结构设计pythonfromenumimportEnumfromthreadingimportLockfromcollectionsimportdefaultdictclassOrderStatus(Enum):PENDING=1PAID=2DELIVERING=3COMPLETED=4classOrder:def__init__(self,order_id,status):self.order_id=order_idself.status=statusclassOrderSystem:def__init__(self):self.tables=defaultdict(set)#status:{order_id}self.lock=Lock()defadd_order(self,order:Order):self.tables[order.status].add(order.order_id)defupdate_order(self,order_id,new_status):withself.lock:iforder_idinself.tables[OrderStatus.PENDING]:self.tables[OrderStatus.PAID].add(order_id)self.tables[OrderStatus.PENDING].remove(order_id)其他状态更新类似...defget_active_orders(self):withself.lock:returnlen(self.tables[OrderStatus.DELIVERING]|self.tables[OrderStatus.PAID])（3）优化策略-分表存储：查询活跃订单时，直接并查“配送中”和“已支付”表，时间复杂度O(1)。-读写锁：读操作（如查询）不阻塞，写操作（如批量更新）互斥，提升并发性能。-延迟删除：订单完成时标记为“过期”，定时清理，避免表膨胀。3.题目（15分）：美团打车系统中有大量司机接单请求，请求按时间戳排序。现需设计一个算法，支持以下场景：-实时接单：司机接单后，系统需快速更新请求状态（如标记为“已接单”）。-请求重排：当有新司机加入时，需将未接单请求按优先级（如距离最近）重新排序。要求：-描述数据结构设计，并说明如何支持高并发和低延迟。-给出伪代码，并分析时间复杂度。答案解析：（1）思路分析-实时接单：使用最小堆（优先队列）管理未接单请求，司机接单时O(logN)时间从堆中删除请求。-请求重排：新司机加入时，将未接单请求按优先级重新入堆，O(NlogN)时间完成重排。-并发控制：使用乐观锁（CAS）或锁分段技术，避免高并发冲突。（2）数据结构设计pythonimportheapqclassRequest:def__init__(self,req_id,timestamp,distance):self.req_id=req_idself.timestamp=timestampself.distance=distance#优先级用距离反比classDispatcher:def__init__(self):self.unassigned_requests=[]#最小堆（按distance升序）self.lock=Lock()defadd_request(self,request:Request):withself.lock:heapq.heappush(self.unassigned_requests,(request.distance,request))deftake_request(self,driver_id,req_id):withself.lock:快速定位并删除请求fori,(_,req)inenumerate(self.unassigned_requests):ifreq.req_id==req_id:delself.unassigned_requests[i]breakdefreassign_requests(self,new_driver_id):withself.lock:重新排序未接单请求sorted_requests=sorted(self.unassigned_requests,key=lambdax:x[1].distance)self.unassigned_requests=[reqfor_,reqinsorted_requests]（3）时间复杂度分析-add_request：O(logN)，堆插入操作。-take_request：O(N)，需遍历堆查找请求。-reassign_requests：O(NlogN)，重新排序操作。优化方案：-批量删除：用跳表替代堆，支持O(logN)删除。-异步更新：用Redis事务批量处理请求状态变更，降低锁竞争。二、系统设计题（共2题，每题25分，总分50分）1.题目（25分）：美团外卖系统需要支持亿级用户实时查询附近骑手位置，骑手位置每秒更新。设计一个高并发的实时定位服务，要求：-低延迟：骑手位置更新和查询响应时间均小于100ms。-高并发：支持百万级骑手和千万级查询请求。-容错性：部分节点故障不影响服务。说明：-描述系统架构，并说明如何实现位置索引和热点区域优化。答案解析：（1）系统架构设计-数据层：-分布式缓存（RedisCluster）：存储骑手位置，使用GeoHash分桶，支持快速范围查询。-持久化存储（MySQLCluster）：记录历史位置，用于离线分析和热力图生成。-计算层：-热点区域检测：用布隆过滤器+计数器识别高密度区域，动态调整缓存分片。-实时计算（Flink）：处理位置流，计算骑手轨迹和预计到达时间（ETA）。-接入层：-负载均衡（Nginx+LVS）：分发请求到不同节点，支持横向扩展。-请求限流：熔断器+滑动窗口限流，防止过载。（2）位置索引设计-GeoHash：将经纬度转换为固定长度的字符串（如“121.345,31.678”→“geohash”），支持矩形范围查询。-空间索引：Redis支持`GEOADD`和`GEORADIUS`，快速查询附近骑手。（3）热点区域优化-动态分片：高密度区域（如商圈）单独分片，降低缓存碰撞。-预加载：提前加载热点区域骑手数据，避免查询时阻塞。2.题目（25分）：美团点评App中有大量用户评价数据，评价包含文本、图片、星级评分等。设计一个高可用的评价存储系统，要求：-数据一致性：用户提交评价后，需保证数据最终一致性。-高可用：单点故障不影响服务。-扩展性：支持评价数据量线性扩展。说明：-描述系统架构，并说明如何实现数据备份和容灾。答案解析：（1）系统架构设计-接入层：-Kafka：异步接收评价请求，削峰填谷。-API网关（Kong）：路由请求到不同服务，支持灰度发布。-数据层：-分布式数据库（TiDB/CockroachDB）：支持SQL+NoSQL混合，自动分片。-对象存储（OSS）：存储评价图片，CDN加速访问。-备份层：-时间序列存储（InfluxDB）：记录评价变更日志，支持回滚。-异地多活（多地域副本）：华东、华南、北美三地部署，数据自动同步。（2）数据备份与容灾-多副本写入：数据库默认3副本，某节点故障自动切换。-日志备份：Kafka日志定期备份到S3，防止数据丢失。-故障切换：用DNS健康检查+自动切换，切换时间<30s。（3）扩展性方案-水平分片：按评价ID哈希分片，支持数据量线性增长。-动态扩容：监控CPU/内存使用率，自动增加数据库节点。三、综合题（共1题，25分）题目（25分）：美团闪购系统中有大量商品优惠券，优惠券有类型（满减、折扣券）、有效期、适用范围（指定商品/品类）等属性。设计一个优惠券秒杀系统，要求：-高并发：支持百万级用户同时抢购。-防超卖：避免同一优惠券被重复领取。-低延迟：秒杀过程响应时间小于50ms。说明：-描述核心流程，并说明如何实现防超卖和锁机制。答案解析：（1）核心流程设计1.请求预处理：用户请求先入Redis队列，按请求ID排序，避免重复处理。2.库存锁定：用Redis事务扣减优惠券库存，成功则扣减，失败则放回。3.优惠券发放：锁定成功后，生成优惠券并存储到数据库。4.回调通知：秒杀结果通过WebSocket实时推送给用户。（2）防超卖