滴出行技术部面试题及答案详解

2026年滴出行技术部面试题及答案详解一、编程语言与数据结构（共5题，每题10分，总分50分）题目1（Python编程题，10分）：编写一个Python函数，实现以下功能：给定一个字符串`s`，统计其中所有单词的出现频率，并按出现频率从高到低排序输出。假设单词以空格分隔，忽略大小写和标点符号。示例输入：`"Helloworld!Hello,howareyou?I'mfine,thankyou!"`示例输出：`{'hello':3,'you':2,'i':1,'am':1,'fine':1,'thank':1,'how':1,'are':1,'world':1}`答案：pythonimportrefromcollectionsimportCounterdefword_frequency(s):去除标点符号并转换为小写words=re.findall(r'\b\w+\b',s.lower())统计频率freq=Counter(words)按频率排序sorted_freq=dict(sorted(freq.items(),key=lambdax:x[1],reverse=True))returnsorted_freq测试s="Helloworld!Hello,howareyou?I'mfine,thankyou!"print(word_frequency(s))解析：1.使用正则表达式`re.findall(r'\b\w+\b',s.lower())`提取所有单词，并转换为小写以忽略大小写差异。2.利用`collections.Counter`统计单词频率。3.使用`sorted`函数按频率降序排序，并转换为字典输出。题目2（Java编程题，10分）：实现一个Java方法，判断一个整数是否为“完全平方数”。即该整数是否可以表示为某个整数的平方。示例输入：`16`示例输出：`true`答案：javapublicclassPerfectSquare{publicstaticbooleanisPerfectSquare(intnum){if(num<0)returnfalse;intleft=0,right=num;while(left<=right){intmid=left+(right-left)/2;longsquare=(long)midmid;if(square==num)returntrue;if(square<num)left=mid+1;elseright=mid-1;}returnfalse;}publicstaticvoidmain(String[]args){System.out.println(isPerfectSquare(16));//trueSystem.out.println(isPerfectSquare(14));//false}}解析：1.使用二分查找法判断，时间复杂度为O(logn)。2.避免整数溢出，将`mid`转换为`long`类型计算平方。3.若平方等于目标数，返回`true`；否则调整搜索范围。题目3（C++编程题，10分）：编写一个C++函数，实现快速排序算法。输入一个整数数组，返回排序后的数组。示例输入：`[3,1,4,1,5,9,2,6,5,3]`示例输出：`[1,1,2,3,3,4,5,5,6,9]`答案：cppinclude<vector>include<iostream>usingnamespacestd;voidquickSort(vector<int>&arr,intleft,intright){if(left>=right)return;intpivot=arr[(left+right)/2];inti=left,j=right;while(i<=j){while(arr[i]<pivot)i++;while(arr[j]>pivot)j--;if(i<=j){swap(arr[i],arr[j]);i++;j--;}}quickSort(arr,left,j);quickSort(arr,i,right);}intmain(){vector<int>arr={3,1,4,1,5,9,2,6,5,3};quickSort(arr,0,arr.size()-1);for(intnum:arr)cout<<num<<"";return0;}解析：1.快速排序采用分治策略，选择中间值作为基准（pivot）。2.双指针从左右向中间遍历，交换不满足条件的元素。3.递归对左右子数组进行排序。题目4（JavaScript编程题，10分）：实现一个JavaScript函数，将一个字符串转换为大写首字母加其余小写的格式（即“camelCase”）。示例输入：`"helloworld"`示例输出：`"HelloWorld"`答案：javascriptfunctiontoCamelCase(str){returnstr.split('').map((word,index)=>index===0?word.toLowerCase():word.charAt(0).toUpperCase()+word.slice(1).toLowerCase()).join('');}//测试console.log(toCamelCase("helloworld"));//HelloWorld解析：1.将字符串按空格分割成单词数组。2.第一个单词全部小写，其余单词首字母大写、其余小写。3.使用`map`和`join`组合结果。题目5（数据结构题，10分）：设计一个LRU（LeastRecentlyUsed）缓存结构，支持`get`和`put`操作。使用哈希表+双向链表实现。示例输入：plaintextput(1,1)→缓存是{1:1}put(2,2)→缓存是{1:1,2:2}get(1)→返回1put(3,3)→去除键2，缓存是{1:1,3:3}get(2)→返回-1(未找到)put(4,4)→去除键1，缓存是{4:4,3:3}get(1)→返回-1(未找到)get(3)→返回3get(4)→返回4答案：pythonclassDLinkedNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head,self.tail=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdef_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_nodedef_move_to_head(self,node):移动到头部self._remove_node(node)self._add_node(node)def_pop_tail(self):弹出尾部节点res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:newNode=DLinkedNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:node.value=valueself._move_to_head(node)测试cache=LRUCache(2)cache.put(1,1)cache.put(2,2)print(cache.get(1))#1cache.put(3,3)#去除2print(cache.get(2))#-1cache.put(4,4)#去除1print(cache.get(1))#-1print(cache.get(3))#3print(cache.get(4))#4解析：1.使用双向链表维护访问顺序，头部为最近访问，尾部为最久未访问。2.哈希表`cache`记录键到节点的映射，实现O(1)访问。3.`get`操作将节点移至头部，`put`操作先判断是否存在：-存在则更新值并移动至头部；-不存在则新建节点并添加至头部，若超出容量则删除尾部节点。二、系统设计与架构（共4题，每题15分，总分60分）题目6（分布式系统设计，15分）：设计一个支持高并发的短链接服务（如`/abc`）。要求：1.用户访问短链接时，能快速解析为原始长链接。2.支持分布式部署，可水平扩展。3.需考虑短链接唯一性、安全性（防止恶意跳转）。答案：1.短链接生成：-使用随机算法生成6位短码（如`a-z`、`A-Z`、`0-9`），确保唯一性。-哈希函数：`hash=md5(长链接+随机种子)`，取前6位作为短码。2.分布式存储：-使用Redis或Memcached缓存短码到长链接的映射，设置过期时间（如24小时）。-若缓存未命中，查询数据库（分片存储，按短码哈希值分配）。3.安全性：-增加校验码（如`/abc?token=xyz`），验证请求合法性。-限制短链接有效期，防止长期跳转风险。4.高并发优化：-使用负载均衡（如Nginx）分发请求到多个服务节点。-数据库读写分离，分片键为短码哈希值。题目7（数据库设计，15分）：设计一个支持实时路况查询的数据库表结构，包含以下字段：1.`location_id`（地点ID，唯一），2.`timestamp`（时间戳），3.`traffic_flow`（车流量，每分钟计数），4.`speed_limit`（限速），5.`current_speed`（实时速度）。要求：-支持按地点和时间范围查询。-优化查询性能，例如车流量统计。答案：sqlCREATETABLETrafficData(location_idINTPRIMARYKEY,timestampDATETIMENOTNULL,traffic_flowINTDEFAULT0,speed_limitINTNOTNULL,current_speedDECIMAL(5,2)NOTNULL);--索引优化CREATEINDEXidx_location_timestampONTrafficData(location_id,timestamp);优化策略：1.分区表：按地点ID分片，每个地点独立存储，避免全表扫描。2.车流量统计：-使用物化视图按`location_id`和`timestamp`分组统计每分钟车流量。-查询时先计算时间差，再聚合流量。3.实时速度更新：-使用Redis缓存热点地点的`current_speed`，减少数据库压力。题目8（消息队列设计，15分）：设计一个订单处理系统，使用Kafka或RabbitMQ实现异步化处理。要求：1.订单创建后，需通知库存、支付、风控等系统。2.若某系统处理失败，需重试或补偿。答案：1.架构：-订单服务发布消息到Kafka主题`order_topic`。-各系统订阅对应分区，例如：-库存系统订阅`stock_partition`，扣减库存。-支付系统订阅`payment_partition`，处理支付流水。2.可靠性：-Kafka保证消息至少传递一次，使用`acks=all`。-各消费者独立记录处理状态，失败时重新入队重试（最多3次）。3.补偿机制：-若库存扣减失败，使用死信队列（DLQ）记录订单，触发人工补偿。-支付失败则重新发起支付请求。题目9（高并发场景设计，15分）：设计一个秒杀活动系统，支持百万级用户同时抢购。要求：1.防止超卖、秒杀接口被刷。2.限流策略（如每秒1000人）。答案：1.防超卖：-使用Redis分布式锁，每个用户抢购时加锁，锁过期后释放。-库存先减后判断，若不足则释放锁并返回失败。2.限流：-Nginx配置IP限流（如每秒1000请求）。-滑动窗口算法（如每5分钟统计流量，动态调整限速阈值）。3.热点优化：-将库存预加载到内存，减少数据库查询。-使用消息队列异步释放锁，避免用户卡顿。三、算法与数据结构（共5题，每题10分，总分50分）题目10（字符串算法，10分）：给定两个字符串`s1`和`s2`，判断`s2`是否为`s1`的“交错字符串”，即`s2`由`s1`的字符重新排列组合而成。示例输入：`s1="aabcc"`,`s2="dbbca"`示例输出：`true`答案：pythondefisInterleave(s1:str,s2:str)->bool:m,n=len(s1),len(s2)ifm+n==0:returnTruedp=[[False](n+1)for_inrange(m+1)]dp[0][0]=Trueforiinrange(1,m+1):dp[i][0]=dp[i-1][0]ands1[i-1]==s2[0]forjinrange(1,n+1):dp[0][j]=dp[0][j-1]ands2[j-1]==s1[0]foriinrange(1,m+1):forjinrange(1,n+1):dp[i][j]=(dp[i-1][j]ands1[i-1]==s2[j-1])or\(dp[i][j-1]ands2[j-1]==s1[i-1])returndp[m][n]解析：1.动态规划（DP）数组`dp[i][j]`表示`s1[:i]`和`s2[:j]`是否交错。2.初始化边界条件：`dp[0][0]=True`，`dp[i][0]`检查`s1`前缀是否匹配`s2[0]`。3.状态转移：当前字符匹配`s1[i-1]`或`s2[j-1]`，取两者之一为真。题目11（树算法，10分）：给定二叉树，判断其是否为平衡二叉树（左右子树高度差不超过1）。示例输入：3/\920/\157示例输出：`true`答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefisBalanced(root:TreeNode)->bool:defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)balanced=(left_balancedandright_balancedandabs(left_height-right_height)<=1)returnmax(left_height,right_height)+1,balancedreturncheck(root)[1]解析：1.递归计算左右子树高度，同时判断平衡性。2.若左右子树均平衡且高度差≤1，则当前树平衡。3.时间复杂度O(n)，每个节点只访问一次。题目12（贪心算法，10分）：给定一个非负数组`nums`，返回一个最小的正数，使得`nums`的所有子数组之和都不小于该正数。示例输入：`[3,-1,2,-1]`示例输出：`3`答案：pythondefminSumSubarray(nums):n=len(nums)min_prefix=0result=float('inf')foriinrange(n):min_prefix=min(min_prefix+nums[i],nums[i])result=min(result,min_prefix)return-result+1ifresult!=float('inf')else1测试print(minSumSubarray([3,-1,2,-1]))#3解析：1.贪心策略：维护当前最小前缀和`min_prefix`，若为负则重置为当前元素。2.子数组最小和为`min_prefix`，取所有`min_prefix`的最小值。3.最终答案为`-min_prefix+1`。题目13（图算法，10分）：给定一个无向图，判断其是否为二分图（可分成两个集合，相邻节点不同色）。示例输入：节点1-2,1-3,2-4,3-4示例输出：`true`答案：pythondefisBipartite(graph):color={}fornodeingraph:ifnodenotincolor:stack=[node]color[node]=0whilestack:current=stack.pop()forneighboringraph[