2026年滴出行技术面试题及解析

2026年滴出行技术面试题及解析一、编程题（共3题，每题20分，总分60分）1.题目（20分）：实现一个函数，输入一个字符串，输出该字符串中所有单词的倒序排列。例如，输入`"helloworld"`，输出`"ollehdlrow"`。要求使用Python语言，考虑字符串中可能包含空格和标点符号，忽略标点符号和空格的顺序。pythondefreverse_words(s:str)->str:你的代码pass2.题目（20分）：设计一个简单的LRU（LeastRecentlyUsed）缓存结构，支持以下操作：-`LRUCache(intcapacity)`：初始化缓存容量为`capacity`。-`get(intkey)`：如果缓存中存在键`key`，则返回其值，并更新该键为最近使用；否则返回`-1`。-`put(intkey,intvalue)`：如果缓存已满，先删除最久未使用的键，再插入新的键值对。要求使用Python实现，时间复杂度为`O(1)`。3.题目（20分）：编写一个函数，输入一个整数数组，返回该数组的中位数。例如，输入`[3,1,2,4,5]`，输出`3`；输入`[1,2]`，输出`1.5`。要求不使用排序，时间复杂度为`O(n)`。二、系统设计题（共2题，每题20分，总分40分）1.题目（20分）：设计一个高并发的订单支付系统，要求支持每秒处理10万笔订单。系统需满足以下需求：-订单支付需保证原子性，防止超卖。-支持异步通知回调，确保支付成功后能及时通知客户端。-考虑系统容灾和扩展性，简述如何设计高可用架构。2.题目（20分）：设计一个实时路况信息推送系统，覆盖全国主要城市。系统需满足以下要求：-数据来源包括GPS车辆上报、第三方数据提供商等，需保证数据实时性和准确性。-推送给用户时需根据用户位置动态筛选最近的路况信息。-简述如何设计数据存储和计算架构，以及如何应对高并发场景。三、数据库题（共2题，每题20分，总分40分）1.题目（20分）：假设滴出行使用MySQL存储订单数据，表结构如下：sqlCREATETABLEorders(idBIGINTAUTO_INCREMENTPRIMARYKEY,user_idBIGINTNOTNULL,car_idBIGINTNOTNULL,order_timeDATETIMENOTNULL,statusENUM('pending','paid','cancelled')NOTNULL,FOREIGNKEY(user_id)REFERENCESusers(id),FOREIGNKEY(car_id)REFERENCEScars(id));写一条SQL查询，统计每个用户的订单状态分布（例如，已支付订单数、待支付订单数等），并按用户ID升序排列。2.题目（20分）：解释MySQL中的事务隔离级别（读未提交、读已提交、可重复读、串行化），并说明在订单支付场景下应选择哪种隔离级别及其原因。四、算法题（共2题，每题20分，总分40分）1.题目（20分）：给定一个二维地图，`1`表示可通行区域，`0`表示障碍物。求从左上角`(0,0)`到右下角`(m-1,n-1)`的最短路径长度（只能上下左右移动）。例如：pythongrid=[[1,0,1,1],[1,1,0,1],[1,1,1,0]]输出：7要求使用BFS算法实现。2.题目（20分）：实现一个LRU缓存的数据结构，支持`get(key)`和`put(key,value)`操作，并保证时间复杂度为`O(1)`。要求使用双向链表和哈希表结合实现。答案及解析一、编程题1.答案：pythondefreverse_words(s:str)->str:words=s.split()reversed_words=[word[::-1]forwordinwords]return''.join(reversed_words)解析：-首先通过`split()`分割字符串为单词列表，忽略标点符号和空格。-对每个单词进行反转（`word[::-1]`），然后重新拼接为字符串。-时间复杂度`O(n)`，空间复杂度`O(n)`。2.答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest_key=self.order.pop(0)delself.cache[oldest_key]self.cache[key]=valueself.order.append(key)解析：-使用哈希表`cache`存储键值对，`order`列表记录访问顺序。-`get`操作时，若键存在则移动到列表末尾表示最近使用。-`put`操作时，若键已存在则更新值并移动到末尾；若缓存已满，则删除最久未使用的键。-时间复杂度`O(1)`。3.答案：pythondeffind_median(nums:List[int])->float: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)n=len(nums)ifn%2==1:returnselect(0,n-1,n//2)else:left=select(0,n-1,n//2-1)right=select(0,n-1,n//2)return(left+right)/2.0解析：-使用快速选择算法（Quickselect）在`O(n)`时间内找到第`k`小元素。-首先随机选择枢轴（pivot）并分区，然后递归处理左侧或右侧。-对于偶数长度数组，取中间两个数的平均值。二、系统设计题1.答案：核心组件：-订单存储：使用分布式数据库（如TiDB）存储订单数据，支持高并发写入和事务隔离。-支付网关：对接支付宝、微信支付等第三方支付平台，通过异步消息队列（如Kafka）处理支付回调。-事务保证：使用分布式事务框架（如Seata）或2PC协议保证支付与订单状态的原子性。-缓存层：使用Redis缓存热点订单数据，减少数据库压力。-监控告警：通过Prometheus+Grafana监控系统状态，设置超卖告警。高可用设计：-负载均衡（Nginx+HAProxy）分发请求，使用多副本存储防数据丢失。-异步消息队列解耦支付与订单服务，提高容错性。2.答案：核心组件：-数据采集层：接入车辆GPS数据、第三方地图数据（如高德地图），使用Flink实时计算处理数据。-数据存储：使用Elasticsearch存储实时路况数据，支持快速查询。-计算层：使用Grafana+Prometheus动态聚合路况信息，根据用户位置推送最近数据。-推送服务：通过WebSocket或长轮询推送实时路况给客户端。高并发设计：-使用分布式缓存（Redis）存储用户位置与路况映射关系。-数据分片（如按城市分片）降低单节点负载。三、数据库题1.答案：sqlSELECTuser_id,SUM(CASEWHENstatus='paid'THEN1ELSE0END)ASpaid_count,SUM(CASEWHENstatus='pending'THEN1ELSE0END)ASpending_count,SUM(CASEWHENstatus='cancelled'THEN1ELSE0END)AScancelled_countFROMordersGROUPBYuser_idORDERBYuser_idASC;解析：-使用`CASEWHEN`条件聚合统计各状态订单数。-`GROUPBYuser_id`按用户分组，`ORDERBY`排序。2.答案：-读未提交：可能读到未提交事务的数据（脏读），适用于读多写少场景。-读已提交：防止脏读，但可能读到已提交但未同步的数据（不可重复读）。-可重复读：锁定记录防止不可重复读，但可能读到幻读（MVCC）。-串行化：完全锁定数据，保证隔离性最高，但性能最低。订单支付场景：选择可重复读，防止因并发支付导致订单状态不一致，同时避免串行化带来的性能问题。四、算法题1.答案：pythonfromcollectionsimportdequedefshortest_path(grid):m,n=len(grid),len(grid[0])queue=deque([(0,0,0)])#(x,y,steps)visited=set([(0,0)])whilequeue:x,y,steps=queue.popleft()ifx==m-1andy==n-1:returnstepsfordx,dyin[(0,1),(1,0),(0,-1),(-1,0)]:nx,ny=x+dx,y+dyif0<=nx<mand0<=ny<nandgrid[nx][ny]==1and(nx,ny)notinvisited:visited.add((nx,ny))queue.append((nx,ny,steps+1))return-1解析：-使用BFS遍历，队列存储当前节点及步数。-标记已访问节点，避免重复遍历。2.答案：pythonclassLRUCache: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.headclassNode:def__init__(self,key,value):self.key=keyself.value=valueself.prev=Noneself.next=Nonedefget(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])eliflen(self.cache)>=self.capacity:self._remove(self.tail.prev)node=self.Node(key,value)self.cache[key]=nodeself._add(node)def_rem