2026年滴出行技术面试题及参考答案

2026年滴出行技术面试题及参考答案一、编程题（共3题，每题15分，总分45分）1.题目（15分）：请实现一个函数`findCheapestPrice(n,flights,src,dst,K)`，其中：-`n`表示城市数量（编号从0到n-1）。-`flights`是一个列表，每个元素为`[u,v,w]`，表示从城市`u`到城市`v`的价格是`w`。-`src`是出发城市，`dst`是目的城市。-`K`是最多经过的换乘次数（包括起点和终点）。-返回从`src`到`dst`的最低价格。如果无法到达，返回`-1`。示例：pythonn=3,flights=[[0,1,100],[1,2,100],[0,2,500]],src=0,dst=2,K=1输出:200参考答案：pythondeffindCheapestPrice(n,flights,src,dst,K):初始化距离表，所有城市到src的距离为无穷大，src到src为0dist=[float('inf')]ndist[src]=0forkinrange(K+1):temp=dist.copy()#深拷贝当前距离表foru,v,winflights:ifdist[u]==float('inf'):continueifdist[u]+w<temp[v]:temp[v]=dist[u]+wdist=temp#更新距离表return-1ifdist[dst]==float('inf')elsedist[dst]解析：-使用动态规划思想，每次更新最多经过`k`次换乘的最短路径。-外层循环控制换乘次数（最多`K`次），内层循环遍历所有航班。-每次更新时，使用临时数组`temp`避免覆盖未更新的值。-最终返回`dist[dst]`，若为无穷大则表示无法到达。2.题目（15分）：请实现一个无重复字符的最长子串函数`lengthOfLongestSubstring(s)`，其中`s`是一个字符串。示例：pythons="abcabcbb"输出:3("abc")参考答案：pythondeflengthOfLongestSubstring(s):left=0max_len=0char_set=set()forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_len=max(max_len,right-left+1)returnmax_len解析：-使用滑动窗口技术，`left`和`right`分别表示窗口的左右边界。-`char_set`记录当前窗口中的字符，若`s[right]`已存在，则移动`left`直至无重复。-每次更新最大长度`max_len`。-时间复杂度O(n)，空间复杂度O(min(m,n))，其中m是字符集大小。3.题目（15分）：请实现一个函数`merge(intervals)`，合并所有重叠的区间。示例：pythonintervals=[[1,3],[2,6],[8,10],[15,18]]输出:[[1,6],[8,10],[15,18]]参考答案：pythondefmerge(intervals):ifnotintervals:return[]按区间的起始位置排序intervals.sort(key=lambdax:x[0])merged=[]forintervalinintervals:如果列表为空或当前区间不与最后一个区间重叠ifnotmergedormerged[-1][1]<interval[0]:merged.append(interval)else:合并重叠区间merged[-1][1]=max(merged[-1][1],interval[1])returnmerged解析：-首先按区间的起始位置排序，确保可以按顺序合并。-遍历每个区间，若不与已合并的最后一个区间重叠，则直接添加；否则更新最后一个区间的结束位置。-时间复杂度O(nlogn)，空间复杂度O(n)。二、算法题（共4题，每题10分，总分40分）1.题目（10分）：给定一个链表，判断其是否为回文链表。示例：python输入:1->2->3->3->2->1输出:true参考答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefisPalindrome(head):ifnotheadornothead.next:returnTrue找到链表中间位置slow=headfast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.next反转后半部分链表prev=Nonewhileslow:temp=slow.nextslow.next=prevprev=slowslow=temp比较前半部分和反转后的后半部分left,right=head,prevwhileright:#只需比较到后半部分结束ifleft.val!=right.val:returnFalseleft=left.nextright=right.nextreturnTrue解析：-使用快慢指针找到链表中间位置，将后半部分反转。-比较反转后的后半部分与前半部分是否相同。-时间复杂度O(n)，空间复杂度O(1)。2.题目（10分）：请设计一个LRU（最近最少使用）缓存，支持`get`和`put`操作。示例：python初始化容量为2lru=LRUCache(2)lru.put(1,1)lru.put(2,2)lru.get(1)#返回1lru.put(3,3)#去除键2lru.get(2)#返回-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`维护键值对，记录访问顺序。-`get`操作将键移动到末尾表示最近使用。-`put`操作若超出容量则移除最久未使用的键。-时间复杂度O(1)，空间复杂度O(capacity)。3.题目（10分）：给定一个二叉树，判断其是否是平衡二叉树（左右子树高度差不超过1）。示例：python输入:[3,9,20,null,null,15,7]输出:true参考答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefisBalanced(root):defcheck(node):ifnotnode:return0left=check(node.left)right=check(node.right)ifleft==-1orright==-1orabs(left-right)>1:return-1returnmax(left,right)+1returncheck(root)!=-1解析：-使用后序遍历计算每个节点的左右子树高度。-若高度差超过1或子树不平衡（返回-1），则整棵树不平衡。-时间复杂度O(n)，空间复杂度O(h)，其中h是树的高度。4.题目（10分）：请实现一个函数`topKFrequent(nums,k)`，返回出现频率最高的`k`个元素。示例：pythonnums=[1,1,1,2,2,3],k=2输出:[1,2]参考答案：pythonfromcollectionsimportCounterdeftopKFrequent(nums,k):count=Counter(nums)按频率降序排序，若频率相同则按元素升序return[numfornum,_incount.most_common(k)]解析：-使用`Counter`统计每个元素的出现频率。-`most_common(k)`返回频率最高的`k`个元素。-时间复杂度O(nlogn)，空间复杂度O(n)。三、系统设计题（共2题，每题25分，总分50分）1.题目（25分）：设计一个短链接系统，要求：-输入长链接，输出短链接（如`/abc123`）。-支持通过短链接跳转回长链接。-高并发场景下仍能快速响应。参考答案：1.数据结构：-使用哈希表（如Redis）存储`short_id->long_url`映射，确保O(1)查询。-短链接`short_id`由随机生成或Base62编码（a-z,A-Z,0-9）组成。2.流程：-输入长链接时，生成唯一`short_id`，存入哈希表，返回短链接。-跳转时，解析`short_id`，从哈希表获取长链接并返回。3.高并发处理：-使用Redis的分布式锁或Lua脚本避免并发生成相同的`short_id`。-负载均衡分发请求至多个节点。4.优化：-缓存热点短链接，减少数据库查询。-统计点击量，支持数据分析。2.题目（25分）：设计一个实时路况监控系统，要求：-支持车辆上报位置和速度。-实时计算每个路段的拥堵状态（如`smooth`,`busy`）。-支持按区域或时间段查询路况。参考答案：1.数据结构：-使用地图（如GeoHash）存储路段信息，每个路段关联车辆列表。-车辆信息包