2026年百度算法工程师面试题目及答案全解析

2026年百度算法工程师面试题目及答案全解析一、编程基础（共5题，每题6分，总分30分）1.题目（6分）：实现一个函数，输入一个非负整数`n`，返回`n`的各位数字之和。例如，输入`123`，返回`6`（1+2+3）。要求不使用内置的字符串或列表操作，仅使用数学方法。答案：pythondefsum_of_digits(n):total=0whilen>0:total+=n%10n=n//10returntotal解析：通过模除`10`获取最后一位数字，加到`total`中，然后整除`10`去掉最后一位，循环直到`n`为`0`。该方法避免使用字符串或列表，符合数学操作要求。2.题目（6分）：给定一个排序数组，实现二分查找算法，返回目标值`target`的索引。如果不存在，返回`-1`。要求时间复杂度为`O(logn)`。答案：pythondefbinary_search(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=left+(right-left)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1解析：利用数组已排序的特性，通过不断缩小搜索范围来查找目标值。每次将中间值与目标比较，调整左右指针，直到找到或范围为空。3.题目（6分）：实现一个函数，输入一个链表头节点`head`，返回其反转后的链表头节点。要求原地反转，不使用额外空间。答案：pythondefreverse_linked_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：通过迭代方式，逐个节点反转`next`指针。使用`prev`和`next_node`辅助，避免断链。4.题目（6分）：给定一个字符串`s`，判断它是否是有效的括号字符串（只包含`'('`和`')'`，左右括号匹配）。要求时间复杂度为`O(n)`。答案：pythondefis_valid_parentheses(s):stack=[]forcharins:ifchar=='(':stack.append(char)elifchar==')':ifnotstackorstack[-1]!='(':returnFalsestack.pop()returnnotstack解析：使用栈结构，遇到`'('`压入，遇到`')'`时检查栈顶是否为`'('`并弹出。最后栈为空则有效。5.题目（6分）：实现一个函数，输入一个正整数`n`，返回`1`到`n`的所有斐波那契数的和。斐波那契数列定义：`F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)`。答案：pythondeffibonacci_sum(n):ifn<=0:return0a,b=1,1total=aforiinrange(2,n+1):a,b=b,a+btotal+=breturntotal解析：使用迭代计算斐波那契数，并累加。避免递归导致栈溢出，时间复杂度为`O(n)`。二、算法设计（共4题，每题7分，总分28分）1.题目（7分）：设计一个算法，输入一个包含重复元素的数组，返回所有不重复的三元组，其中三元组的元素之和等于给定的目标值`target`。例如，输入`[-1,0,1,2,-1,-4]`和`0`，返回`[[-1,-1,2],[-1,0,1]]`。答案：pythondefthree_sum(nums,target):nums.sort()n=len(nums)result=[]foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:result.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-=1returnresult解析：先排序数组，然后固定一个数，使用双指针在剩余部分查找和为`target-nums[i]`的二元组。注意去重避免重复三元组。2.题目（7分）：设计一个算法，输入一个包含`0`和`1`的二维矩阵，返回其中最大的全`1`正方形的大小。例如，输入`[[1,0,1,0,0],[1,0,1,1,1],[1,1,1,1,1],[1,0,0,1,0]]`，返回`4`（一个`2x2`的正方形）。答案：pythondefmaximal_square(matrix):ifnotmatrixornotmatrix[0]:return0m,n=len(matrix),len(matrix[0])dp=[[0]nfor_inrange(m)]max_side=0foriinrange(m):forjinrange(n):ifmatrix[i][j]=='1':ifi==0orj==0:dp[i][j]=1else:dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1max_side=max(max_side,dp[i][j])returnmax_sidemax_side解析：动态规划解法，`dp[i][j]`表示以`(i,j)`为右下角的最大全`1`正方形边长。状态转移方程为`dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1`。3.题目（7分）：设计一个算法，输入一个字符串`s`和一个字典`word_dict`，判断`s`是否可以由字典中的单词组合而成（可以重复使用字典中的单词）。例如，输入`s="leetcode"`和`word_dict=["leet","code"]`，返回`True`。答案：pythondefword_break(s,word_dict):word_set=set(word_dict)dp=[False](len(s)+1)dp[0]=Trueforiinrange(1,len(s)+1):forjinrange(i):ifdp[j]ands[j:i]inword_set:dp[i]=Truebreakreturndp[len(s)]解析：动态规划解法，`dp[i]`表示`s[:i]`是否可以由字典单词组成。遍历每个位置，检查前缀是否在字典中且`dp[j]`为`True`。4.题目（7分）：设计一个算法，输入一个字符串`s`，返回其所有可能的子集（包括空集）。例如，输入`s="abc"`，返回`["","a","b","ab","c","ac","bc","abc"]`。答案：pythondefsubsets(s):s=sorted(s)result=[]subset=[]defbacktrack(index):result.append("".join(subset))foriinrange(index,len(s)):ifi>indexands[i]==s[i-1]:continuesubset.append(s[i])backtrack(i+1)subset.pop()backtrack(0)returnresult解析：回溯算法，通过递归构建所有子集。使用`index`避免重复子集（如连续字符相同时跳过）。三、系统设计（共3题，每题8分，总分24分）1.题目（8分）：设计一个简单的URL短链接服务。输入一个长URL，返回一个短URL，并支持通过短URL查询原始长URL。要求支持高并发访问。答案：1.短URL生成：-使用哈希函数（如MD5或SHA-256）对长URL进行哈希，取前`6`位作为短码（如`a1b2c3`）。-使用自增ID或分布式ID生成器（如Twitter的Snowflake算法）生成唯一短码。-避免冲突：使用随机数或前缀树（Trie）处理哈希碰撞。2.存储：-使用Redis或Memcached存储短码与长URL的映射，支持快速读写。-数据库（如MySQL）备份持久化，防止服务重启丢失数据。3.高并发：-使用负载均衡（如Nginx）分发请求。-设置合理的缓存过期时间（如`300s`），减少数据库访问。4.示例：-输入：`/long/path`-生成短URL：`https://short.ly/a1b2c3`-查询：通过`a1b2c3`返回原始长URL。解析：核心在于高效映射和快速访问。哈希函数+缓存（Redis）是常用方案，Snowflake算法可保证唯一性。负载均衡和缓存策略保证高并发。2.题目（8分）：设计一个实时新闻推荐系统，输入用户实时浏览的新闻ID列表，返回每个用户可能感兴趣的新闻推荐列表。要求支持个性化推荐和实时更新。答案：1.数据结构：-用户行为流：使用Kafka或RabbitMQ收集实时用户行为（如点击、停留时间）。-用户画像：存储用户历史兴趣（如标签、分类）。2.推荐算法：-协同过滤：根据相似用户的历史行为推荐（如User-BasedCF）。-内容推荐：基于新闻内容标签（如TF-IDF）匹配用户兴趣。-实时更新：使用滑动窗口统计用户最近行为，动态调整推荐权重。3.系统架构：-流处理：使用Flink或SparkStreaming处理实时数据。-推荐服务：微服务架构，定时或按需更新推荐结果。-缓存：Redis存储热门推荐，加速响应。4.示例：-用户点击`新闻A`、`新闻C`，系统根据历史和实时行为推荐`新闻B`。解析：实时推荐结合了流处理和机器学习。关键在于快速处理用户行为并动态调整推荐策略。分布式流处理框架和缓存是性能保障。3.题目（8分）：设计一个分布式计数器服务，支持多个客户端并发读写计数，要求高可用、高并发、分布式一致性。答案：1.数据结构：-使用Redis的`INCR`命令实现原子计数。-若需持久化，使用Redis的RDB/AOF或分布式数据库（如TiDB）。2.分布式一致性：-使用分布式锁（如ZooKeeper或RedisLock）确保写操作互斥。-集群部署：多节点Redis集群或分片（Sharding）提高并发。3.高可用：-主从复制：配置Redis主节点和从节点，主节点故障时自动切换。-负载均衡：使用Keepalived或Nginx实现服务高可用。4.示例：-客户端A调用`incr(counter)`，计数器加`1`。-客户端B同样调用，计数器最终为`2`。解析：Redis的原子操作是关键。集群和主从复制保证高可用，分布式锁处理一致性。分片可进一步扩展并发能力。四、综合应用（共2题，每题10分，总分20分）1.题目（10分）：设计一个广告投放系统，输入用户ID、广告ID和上下文信息（如时间、地点），返回给用户最合适的广告进行展示。要求考虑用户兴趣、广告效果和多样性。答案：1.数据结构：-用户兴趣：使用向量表示用户偏好（如Embedding）。-广告标签：存储广告属性（如行业、目标人群）。2.推荐算法：-相似度匹配：计算用户与广告的相似度（如余弦相似度）。-Bandit算法：结合探索（随机展示）与利用（高点击广告）。-多样性：限制同类广告展示频率，避免用户疲劳。3.系统架构：-实时计算：使用DLV或Flink进行在线相似度计算。-广告池：存储所有广告，按优先级排序。-缓存：Redis缓存用户画像和广告匹配结果。4.示例：-用户`U1`偏好科技，展示`广告X`（科技类）；若`U1`近期点击过`广告Y`（金融类），适当展示`广告Y`。解析：广告推荐结合了协同过滤和Bandit算法。实时计算和缓存是性能关键，多样性策略提升用户体验。2.题目（10分）：设计一个智能问答系统，输入用户自然语言问题，返回最相关的答案。要求支持多轮对话和上下文理解。答案：1.数据结构：-知识库：存储FAQ、文档（如Elasticsearch索引）。-上下文：使用LSTM或Transformer存储对话历史。2.核心算法：-NLU：使用BERT或spaCy进行意图识别和实体抽取。-