2026年百度算法工程師面試題及答案一、編程題（共5題，每題15分，總分75分）1.（15分）題目：給定一個(gè)非空字符串`s`，其中僅包含小寫字母。你可以對(duì)字符串進(jìn)行任意次數(shù)的刪除操作，每次刪除操作必須刪除兩個(gè)相鄰且相同的字母。返回刪除操作后的字符串。示例：輸入：s="abba"輸出：""輸入：s="aab"輸出："b"要求：-請(qǐng)使用Python實(shí)現(xiàn)，并解釋時(shí)間復(fù)雜度。-考慮邊界情況，如字符串長(zhǎng)度為奇數(shù)或全為相同字符。答案與解析：pythondefremoveDuplicates(s:str)->str:stack=[]forcharins:ifstackandstack[-1]==char:stack.pop()else:stack.append(char)return''.join(stack)解析：-使用棧（列表）存儲(chǔ)字符，遍歷字符串時(shí)，若棧頂字符與當(dāng)前字符相同，則彈出棧頂（刪除兩個(gè)相鄰相同字符）。-時(shí)間復(fù)雜度：O(n)，只需遍歷一次字符串?？臻g復(fù)雜度：O(n)，最壞情況下棧存儲(chǔ)所有字符。2.（15分）題目：設(shè)計(jì)一個(gè)LRU（LeastRecentlyUsed）緩存，支持以下操作：-`get(key)`:獲取鍵`key`對(duì)應(yīng)的值，若存在則返回值并更新最近使用時(shí)間，否則返回-1。-`put(key,value)`:插入或更新鍵值對(duì)，若緩存已滿則刪除最久未使用的鍵。要求：-使用Python實(shí)現(xiàn)，并解釋時(shí)間復(fù)雜度。-可使用哈希表+雙向鏈表實(shí)現(xiàn)。答案與解析：pythonclassNode: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=Node(),Node()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)ifnode:node.value=valueself._move_to_head(node)else:newNode=Node(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]解析：-使用哈希表存儲(chǔ)鍵到節(jié)點(diǎn)的映射，雙向鏈表維護(hù)最近使用順序。-`get`操作將節(jié)點(diǎn)移到頭部，`put`操作插入新節(jié)點(diǎn)并可能刪除尾部節(jié)點(diǎn)。-時(shí)間復(fù)雜度：O(1)。3.（15分）題目：給定一個(gè)包含`n`個(gè)整數(shù)的數(shù)組，返回所有和為`target`的三個(gè)整數(shù)的組合。結(jié)果中不能有重復(fù)的組合。示例：輸入：nums=[2,7,11,15],target=9輸出：[[2,7]]要求：-使用Python實(shí)現(xiàn)，并解釋時(shí)間復(fù)雜度。-可使用哈希表去重。答案與解析：pythondefthreeSum(nums:List[int],target:int)->List[List[int]]:nums.sort()res=[]foriinrange(len(nums)-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,len(nums)-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:res.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnres解析：-先排序，然后固定一個(gè)數(shù)，使用雙指針法查找另外兩個(gè)數(shù)。-去重：跳過重復(fù)的數(shù)以避免重復(fù)組合。-時(shí)間復(fù)雜度：O(n2)。4.（15分）題目：給定一個(gè)無向圖，包含`n`個(gè)節(jié)點(diǎn)和`m`條邊，判斷該圖是否為二分圖（即可以將節(jié)點(diǎn)分成兩個(gè)集合，使得每條邊連接的兩個(gè)節(jié)點(diǎn)屬于不同集合）。示例：輸入：n=4,edges=[[1,2],[1,3],[2,4]]輸出：True要求：-使用Python實(shí)現(xiàn)，并解釋時(shí)間復(fù)雜度。-可使用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）。答案與解析：pythondefisBipartite(n:int,edges:List[List[int]])->bool:fromcollectionsimportdefaultdict,dequegraph=defaultdict(list)foru,vinedges:graph[u].append(v)graph[v].append(u)color={}fornodeinrange(1,n+1):ifnodenotincolor:color[node]=0queue=deque([node])whilequeue:current=queue.popleft()forneighboringraph[current]:ifneighbornotincolor:color[neighbor]=1-color[current]queue.append(neighbor)elifcolor[neighbor]==color[current]:returnFalsereturnTrue解析：-使用顏色標(biāo)記兩個(gè)集合（0和1），遍歷每個(gè)節(jié)點(diǎn)，若相鄰節(jié)點(diǎn)顏色相同則不是二分圖。-時(shí)間復(fù)雜度：O(n+m)。5.（15分）題目：給定一個(gè)整數(shù)數(shù)組，返回所有子序列的和的異或（XOR）的最大值。示例：輸入：nums=[1,2,3,4]輸出：7要求：-使用Python實(shí)現(xiàn)，并解釋時(shí)間復(fù)雜度。-可使用動(dòng)態(tài)規(guī)劃或位運(yùn)算。答案與解析：pythondefmaxSubarrayXOR(nums:List[int])->int:xor=[0]32fornuminnums:foriinrange(31,-1,-1):ifnum&(1<<i):xor[i]^=1max_xor=0foriinrange(31,-1,-1):ifxor[i]:max_xor|=(1<<i)returnmax_xor解析：-使用位運(yùn)算統(tǒng)計(jì)每個(gè)位的1的個(gè)數(shù)，若某位有奇數(shù)個(gè)1，則可設(shè)置該位為1。-時(shí)間復(fù)雜度：O(n32)。二、系統(tǒng)設(shè)計(jì)題（共2題，每題25分，總分50分）1.（25分）題目：設(shè)計(jì)一個(gè)高并發(fā)的短鏈接服務(wù)（如t.co），要求：-用戶輸入長(zhǎng)鏈接，返回短鏈接，點(diǎn)擊短鏈接可跳轉(zhuǎn)至長(zhǎng)鏈接。-支持高并發(fā)訪問（每秒百萬級(jí)請(qǐng)求），并保證低延遲。要求：-說明系統(tǒng)架構(gòu)，數(shù)據(jù)庫(kù)選擇，緩存策略。-分析關(guān)鍵模塊的設(shè)計(jì)思路。答案與解析：系統(tǒng)架構(gòu)：1.API服務(wù)層（無狀態(tài)）：-使用多個(gè)負(fù)載均衡的API服務(wù)器（如Nginx+Gunicorn），處理長(zhǎng)鏈接生成和短鏈接跳轉(zhuǎn)請(qǐng)求。-使用Redis緩存熱點(diǎn)短鏈接的映射關(guān)系。2.數(shù)據(jù)庫(kù)：-使用分片MySQL存儲(chǔ)長(zhǎng)鏈接和短鏈接的映射，主鍵為短鏈接ID。-索引：短鏈接ID（唯一），創(chuàng)建時(shí)間。3.分布式ID生成器：-使用Snowflake算法生成唯一短鏈接ID（如`http://t.co/xxxxxxxx`）。4.CDN加速：-將熱點(diǎn)短鏈接的跳轉(zhuǎn)規(guī)則配置到CDN，減少源站壓力。緩存策略：-使用Redis緩存熱點(diǎn)短鏈接的映射（過期時(shí)間如1小時(shí)），減少數(shù)據(jù)庫(kù)查詢。-使用本地緩存（如LRU）緩存頻繁訪問的短鏈接。關(guān)鍵模塊設(shè)計(jì)：-長(zhǎng)鏈接生成：-SnowflakeID生成短鏈接，寫入數(shù)據(jù)庫(kù)和Redis。-短鏈接跳轉(zhuǎn)：-首查Redis，若未命中則查數(shù)據(jù)庫(kù)，返回長(zhǎng)鏈接。2.（25分）題目：設(shè)計(jì)一個(gè)實(shí)時(shí)推薦系統(tǒng)，輸入用戶行為日志（如點(diǎn)擊、收藏、購(gòu)買），輸出個(gè)性化推薦列表。要求：-支持毫秒級(jí)響應(yīng)，處理每秒數(shù)千條行為日志。-推薦算法需兼顧準(zhǔn)確性和多樣性。要求：-說明數(shù)據(jù)流處理架構(gòu)，推薦算法，以及離線與在線協(xié)同。答案與解析：數(shù)據(jù)流處理架構(gòu)：1.消息隊(duì)列（Kafka/Flink）：-用戶行為日志接入Kafka，使用Flink實(shí)時(shí)處理并更新用戶畫像。2.特征存儲(chǔ)（Redis/HBase）：-存儲(chǔ)用戶實(shí)時(shí)特征（如最近點(diǎn)擊、收藏商品）。3.離線計(jì)算（Spark）：-每日計(jì)算用戶畫像（如協(xié)同過濾模型、用戶標(biāo)簽）。推薦算法：-實(shí)時(shí)部分：-基于用戶最近行為（如點(diǎn)擊商品）進(jìn)行召回（如Top-K相似用戶商品）。-離線部分：-協(xié)同過濾（UserCF/ItemCF），矩陣分解（如SVD）。-融合：-將實(shí)時(shí)召回與離線排序結(jié)合（如LambdaMART）。離線與在線協(xié)同：-離線模型每日更新，在線模型實(shí)時(shí)微調(diào)（如使用在線學(xué)習(xí)）。-使用A/B測(cè)試評(píng)估推薦效果，動(dòng)態(tài)調(diào)整策略。三、綜合題（共2題，每題25分，總分50分）1.（25分）題目：假設(shè)你正在開發(fā)百度的AI寫作助手，輸入一段文本，輸出流暢的續(xù)寫內(nèi)容。請(qǐng)：-設(shè)計(jì)模型輸入輸出，說明關(guān)鍵技術(shù)（如Transformer）。-分析如何提升續(xù)寫質(zhì)量（如避免重復(fù)、邏輯連貫）。答案與解析：模型輸入輸出：-輸入：-原始文本（如用戶輸入的段落）。-文本長(zhǎng)度限制（如200字）。-輸出：-推薦的續(xù)寫內(nèi)容（如下一段話）。關(guān)鍵技術(shù)：-Transformer+Attention：-使用BERT/Transformer編碼輸入文本，通過Self-Attention捕捉上下文關(guān)系。-生成策略：-BeamSearch或GreedyDecoding生成續(xù)寫內(nèi)容。提升續(xù)寫質(zhì)量：-避免重復(fù)：-使用TokenMask或No-RepeatConstraint限制重復(fù)詞語(yǔ)。-邏輯連貫：-引入外部知識(shí)圖譜（如百度百科）增強(qiáng)事實(shí)一致性。2.（25分）題目：百度地圖需要實(shí)時(shí)更新道路擁堵情況，請(qǐng)?jiān)O(shè)計(jì)一個(gè)監(jiān)控系統(tǒng)：-數(shù)據(jù)來源（如手機(jī)GPS數(shù)據(jù)、攝像頭）。-處理流程（如異常檢測(cè)、擁堵預(yù)測(cè)）。-如何優(yōu)化系統(tǒng)魯棒性（如數(shù)據(jù)去噪、容