百度算法工程师面试题目分析

2026年百度算法工程师面试题目分析一、编程基础与数据结构（共5题，每题6分，总分30分）题目1：给定一个数组`arr`和一个目标值`target`，请实现一个函数，找出数组中和为目标值的三元组，并返回所有不重复的三元组。要求：1.不能使用重复的三元组。2.时间复杂度尽可能低。3.示例输入：`arr=[-1,0,1,2]`，`target=0`，输出：`[[-1,0,1]]`。答案与解析：pythondefthree_sum(arr,target):arr.sort()n=len(arr)res=[]foriinrange(n):ifi>0andarr[i]==arr[i-1]:continueleft,right=i+1,n-1whileleft<right:total=arr[i]+arr[left]+arr[right]iftotal==target:res.append([arr[i],arr[left],arr[right]])whileleft<rightandarr[left]==arr[left+1]:left+=1whileleft<rightandarr[right]==arr[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnres解析：1.首先对数组排序，便于使用双指针法。2.遍历数组时，跳过重复的元素以避免重复三元组。3.使用左指针和右指针分别从当前元素的下一个位置和数组末尾开始遍历，根据和与目标值的比较调整指针位置。4.当找到满足条件的三元组时，移动指针并跳过重复值。题目2：请实现一个函数，判断一个字符串是否是有效的括号组合。例如：`"()"`、`"()[]{}"`有效，`"(]"`无效。要求：1.支持四种括号：`'()[]{}'`。2.时间复杂度O(n)，空间复杂度O(n)。答案与解析：pythondefisValid(s):stack=[]mapping={')':'(',']':'[','}':'{'}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：1.使用栈来存储未匹配的左括号。2.遍历字符串，遇到右括号时检查栈顶是否为对应的左括号。3.若不匹配或栈为空时直接返回False。4.最终栈为空则有效。题目3：给定一个链表，删除链表的倒数第n个节点，并返回链表的头节点。示例：`head=[1,2,3,4,5]`，`n=2`，输出：`[1,2,3,5]`。答案与解析：pythondefremoveNthFromEnd(head,n):dummy=ListNode(0,head)fast,slow=dummy,dummyfor_inrange(n+1):fast=fast.nextwhilefast:fast=fast.nextslow=slow.nextslow.next=slow.next.nextreturndummy.next解析：1.使用虚拟头节点简化边界处理。2.快指针先走n+1步，确保删除后链表长度不变。3.慢指针与快指针同步移动，当快指针到达末尾时，慢指针指向要删除节点的前一个节点。题目4：实现一个LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。要求：1.`get(key)`：返回键对应的值，若不存在返回-1。2.`put(key,value)`：插入或更新键值对，若缓存已满则删除最久未使用的键。3.时间复杂度O(1)。答案与解析：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.head,self.tail=ListNode(),ListNode()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:node=ListNode(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:lru=self.tail.prevself._remove_node(lru)delself.cache[lru.key]def_move_to_head(self,node):self._remove_node(node)self._add_node(node)def_add_node(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):prev,next=node.prev,node.nextprev.next=nextnext.prev=prev解析：1.使用双向链表和哈希表实现。链表维护最近使用顺序，哈希表快速访问。2.`get`操作将节点移动到头部，返回值。3.`put`操作插入新节点到头部，若超出容量则删除尾节点。题目5：给定一个非空二叉树，返回其最大深度。示例：`[3,9,20,null,null,15,7]`，最大深度为3。答案与解析：pythondefmaxDepth(root):ifnotroot:return0left=maxDepth(root.left)right=maxDepth(root.right)returnmax(left,right)+1解析：1.递归计算左右子树的最大深度，取较大值加1。2.基线条件为空节点深度为0。二、算法设计与优化（共5题，每题8分，总分40分）题目6：设计一个算法，找出数组中第k个最大的元素。示例：`nums=[3,2,1,5,6,4]`，`k=2`，输出：5。要求：1.不修改数组，时间复杂度O(nlogn)。2.优化为O(n)时间复杂度。答案与解析：O(nlogn)解法：pythondeffindKthLargest(nums,k):nums.sort(reverse=True)returnnums[k-1]解析：1.排序后取第k个元素。O(n)解法：pythondeffindKthLargest(nums,k):defpartition(left,right,pivot_index):pivot_value=nums[pivot_index]nums[pivot_index],nums[right]=nums[right],nums[pivot_index]store_index=leftforiinrange(left,right):ifnums[i]>pivot_value:nums[store_index],nums[i]=nums[i],nums[store_index]store_index+=1nums[right],nums[store_index]=nums[store_index],nums[right]returnstore_indexdefselect(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=random.randint(left,right)pivot_index=partition(left,right,pivot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnselect(left,pivot_index-1,k_smallest)else:returnselect(pivot_index+1,right,k_smallest)returnselect(0,len(nums)-1,k-1)解析：1.快速选择算法（Quickselect）基于快速排序的分区思想。2.随机选择枢轴以减少最坏情况概率。3.递归缩小范围直到找到第k大元素。题目7：给定一个字符串`s`，请找到其中最长的回文子串。示例：`s="babad"`，输出："bab"或"aba"。答案与解析：pythondeflongestPalindrome(s):ifnots:return""start,end=0,0foriinrange(len(s)):len1=expandAroundCenter(s,i,i)len2=expandAroundCenter(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]defexpandAroundCenter(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1解析：1.对每个字符尝试以中心扩展（奇数和偶数长度回文）。2.记录最大回文子串的起始和结束位置。题目8：设计一个算法，将一个非降序数组转换为二叉搜索树（BST），要求生成的BST尽可能平衡。示例：`nums=[1,2,3,4,5,6,7]`，输出：4/\26/\/\1357答案与解析：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefsortedArrayToBST(nums):ifnotnums:returnNonemid=len(nums)//2root=TreeNode(nums[mid])root.left=sortedArrayToBST(nums[:mid])root.right=sortedArrayToBST(nums[mid+1:])returnroot解析：1.递归构建BST，选择中间元素为根节点，左右子树分别由前半段和后半段递归生成。2.这样构建的树高度尽可能平衡。题目9：给定一个包含`n`个整数的数组，判断该数组是否可以划分为至少两个连续的子数组，且每个子数组的和相等。示例：`nums=[3,3,6,5,-2,2,3,1]`，输出：True（可划分为[3,3,6,5]和[-2,2,3,1]）。答案与解析：pythondefcanPartition(nums):total_sum=sum(nums)iftotal_sum%2!=0:returnFalsetarget=total_sum//2dp=[False](target+1)dp[0]=Truefornuminnums:forjinrange(target,num-1,-1):dp[j]=dp[j]ordp[j-num]returndp[target]解析：1.转化为子集和问题，判断是否存在两个子集和为`total_sum//2`。2.动态规划dp[j]表示是否可达和为j。题目10：实现一个算法，找出所有可能的括号组合，例如：`n=3`，输出：`["((()))","(()())","(())()","()(())","()()()"]`。要求：1.不使用递归。2.时间复杂度O(2^n)。答案与解析：pythondefgenerateParenthesis(n):result=[]defbacktrack(s,left,right):iflen(s)==2n:result.append(s)returnifleft<n:backtrack(s+'(',left+1,right)ifright<left:backtrack(s+')',left,right+1)backtrack('',0,0)returnresult解析：1.回溯法生成括号组合，左括号数量不超过n，右括号数量不超过左括号。2.剪枝避免无效路径。三、系统设计（共3题，每题10分，总分30分）题目11：设计一个微博系统，支持以下功能：1.用户发布微博（最多140字）。2.用户关注/取消关注其他用户。3.用户获取关注者的最新10条微博。要求：1.描述数据结构。2.说明核心算法。答案与解析：数据结构：1.User：用户表（id,name,followers,following）2.Tweet：微博表（id,user_id,content,timestamp）3.Follow：关注关系表（follower_id,followee_id）核心算法：1.发布微博：插入到`Tweet`表，索引`user_id`。2.关注/取消关注：更新`Follow`表。3.获取关注者微博：-按时间倒序获取`user_id`的最近10条微博。-可用Redis缓存热门用户微博。题目12：设计一个短链接系统，支持以下功能：1.将长链接转换为短链接。2.通过短链接跳转到对应的长链接。要求：1.描述数据结构。2.说明生成短链接的算法。答案与解析：数据结构：1.Link：链接表（id,long_url,short_url,created_at）2.短链接使用62进制编码（a-z,A-Z,0-9）。生成算法：1.长链接hash后生成唯一ID。2.ID转为62进制字