百度算法工程师面试题及答案

2026年百度算法工程师面试题及答案一、编程题（共5题，每题15分，总分75分）1.（15分）题目：给定一个非空字符串`s`，其中仅包含小写字母。你可以对字符串进行任意次数的删除操作，每次删除操作必须删除两个相邻且相同的字母。返回删除操作后的字符串。示例：输入：s="abba"输出：""输入：s="aab"输出："b"要求：-请使用Python实现，并解释时间复杂度。-考虑边界情况，如字符串长度为奇数或全为相同字符。答案与解析：pythondefremoveDuplicates(s:str)->str:stack=[]forcharins:ifstackandstack[-1]==char:stack.pop()else:stack.append(char)return''.join(stack)解析：-使用栈（列表）存储字符，遍历字符串时，若栈顶字符与当前字符相同，则弹出栈顶（删除两个相邻相同字符）。-时间复杂度：O(n)，只需遍历一次字符串。空间复杂度：O(n)，最坏情况下栈存储所有字符。2.（15分）题目：设计一个LRU（LeastRecentlyUsed）缓存，支持以下操作：-`get(key)`:获取键`key`对应的值，若存在则返回值并更新最近使用时间，否则返回-1。-`put(key,value)`:插入或更新键值对，若缓存已满则删除最久未使用的键。要求：-使用Python实现，并解释时间复杂度。-可使用哈希表+双向链表实现。答案与解析：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]解析：-使用哈希表存储键到节点的映射，双向链表维护最近使用顺序。-`get`操作将节点移到头部，`put`操作插入新节点并可能删除尾部节点。-时间复杂度：O(1)。3.（15分）题目：给定一个包含`n`个整数的数组，返回所有和为`target`的三个整数的组合。结果中不能有重复的组合。示例：输入：nums=[2,7,11,15],target=9输出：[[2,7]]要求：-使用Python实现，并解释时间复杂度。-可使用哈希表去重。答案与解析：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解析：-先排序，然后固定一个数，使用双指针法查找另外两个数。-去重：跳过重复的数以避免重复组合。-时间复杂度：O(n²)。4.（15分）题目：给定一个无向图，包含`n`个节点和`m`条边，判断该图是否为二分图（即可以将节点分成两个集合，使得每条边连接的两个节点属于不同集合）。示例：输入：n=4,edges=[[1,2],[1,3],[2,4]]输出：True要求：-使用Python实现，并解释时间复杂度。-可使用深度优先搜索（DFS）或广度优先搜索（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解析：-使用颜色标记两个集合（0和1），遍历每个节点，若相邻节点颜色相同则不是二分图。-时间复杂度：O(n+m)。5.（15分）题目：给定一个整数数组，返回所有子序列的和的异或（XOR）的最大值。示例：输入：nums=[1,2,3,4]输出：7要求：-使用Python实现，并解释时间复杂度。-可使用动态规划或位运算。答案与解析：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解析：-使用位运算统计每个位的1的个数，若某位有奇数个1，则可设置该位为1。-时间复杂度：O(n32)。二、系统设计题（共2题，每题25分，总分50分）1.（25分）题目：设计一个高并发的短链接服务（如t.co），要求：-用户输入长链接，返回短链接，点击短链接可跳转至长链接。-支持高并发访问（每秒百万级请求），并保证低延迟。要求：-说明系统架构，数据库选择，缓存策略。-分析关键模块的设计思路。答案与解析：系统架构：1.API服务层（无状态）：-使用多个负载均衡的API服务器（如Nginx+Gunicorn），处理长链接生成和短链接跳转请求。-使用Redis缓存热点短链接的映射关系。2.数据库：-使用分片MySQL存储长链接和短链接的映射，主键为短链接ID。-索引：短链接ID（唯一），创建时间。3.分布式ID生成器：-使用Snowflake算法生成唯一短链接ID（如`http://t.co/xxxxxxxx`）。4.CDN加速：-将热点短链接的跳转规则配置到CDN，减少源站压力。缓存策略：-使用Redis缓存热点短链接的映射（过期时间如1小时），减少数据库查询。-使用本地缓存（如LRU）缓存频繁访问的短链接。关键模块设计：-长链接生成：-SnowflakeID生成短链接，写入数据库和Redis。-短链接跳转：-首查Redis，若未命中则查数据库，返回长链接。2.（25分）题目：设计一个实时推荐系统，输入用户行为日志（如点击、收藏、购买），输出个性化推荐列表。要求：-支持毫秒级响应，处理每秒数千条行为日志。-推荐算法需兼顾准确性和多样性。要求：-说明数据流处理架构，推荐算法，以及离线与在线协同。答案与解析：数据流处理架构：1.消息队列（Kafka/Flink）：-用户行为日志接入Kafka，使用Flink实时处理并更新用户画像。2.特征存储（Redis/HBase）：-存储用户实时特征（如最近点击、收藏商品）。3.离线计算（Spark）：-每日计算用户画像（如协同过滤模型、用户标签）。推荐算法：-实时部分：-基于用户最近行为（如点击商品）进行召回（如Top-K相似用户商品）。-离线部分：-协同过滤（UserCF/ItemCF），矩阵分解（如SVD）。-融合：-将实时召回与离线排序结合（如LambdaMART）。离线与在线协同：-离线模型每日更新，在线模型实时微调（如使用在线学习）。-使用A/B测试评估推荐效果，动态调整策略。三、综合题（共2题，每题25分，总分50分）1.（25分）题目：假设你正在开发百度的AI写作助手，输入一段文本，输出流畅的续写内容。请：-设计模型输入输出，说明关键技术（如Transformer）。-分析如何提升续写质量（如避免重复、逻辑连贯）。答案与解析：模型输入输出：-输入：-原始文本（如用户输入的段落）。-文本长度限制（如200字）。-输出：-推荐的续写内容（如下一段话）。关键技术：-Transformer+Attention：-使用BERT/Transformer编码输入文本，通过Self-Attention捕捉上下文关系。-生成策略：-BeamSearch或GreedyDecoding生成续写内容。提升续写质量：-避免重复：-使用TokenMask或No-RepeatConstraint限制重复词语。-逻辑连贯：-引入外部知识图谱（如百度百科）增强事实一致性。2.（25分）题目：百度地图需要实时更新道路拥堵情况，请设计一个监控系统：-数据来源（如手机GPS数据、摄像头）。-处理流程（如异常检测、拥堵预测）。-如何优化系统鲁棒性（如数据去噪、容