2026年滴出行技術(shù)面試題目與解答一、編程語言基礎(chǔ)（3題，每題10分，共30分）題目1：用Python實(shí)現(xiàn)一個(gè)函數(shù)，接收一個(gè)字符串作為輸入，返回該字符串中所有唯一字符的列表（即出現(xiàn)一次的字符）。假設(shè)輸入字符串僅包含小寫字母，且長度不超過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`統(tǒng)計(jì)每個(gè)字符的出現(xiàn)次數(shù)。2.遍歷字符串，若字符已存在于字典中，則計(jì)數(shù)加1；否則初始化為1。3.最終通過列表推導(dǎo)式篩選出現(xiàn)次數(shù)為1的字符并返回。4.時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)（假設(shè)字符集固定為小寫字母）。題目2：用Java實(shí)現(xiàn)一個(gè)方法，接收一個(gè)整數(shù)數(shù)組，返回該數(shù)組的中位數(shù)。假設(shè)數(shù)組長度為奇數(shù)。解答2：javaimportjava.util.Arrays;publicstaticdoublefindMedian(int[]arr){Arrays.sort(arr);intn=arr.length;return(double)arr[n/2];}解析：1.使用`Arrays.sort`對數(shù)組進(jìn)行排序，時(shí)間復(fù)雜度為O(nlogn)。2.中位數(shù)為排序后位于中間位置的元素（索引為`n/2`）。3.返回中位數(shù)時(shí)轉(zhuǎn)換為`double`類型以支持浮點(diǎn)數(shù)。題目3：用C++實(shí)現(xiàn)一個(gè)函數(shù)，接收一個(gè)字符串，返回該字符串的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.遍歷模式串，若當(dāng)前字符與前綴不匹配，則移動前綴長度至`lps[length-1]`。3.匹配成功則前綴長度加1，記錄至`lps[i]`。4.最終返回前綴表，用于KMP算法的匹配過程。二、數(shù)據(jù)結(jié)構(gòu)與算法（5題，每題12分，共60分）題目4：設(shè)計(jì)一個(gè)無重復(fù)元素的集合，支持插入、刪除和查詢操作，要求平均時(shí)間復(fù)雜度為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.哈希集合通過哈希函數(shù)將元素存儲在桶中，確保插入、刪除和查詢的平均時(shí)間復(fù)雜度為O(1)。2.若哈希沖突，通過鏈表或紅黑樹解決，但實(shí)際操作仍保持高效。題目5：實(shí)現(xiàn)一個(gè)二叉搜索樹（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.迭代后序遍歷需訪問左子樹、右子樹和根節(jié)點(diǎn)。2.使用棧模擬遞歸，通過`last_visited`變量記錄已訪問的右子節(jié)點(diǎn)，避免重復(fù)訪問。3.時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。題目6：給定一個(gè)包含n個(gè)整數(shù)的數(shù)組，找到和為特定值target的三個(gè)數(shù)的組合數(shù)量。解答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.先排序數(shù)組，便于使用雙指針法。2.固定一個(gè)數(shù)，用雙指針分別從左右查找剩余的兩個(gè)數(shù)，滿足和為target時(shí)計(jì)數(shù)加1。3.時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。題目7：設(shè)計(jì)一個(gè)LRU（LeastRecentlyUsed）緩存，支持get和put操作，容量為capacity。解答7：使用雙向鏈表+哈希表實(shí)現(xiàn)。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.使用雙向鏈表維護(hù)訪問順序，頭節(jié)點(diǎn)為最近訪問，尾節(jié)點(diǎn)為最久未訪問。2.哈希表`cache`存儲鍵到節(jié)點(diǎn)的映射，實(shí)現(xiàn)O(1)時(shí)間復(fù)雜度的get和put。3.put操作時(shí)若超出容量，則刪除尾節(jié)點(diǎn)。題目8：實(shí)現(xiàn)快速排序算法，并分析其時(shí)間復(fù)雜度和穩(wěn)定性。解答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.快速排序采用分治法，選擇基準(zhǔn)值（pivot）并分區(qū)。2.時(shí)間復(fù)雜度：平均O(nlogn)，最壞O(n2)；空間復(fù)雜度O(logn)。3.不穩(wěn)定排序，因相等的元素可能因分區(qū)順序改變相對位置。三、系統(tǒng)設(shè)計(jì)與數(shù)據(jù)庫（5題，每題15分，共75分）題目9：設(shè)計(jì)一個(gè)高并發(fā)的短鏈接系統(tǒng)，要求支持秒級生成和解析，并保證唯一性。解答9：1.短鏈接生成：-使用哈希算法（如SHA-256）將長鏈接加密，取前6位作為短鏈接（62進(jìn)制編碼）。-若沖突，增加位數(shù)或使用雪崩效應(yīng)更強(qiáng)的算法（如Base62）。2.高并發(fā)支持：-使用Redis或Memcached緩存熱點(diǎn)短鏈接，減少數(shù)據(jù)庫查詢。-分布式鎖確保唯一性（如ZooKeeper或Redis分布式鎖）。3.唯一性保證：-數(shù)據(jù)庫使用自增ID或UUID，結(jié)合緩存雪崩處理。-監(jiān)控并設(shè)置告警，防止ID沖突。題目10：設(shè)計(jì)一個(gè)高可用、可擴(kuò)展的訂單系統(tǒng)，支持高并發(fā)下單場景。解答10：1.架構(gòu)設(shè)計(jì)：-微服務(wù)架構(gòu)，訂單、支付、庫存獨(dú)立部署。-使用消息隊(duì)列（如Kafka）解耦服務(wù)。2.高可用：-訂單服務(wù)使用多副本部署（如Kubernetes），負(fù)載均衡。-數(shù)據(jù)庫讀寫分離，主從復(fù)制（如MySQLCluster）。3.可擴(kuò)展：-使用無狀態(tài)服務(wù)，水平擴(kuò)展。-超時(shí)控制與熔斷（如Hystrix）。題目11：設(shè)計(jì)一個(gè)支持分頁、搜索和排序的商品推薦系統(tǒng)，數(shù)據(jù)量千萬級。解答11：1.數(shù)據(jù)存儲：-使用Elasticsearch分頁和搜索，排序通過排序算法。-推薦算法基于協(xié)同過濾（如矩陣分解）。2.緩存策略：-Redis緩存熱門商品和用戶畫像。-Tengine或Nginx反向代理，減少后端壓力。3.性能優(yōu)化：-異步更新推薦結(jié)果（如Celery）。-冷熱數(shù)據(jù)分離（如HBase）。題目12：設(shè)計(jì)一個(gè)支持百萬級日活用戶的實(shí)時(shí)推送系統(tǒng)（如消息通知）。解答12：1.架構(gòu)設(shè)計(jì)：-使用WebSocket或MQTT協(xié)議。-Redis訂閱模式（如RedisPub/Sub）。2.高并發(fā)：-消息隊(duì)列削峰填谷（如RocketMQ）。-負(fù)載均衡器分發(fā)請求。3.容災(zāi)備份：-多機(jī)房部署，跨區(qū)域同步。-監(jiān)控告警（如Prometheus+Grafana）。題目13：設(shè)計(jì)一個(gè)支持高并發(fā)寫入的日志系統(tǒng)，要求支持實(shí)時(shí)查詢和分詞索引。解答13：1.寫入優(yōu)化：-Kafka或Pulsar日志收集，分布式寫入。-HDFS或?qū)ο蟠鎯w檔。2.查詢優(yōu)化：-