2026年百度搜索算法工程师面试问题集

2026年百度搜索算法工程师面试问题集一、编程基础与数据结构（共5题，每题8分）1.题目：给定一个未排序的整数数组，返回其中出现次数超过阈值（例如50%）的最小整数。要求时间复杂度O(n)，空间复杂度O(1)。示例：输入`[3,4,3,2,2,3,3]`，阈值50%，输出`3`。答案：-使用摩尔投票法（Boyer-MooreMajorityVote）：1.初始化`candidate=None`，`count=0`；2.遍历数组：-若`count==0`，则`candidate=num`，`count=1`；-否则，若`num==candidate`，`count+=1`；否则`count-=1`；3.验证`candidate`是否满足阈值（可通过第二次遍历统计频率）；-代码示例（Python）：pythondefmajority_element(nums,threshold=50):candidate=Nonecount=0fornuminnums:ifcount==0:candidate=numcount=1elifnum==candidate:count+=1else:count-=1验证频率ifnums.count(candidate)>len(nums)(threshold/100):returncandidatereturn-1-解析：摩尔投票法适用于寻找“多数元素”（出现次数>50%），通过抵消法确保最终`candidate`是真实多数元素。验证步骤防止误判（如`[3,3]`，若阈值50%则需返回`3`）。2.题目：实现一个LRU（LeastRecentlyUsed）缓存，支持`get(key)`和`put(key,value)`操作。要求时间复杂度O(1)。示例：-`put(1,1)`→缓存为`{1:1}`；-`put(2,2)`→缓存为`{1:1,2:2}`；-`get(1)`→返回`1`（访问1）；-`put(3,3)`→最久未使用`2`被移除，缓存为`{1:1,2:3,3:3}`；-`get(2)`→返回`3`（2已过期）。答案：-使用双向链表+哈希表：-双向链表：头节点为最近使用，尾节点为最久未使用；-哈希表：`key→node`，O(1)访问；-操作：-`get(key)`：若存在，移动节点到头，返回值；否则返回-1；-`put(key,value)`：若存在，更新值并移动到头；否则，若缓存满，移除尾节点，插入新节点到头。-代码示例（Python伪代码）：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head,self.tail=Node(0,0),Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key):ifkeyinself.cache:node=self.cache[key]self._move_to_head(node)returnnode.valuereturn-1defput(self,key,value):ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_head(node)else:iflen(self.cache)==self.capacity:self._remove_tail()new_node=Node(key,value)self.cache[key]=new_nodeself._add_to_head(new_node)def_move_to_head(self,node):self._remove_node(node)self._add_to_head(node)def_add_to_head(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):node.prev.next=node.nextnode.next.prev=node.prevdef_remove_tail(self):tail=self.tail.prevself._remove_node(tail)delself.cache[tail.key]-解析：LRU的核心在于高效更新“最近使用”状态。双向链表保证O(1)删除/插入，哈希表保证O(1)查询单节点。3.题目：给定一个字符串`s`，判断是否可以通过删除零个或多个字符（不改变剩余字符顺序）得到`p`。例如，`s="abcde"`,`p="ace"`→返回`True`。示例：`s="axc"`,`p="ac"`→`True`；`s="abc"`,`p="def"`→`False`。答案：-双指针法：1.初始化`i=j=0`；2.遍历`s`，若`s[i]==p[j]`，则`i++`，`j++`；3.若`j==len(p)`，则匹配成功；-代码示例（Python）：pythondefisSubsequence(s,p):i,j=0,0whilei<len(s)andj<len(p):ifs[i]==p[j]:j+=1i+=1returnj==len(p)-解析：通过逐个匹配`s`和`p`的字符，确保`p`的顺序在`s`中存在。若`j`遍历完`p`，则`p`是`s`的子序列。4.题目：实现一个函数，统计字符串中所有不同字母的全排列中字典序第`k`小的排列。例如，`s="abc"`,`k=4`→输出`"bac"`。示例：`s="aabb"`,`k=9`→`"bbaa"`。答案：-前缀统计+阶乘计算：1.统计`s`中各字母频率；2.对每个前缀字母（按字母顺序），计算其阶乘（`fact=factorial(len(s)-1)`）；3.`k=k-count[prev]fact`，若`k<=0`，则当前字母为首位；4.移除当前字母，递归处理剩余字母；-代码示例（Python）：pythondefgetPermutation(s,k):frommathimportfactorialcount={}forcins:count[c]=count.get(c,0)+1res=[]total=factorial(len(s))k-=1foriinrange(len(s)):fact=factorial(len(s)-1-i)forcinsorted(count.keys()):ifcount[c]==0:continueifk<fact:res.append(c)count[c]-=1breakk-=factreturn''.join(res)-解析：通过计算每个字母作为首位的可能性，逐步确定前缀，递归处理剩余字母。时间复杂度O(n^2)，适用于n≤10。5.题目：给定一个无向图，判断是否包含环。要求不使用额外空间（除递归栈）。示例：图表示为邻接表`[[1],[0,2],[1,3],[3]]`→无环；`[[1,2],[0,2],[0,1,3],[3]]`→有环。答案：-深度优先搜索（DFS）：1.对每个节点，若未访问，执行DFS；2.在DFS中，标记节点为“正在访问”（gray），若再次遇到gray则环存在；3.完成后标记为“已访问”（black）；-代码示例（Python）：pythondefhasCycle(graph):color=[0]len(graph)#0:white,1:gray,2:blackdefdfs(node):ifcolor[node]==1:returnTrueifcolor[node]==2:returnFalsecolor[node]=1forneighboringraph[node]:ifdfs(neighbor):returnTruecolor[node]=2returnFalseforiinrange(len(graph)):ifcolor[i]==0:ifdfs(i):returnTruereturnFalse-解析：通过颜色标记避免重复遍历，DFS是环检测的经典方法。若某节点在“正在访问”状态被再次访问，则存在环。二、系统设计（共3题，每题10分）1.题目：设计一个类似百度知道的问答系统，要求支持实时搜索、答案排序（优先权威度高的内容）、用户反馈调整。答案：-架构：1.数据层：-问题库：Elasticsearch索引，存储问题、答案、来源（如百度知道）、权威度（根据用户投票、专家认证）；-用户反馈：Redis存储用户点赞/踩记录，用于实时调整排序；2.计算层：-搜索引擎：B站式搜索（关键词匹配+语义理解），召回TopK问题；-排序模型：-特征：问题与查询的TF-IDF相似度、答案权威度（投票数、专家标签）、用户行为（点击率、停留时长）；-模型：LambdaMART或LambdaRank，线上A/B测试优化；3.服务层：-API：RESTful接口，支持分页、实时反馈；-缓存：Redis缓存热门问题及答案；-关键点：-权威度计算：结合专家认证和用户投票（如Top1000问题优先展示）；-实时反馈：用户反馈通过Redis更新答案排序权重；-扩展：-多模态输入（图片问题→OCR转文字）；-问答对训练（强化专家知识）。2.题目：设计一个支持亿级用户的短链接服务（如百度短链），要求高并发、低延迟、唯一性。答案：-架构：1.存储层：-短码生成：62位Base62编码（a-z,A-Z,0-9），覆盖`62^62`组合；-数据结构：Redis存储`短码→长URL`映射（高并发写）；-持久化：RocksDB或Cassandra，避免Redis重启丢失数据；2.计算层：-唯一性校验：分布式锁（RedisLua脚本）确保短码生成唯一；-热点处理：热点短码使用CDN缓存，减少后端压力；3.服务层：-API：HTTP接口，支持异步生成短码（客户端先请求，后端回调）；-负载均衡：Nginx+LVS分发请求；-关键点：-唯一性：Base62编码+锁机制；-高并发：Redis+异步处理；-低延迟：CDN缓存热点短链。3.题目：设计一个实时推荐系统（如百度信息流），支持个性化内容推送。答案：-架构：1.数据层：-用户行为：Kafka收集点击、点赞、分享数据；-用户画像：HBase存储用户标签（年龄、兴趣、地域）；2.计算层：-召回模型：-协同过滤：基于用户/物品相似度（如UserCF）；-深度学习：DIN（DeepInterestNetwork）捕捉用户动态兴趣；-排序模型：-特征：召回模型的得分、时效性、多样性；-模型：DeepFM或LambdaMART，线上实时更新；3.服务层：-实时计算：Flink/SparkStreaming处理用户行为；-冷启动：新用户使用基于人口统计的推荐；-关键点：-实时性：Kafka+Flink保证毫秒级更新；-多样性：避免推荐同类型内容（如新闻流）；-可解释性：向用户展示推荐原因（如“根据你的浏览历史”）。三、搜索算法与工程（共4题，每题10分）1.题目：解释TF-IDF的原理，并说明如何优化其不足（如忽略语义）。答案：-TF-IDF原理：-TF（词频）：文档内词频，越频繁越重要；-IDF（逆文档频率）：`log(N/df)`，`df`为词出现文档数，越稀疏越重要；-公式：`TF-IDF=TFIDF`；-优化：-语义增强：-LSI（潜在语义索引）：将TF-IDF向量降维到隐含语义空间；-Word2Vec/BERT：用预训练模型捕捉上下文语义；-动态权重：结合用户实时行为（如点击后降低权重）；-领域适配：为特定领域（如医疗）调整IDF计算方式。2.题目：设计一个搜索相关性排序系统，要求支持实时更新和冷启动方案。答案：-实时更新：-在线学习：使用在线梯度下降更新排序模型（如LambdaMART）；-特征工程：实时收集用户行为（如搜索时长、点击后跳转），动态调整特征权重；-冷启动方案：-基于规则：新问题优先展示权威来源（如官网、知乎）；-用户画像：结合用户注册信息（年龄、地域）进行初始推荐；-多样性优先：避免冷启动时推荐同类型内容，鼓励探索。3.题目：解释搜索引擎的召回与排序流程，并说明如何平衡两者。答案：-召回流程：-分词：Jieba分词+停用词过滤；-特征提取：TF-IDF、BM25、文本嵌入（BERT）；-候选集生成：基于倒排索引快速匹配，TopM候选；-排序流程：-特征工程：结合召回特征+用户行为特征（如点击率、多样性）；-模型排序：LambdaRank或DeepFM，A/B测试优化；-平衡策略：-召回-排序协同：召回阶段加入排序模型预估得分，过滤低分候选；-多样性控制：排序时加入多样性约束（如新闻流避免同来源重复）。4.题目：如何处理搜索结果中的噪声（如广告