2026年百度算法工程师面试技巧及答案详解

2026年百度算法工程师面试技巧及答案详解一、编程基础（5题，每题10分，共50分）1.题目：实现一个函数，输入一个正整数`n`，返回`n`的阶乘。要求：不能使用递归，时间复杂度O(n)。答案：pythondeffactorial(n):result=1foriinrange(2,n+1):result=ireturnresult解析：使用循环计算阶乘，避免递归导致的栈溢出问题。时间复杂度为O(n)，空间复杂度为O(1)。2.题目：给定一个字符串`s`，统计其中出现频率最高的字符及其出现次数。答案：pythonfromcollectionsimportdefaultdictdeftop_frequent_char(s):freq=defaultdict(int)forcharins:freq[char]+=1max_char=max(freq,key=freq.get)returnmax_char,freq[max_char]解析：使用哈希表统计字符频率，然后找到最大频率的字符。时间复杂度为O(n)，空间复杂度为O(k)，k为字符集大小。3.题目：实现快速排序算法，并分析其时间复杂度。答案：pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)解析：快速排序的平均时间复杂度为O(nlogn)，最坏情况为O(n^2)。空间复杂度为O(logn)（递归栈）。4.题目：实现一个无重复数字的数组，返回所有可能的子集（幂集）。答案：pythondefsubsets(nums):result=[]subset=[]defbacktrack(start):result.append(subset.copy())foriinrange(start,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult解析：使用回溯法生成所有子集，时间复杂度为O(2^n)，空间复杂度为O(n)。5.题目：给定一个链表，反转其链表节点。答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev解析：使用三指针法反转链表，时间复杂度为O(n)，空间复杂度为O(1)。二、数据结构与算法（5题，每题10分，共50分）6.题目：设计一个LRU（最近最少使用）缓存，支持get和put操作。答案：pythonfromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity:int):self.cache=OrderedDict()self.capacity=capacitydefget(self,key:int)->int:ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]defput(self,key:int,value:int)->None:ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)解析：使用`OrderedDict`实现LRU缓存，get操作将元素移动到末尾，put操作先移动已存在的元素，如果超出容量则删除最旧的元素。7.题目：给定一个整数数组，判断是否存在三个元素a,b,c，使得a+b+c=0。返回所有不重复的三元组。答案：pythondefthree_sum(nums):nums.sort()result=[]n=len(nums)foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0: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<0:left+=1else:right-=1returnresult解析：排序后使用双指针法，时间复杂度为O(n^2)，空间复杂度为O(1)。8.题目：给定一个二叉树，判断其是否是平衡二叉树（左右子树高度差不超过1）。答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balanced=check(node.left)right_height,right_balanced=check(node.right)returnmax(left_height,right_height)+1,left_balancedandright_balancedandabs(left_height-right_height)<=1returncheck(root)[1]解析：后序遍历计算每个节点的高度，同时判断平衡性，时间复杂度为O(n)，空间复杂度为O(h)，h为树的高度。9.题目：实现二叉树的层序遍历（按层次从左到右）。答案：pythondeflevel_order(root):ifnotroot:return[]result=[]queue=[root]whilequeue:level=[]for_inrange(len(queue)):node=queue.pop(0)level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(level)returnresult解析：使用队列实现BFS（广度优先搜索），时间复杂度为O(n)，空间复杂度为O(n)。10.题目：给定一个字符串，判断其是否是有效的括号组合（如"()[]{}"）。答案：pythondefisValid(s):stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse'#'ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack解析：使用栈匹配括号，时间复杂度为O(n)，空间复杂度为O(n)。三、系统设计（3题，每题15分，共45分）11.题目：设计一个短链接服务（如tinyurl），要求：1.输入长链接，返回短链接；2.输入短链接，能查询到原始长链接；3.支持高并发访问。答案：1.短链接生成：使用Base62编码（a-z,A-Z,0-9）将ID映射为短链接，如`/a1b2`；2.存储：使用Redis存储短链接与长链接的映射，key为短链接，value为长链接；3.高并发：使用分布式锁或CAS机制防止写入冲突；4.分布式部署：部署多个节点，使用负载均衡（如Nginx）分发请求。解析：核心是哈希映射和分布式缓存，Base62减少短链接长度，Redis保证高性能。12.题目：设计一个实时推荐系统（如淘宝商品推荐），要求：1.输入用户ID和商品ID，返回推荐商品；2.支持个性化推荐（基于用户历史行为）；3.支持实时更新（用户行为变化时立即更新推荐结果）。答案：1.数据存储：使用MongoDB存储用户行为日志（用户ID、商品ID、时间戳）；2.特征提取：使用Flink或SparkStreaming实时处理用户行为，计算用户兴趣向量；3.推荐算法：协同过滤（基于用户或商品），结合实时特征更新推荐结果；4.缓存：Redis缓存用户推荐结果，减少计算开销。解析：实时推荐系统需要结合流处理和推荐算法，Redis保证低延迟。13.题目：设计一个高可用新闻推荐系统（如腾讯新闻），要求：1.支持全球用户访问