百度算法工程师面试问题集

2026年百度算法工程师面试问题集一、编程基础与数据结构（共5题，每题10分，总分50分）1.题目：给定一个未排序的整数数组，实现一个函数，找出数组中第三大的数。如果数组中少于三个不同的数，返回最大的数。要求：时间复杂度不超过O(n)，空间复杂度不超过O(1)。2.题目：设计一个LRU（LeastRecentlyUsed）缓存，支持get和put操作。get(key)返回键对应的值，如果键不存在返回-1；put(key,value)插入或更新键值对，如果缓存已满，则删除最久未使用的元素。要求：使用链表和哈希表实现，时间复杂度为O(1)。3.题目：给定一个二叉树，判断其是否是平衡二叉树。平衡二叉树是指对于任意节点，其左右子树的高度差不超过1。要求：时间复杂度不超过O(n)。4.题目：实现一个函数，将一个非负整数转换为罗马数字。罗马数字由I、V、X、L、C、D、M七个字符组成，表示1、5、10、50、100、500、1000。要求：时间复杂度为O(1)。5.题目：给定一个字符串，判断其是否是有效的括号字符串，其中括号包括()、[]、{}。有效字符串需要满足括号匹配且嵌套正确。要求：使用栈实现，时间复杂度为O(n)。二、算法设计与问题解决（共4题，每题15分，总分60分）1.题目：设计一个算法，找出数组中所有出现次数超过一半的数字。假设数组长度为n，至少有一个数字出现次数超过n/2。要求：时间复杂度为O(n)，空间复杂度为O(1)。2.题目：给定一个字符串，判断其是否是另一个字符串的子串。不考虑大小写，且支持多行匹配。要求：使用KMP算法实现，时间复杂度为O(m+n)。3.题目：设计一个算法，找出二叉搜索树中的第k小元素。假设二叉搜索树的根节点为root，k为正整数。要求：时间复杂度不超过O(n)，空间复杂度不超过O(h)。4.题目：给定一个字符串，找出所有可能的排列组合，且不重复。例如，输入"abc"，输出["abc","acb","bac","bca","cab","cba"]。要求：使用回溯算法实现，时间复杂度为O(n!)。三、系统设计与工程能力（共3题，每题20分，总分60分）1.题目：设计一个简单的微博系统，支持用户发布、关注、点赞和查看时间线。用户可以关注其他用户，时间线显示关注用户的最新动态。要求：说明系统架构、数据存储方式、关键模块设计。2.题目：设计一个分布式搜索引擎，支持实时索引更新和快速查询。假设系统由多个节点组成，数据分片存储。要求：说明系统架构、数据分片策略、索引更新机制、查询优化方案。3.题目：设计一个短链生成系统，将长URL转换为短URL，并支持反向解析。例如，输入"/long-url"，输出"短链接"。要求：说明系统架构、短链生成算法、数据存储方式、高并发处理方案。四、自然语言处理与推荐系统（共2题，每题25分，总分50分）1.题目：给定一段文本，提取其中的关键实体（人名、地名、组织名），并判断实体之间的关系。例如，"马云是阿里巴巴的创始人"，提取实体并说明关系。要求：使用命名实体识别（NER）和关系抽取技术，说明实现方法。2.题目：设计一个电影推荐系统，根据用户历史观看记录和评分，推荐可能喜欢的电影。假设用户历史数据包括电影ID、评分和观看时间。要求：说明推荐算法（如协同过滤、深度学习），数据预处理方法，系统架构。五、机器学习与深度学习（共2题，每题25分，总分50分）1.题目：给定一个图像数据集，设计一个卷积神经网络（CNN），实现图像分类任务。假设数据集包含10个类别。要求：说明网络结构（卷积层、池化层、全连接层），训练方法，评估指标。2.题目：设计一个自然语言生成模型，根据输入的文本生成摘要。例如，输入"今天天气很好，我们去公园玩"，生成"今天天气好，去公园玩"。要求：说明模型结构（如RNN、Transformer），训练方法，生成策略。答案与解析一、编程基础与数据结构1.答案：pythondefthird_largest(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:third,second,first=second,first,numeliffirst>num>second:third,second=second,numelifsecond>num>third:third=numreturnfirstifthird==float('-inf')elsethird解析：遍历数组，维护三个变量first、second、third分别表示最大、第二大、第三大的数。每次遇到新的数时，更新这三个变量。最终返回third，如果数组中少于三个不同的数，返回first。2.答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=ListNode(0)self.tail=ListNode(0)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: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:newNode=ListNode(key,value)self.cache[key]=newNodeself._add_node(newNode)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]解析：使用双向链表和哈希表实现。双向链表维护最近使用的顺序，哈希表实现O(1)时间复杂度的get和put操作。当链表满时，删除链表尾部的节点，并从哈希表中删除对应的键。3.答案：pythondefis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)balanced=left_balancedandright_balancedandabs(left_height-right_height)<=1returnmax(left_height,right_height)+1,balancedreturncheck(root)[1]解析：递归检查每个节点的左右子树高度差不超过1。check函数返回子树高度和是否平衡。如果所有节点都满足平衡条件，返回True。4.答案：pythondefint_to_roman(num):val=[1000,900,500,400,100,90,50,40,10,9,5,4,1]syms=["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]roman=""i=0whilenum>0:for_inrange(num//val[i]):roman+=syms[i]num-=val[i]i+=1returnroman解析：使用列表val和syms分别表示数值和符号。从大到小遍历val，对于每个数值，尽可能多地添加对应的符号到结果字符串中，并减少num。最终返回结果字符串。5.答案：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：使用栈遍历字符串。遇到开括号时压栈，遇到闭括号时弹出栈顶元素并检查是否匹配。如果栈为空或栈顶元素不匹配，返回False。遍历结束后，如果栈为空，返回True。二、算法设计与问题解决1.答案：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate解析：Boyer-Moore多数投票算法。维护一个计数器count和一个候选数candidate。遍历数组，如果count为0，将当前数设为候选数；如果当前数与候选数相同，count加1，否则减1。最终候选数为多数元素。2.答案：pythondefKMPSearch(text,pattern):defcomputeLPSArray(pat):M=len(pat)lps=[0]Mlength=0i=1whilei<M:ifpat[i]==pat[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=1returnlpsM=len(pattern)N=len(text)lps=computeLPSArray(pattern)i=0j=0whilei<N:ifpattern[j]==text[i]:i+=1j+=1ifj==M:returnTruej=lps[j-1]elifi<Nandpattern[j]!=text[i]:ifj!=0:j=lps[j-1]else:i+=1returnFalse解析：KMP算法的核心是LPS（最长前缀后缀）数组。computeLPSArray函数计算LPS数组。搜索时，如果字符匹配，移动两个指针；如果不匹配，根据LPS数组移动模式串指针。如果模式串指针到达末尾，返回True。3.答案：pythondefkth_smallest(root,k):definorder(node):nonlocalcount,resifnotnodeorresisnotNone:returninorder(node.left)count+=1ifcount==k:res=node.valreturninorder(node.right)res=Nonecount=0inorder(root)returnres解析：中序遍历二叉搜索树，时间复杂度为O(n)。维护一个计数器count和一个结果变量res。遍历到第k个节点时，记录结果并返回。4.答案：pythondefpermute_unique(nums):res=[]defbacktrack(path,used):iflen(path)==len(nums):res.append(path.copy())returnforiinrange(len(nums)):ifused[i]:continueifi>0andnums[i]==nums[i-1]andnotused[i-1]:continueused[i]=Truepath.append(nums[i])backtrack(path,used)path.pop()used[i]=Falsenums.sort()backtrack([],[False]len(nums))returnres解析：回溯算法实现排列组合。首先对数组排序，避免重复排列。使用used数组记录是否使用过某个数字。每次选择一个未使用的数字，并递归生成所有可能的排列。如果排列长度等于数组长度，记录结果。三、系统设计与工程能力1.微博系统设计：架构：采用微服务架构，包括用户服务、发布服务、关注服务、点赞服务、时间线服务。使用消息队列（如Kafka）处理异步操作。数据存储：用户信息存储在MySQL中，发布内容存储在MongoDB中，关注关系存储在Redis中。关键模块：-用户服务：注册、登录、用户信息管理。-发布服务：发布、编辑、删除微博。-关注服务：关注、取消关注用户。-点赞服务：点赞、取消点赞微博。-时间线服务：根据关注关系聚合用户的时间线。2.分布式搜索引擎设计：架构：采用分布式架构，包括数据节点、索引节点、查询节点。使用Elasticsearch作为搜索引擎。数据分片策略：根据URL的哈希值进行分片，每个分片存储在不同的数据节点上。索引更新机制：使用增量索引，新数据实时写入Elasticsearch。查询优化方案：使用缓存机制，对热门查询结果进行缓存。使用分片路由优化查询性能。3.短链生成系统设计：架构：采用单点服务架构，使用Redis存储短链与长链的映射关