2026年滴出行技术面试题目与解答

2026年滴出行技术面试题目与解答一、编程语言基础（3题，每题10分，共30分）题目1：用Python实现一个函数，接收一个字符串作为输入，返回该字符串中所有唯一字符的列表（即出现一次的字符）。假设输入字符串仅包含小写字母，且长度不超过1000。解答1：pythondefunique_chars(s):char_count={}forcharins:ifcharinchar_count:char_count[char]+=1else:char_count[char]=1return[charforchar,countinchar_count.items()ifcount==1]解析：1.使用字典`char_count`统计每个字符的出现次数。2.遍历字符串，若字符已存在于字典中，则计数加1；否则初始化为1。3.最终通过列表推导式筛选出现次数为1的字符并返回。4.时间复杂度为O(n)，空间复杂度为O(1)（假设字符集固定为小写字母）。题目2：用Java实现一个方法，接收一个整数数组，返回该数组的中位数。假设数组长度为奇数。解答2：javaimportjava.util.Arrays;publicstaticdoublefindMedian(int[]arr){Arrays.sort(arr);intn=arr.length;return(double)arr[n/2];}解析：1.使用`Arrays.sort`对数组进行排序，时间复杂度为O(nlogn)。2.中位数为排序后位于中间位置的元素（索引为`n/2`）。3.返回中位数时转换为`double`类型以支持浮点数。题目3：用C++实现一个函数，接收一个字符串，返回该字符串的KMP（Knuth-Morris-Pratt）前缀表。解答3：cppinclude<vector>include<string>std::vector<int>kmpPrefixTable(conststd::string&pattern){intn=pattern.length();std::vector<int>lps(n,0);intlength=0;for(inti=1;i<n;++i){while(length>0&&pattern[i]!=pattern[length]){length=lps[length-1];}if(pattern[i]==pattern[length]){length++;lps[i]=length;}else{lps[i]=0;}}returnlps;}解析：1.初始化前缀表`lps`，长度为0。2.遍历模式串，若当前字符与前缀不匹配，则移动前缀长度至`lps[length-1]`。3.匹配成功则前缀长度加1，记录至`lps[i]`。4.最终返回前缀表，用于KMP算法的匹配过程。二、数据结构与算法（5题，每题12分，共60分）题目4：设计一个无重复元素的集合，支持插入、删除和查询操作，要求平均时间复杂度为O(1)。解答4：使用哈希集合（如Java中的`HashSet`或Python中的`set`）。javaimportjava.util.HashSet;importjava.util.Set;publicclassCustomSet{privateSet<Integer>set;publicCustomSet(){set=newHashSet<>();}publicvoidinsert(intvalue){set.add(value);}publicvoiddelete(intvalue){set.remove(value);}publicbooleancontains(intvalue){returnset.contains(value);}}解析：1.哈希集合通过哈希函数将元素存储在桶中，确保插入、删除和查询的平均时间复杂度为O(1)。2.若哈希冲突，通过链表或红黑树解决，但实际操作仍保持高效。题目5：实现一个二叉搜索树（BST）的迭代后序遍历（左右中）。解答5：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpostorderTraversal(root):ifnotroot:return[]stack=[]output=[]last_visited=Nonecurrent=rootwhilestackorcurrent:ifcurrent:stack.append(current)current=current.leftelse:peek_node=stack[-1]ifpeek_node.rightandlast_visited!=peek_node.right:current=peek_node.rightelse:stack.pop()output.append(peek_node.val)last_visited=peek_nodereturnoutput解析：1.迭代后序遍历需访问左子树、右子树和根节点。2.使用栈模拟递归，通过`last_visited`变量记录已访问的右子节点，避免重复访问。3.时间复杂度为O(n)，空间复杂度为O(n)。题目6：给定一个包含n个整数的数组，找到和为特定值target的三个数的组合数量。解答6：pythondefthreeSum(nums,target):nums.sort()n=len(nums)count=0foriinrange(n-2):left,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:count+=1left+=1right-=1eliftotal<target:left+=1else:right-=1returncount解析：1.先排序数组，便于使用双指针法。2.固定一个数，用双指针分别从左右查找剩余的两个数，满足和为target时计数加1。3.时间复杂度为O(n²)，空间复杂度为O(1)。题目7：设计一个LRU（LeastRecentlyUsed）缓存，支持get和put操作，容量为capacity。解答7：使用双向链表+哈希表实现。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.headdefget(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:node=DLinkedNode(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]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_nodedef_pop_tail(self):res=self.tail.prevself._remove_node(res)returnres解析：1.使用双向链表维护访问顺序，头节点为最近访问，尾节点为最久未访问。2.哈希表`cache`存储键到节点的映射，实现O(1)时间复杂度的get和put。3.put操作时若超出容量，则删除尾节点。题目8：实现快速排序算法，并分析其时间复杂度和稳定性。解答8：pythondefquicksort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquicksort(left)+middle+quicksort(right)解析：1.快速排序采用分治法，选择基准值（pivot）并分区。2.时间复杂度：平均O(nlogn)，最坏O(n²)；空间复杂度O(logn)。3.不稳定排序，因相等的元素可能因分区顺序改变相对位置。三、系统设计与数据库（5题，每题15分，共75分）题目9：设计一个高并发的短链接系统，要求支持秒级生成和解析，并保证唯一性。解答9：1.短链接生成：-使用哈希算法（如SHA-256）将长链接加密，取前6位作为短链接（62进制编码）。-若冲突，增加位数或使用雪崩效应更强的算法（如Base62）。2.高并发支持：-使用Redis或Memcached缓存热点短链接，减少数据库查询。-分布式锁确保唯一性（如ZooKeeper或Redis分布式锁）。3.唯一性保证：-数据库使用自增ID或UUID，结合缓存雪崩处理。-监控并设置告警，防止ID冲突。题目10：设计一个高可用、可扩展的订单系统，支持高并发下单场景。解答10：1.架构设计：-微服务架构，订单、支付、库存独立部署。-使用消息队列（如Kafka）解耦服务。2.高可用：-订单服务使用多副本部署（如Kubernetes），负载均衡。-数据库读写分离，主从复制（如MySQLCluster）。3.可扩展：-使用无状态服务，水平扩展。-超时控制与熔断（如Hystrix）。题目11：设计一个支持分页、搜索和排序的商品推荐系统，数据量千万级。解答11：1.数据存储：-使用Elasticsearch分页和搜索，排序通过排序算法。-推荐算法基于协同过滤（如矩阵分解）。2.缓存策略：-Redis缓存热门商品和用户画像。-Tengine或Nginx反向代理，减少后端压力。3.性能优化：-异步更新推荐结果（如Celery）。-冷热数据分离（如HBase）。题目12：设计一个支持百万级日活用户的实时推送系统（如消息通知）。解答12：1.架构设计：-使用WebSocket或MQTT协议。-Redis订阅模式（如RedisPub/Sub）。2.高并发：-消息队列削峰填谷（如RocketMQ）。-负载均衡器分发请求。3.容灾备份：-多机房部署，跨区域同步。-监控告警（如Prometheus+Grafana）。题目13：设计一个支持高并发写入的日志系统，要求支持实时查询和分词索引。解答13：1.写入优化：-Kafka或Pulsar日志收集，分布式写入。-HDFS或对象存储归档。2.查询优化：-