百度公司软件开发工程师招聘考试题

2026年百度公司软件开发工程师招聘考试题一、编程题（共3题，每题20分，总分60分）1.剑指Offer经典题：合并两个有序链表题目描述：给定两个排序链表的头节点`l1`和`l2`，请合并它们，并返回合并后的链表头节点。合并后的链表应保持有序。示例：-输入：`l1=[1,2,4]`,`l2=[1,3,4]`-输出：`[1,1,2,3,4,4]`要求：-不能使用额外的数组空间，需原地修改链表。-时间复杂度：O(m+n)，其中m和n分别为两个链表的长度。参考代码（Python）：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1:ListNode,l2:ListNode)->ListNode:dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<=l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextifl1:current.next=l1ifl2:current.next=l2returndummy.next答案解析：-使用虚拟头节点`dummy`简化边界处理。-通过循环遍历`l1`和`l2`，比较当前节点的值，将较小的节点链接到`current`，并移动对应的指针。-最后处理剩余的链表节点。-时间复杂度：O(m+n)，空间复杂度：O(1)。2.百度业务相关：LRU缓存机制题目描述：设计一个LRU（LeastRecentlyUsed）缓存系统，支持以下操作：-`get(key)`:获取键`key`对应的值。如果键存在，返回值并更新最近使用时间；如果不存在，返回-1。-`put(key,value)`:插入或更新键值对。如果键已存在，更新值并移动到最前面；如果键不存在，插入键值对，如果缓存已满，则删除最久未使用的键。要求：-使用哈希表和双向链表实现，哈希表用于快速查找，双向链表用于维护使用顺序。-时间复杂度：O(1)。参考代码（Python）：pythonclassDLinkedNode: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=DLinkedNode(),DLinkedNode()self.head.next=self.tailself.tail.prev=self.headdefget(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:node=DLinkedNode(key,value)self.cache[key]=nodeself._add_node(node)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]def_move_to_head(self,node:DLinkedNode):self._remove_node(node)self._add_node(node)def_add_node(self,node:DLinkedNode):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node:DLinkedNode):prev=node.prevnext=node.nextprev.next=nextnext.prev=prevdef_pop_tail(self)->DLinkedNode:res=self.tail.prevself._remove_node(res)returnres答案解析：-使用双向链表维护最近使用顺序，头节点为最近使用的节点，尾节点为最久未使用的节点。-哈希表存储键到链表节点的映射，实现O(1)时间复杂度的查找。-`get`操作将节点移动到头节点，`put`操作将新节点插入头节点，如果超出容量则删除尾节点。3.数据结构题：二叉树的层序遍历题目描述：给定一个二叉树，返回其层序遍历（即从上到下，从左到右遍历）。示例：-输入：`[3,9,20,null,null,15,7]`-输出：`[[3],[9,20],[15,7]]`要求：-使用队列实现，确保每层节点按从左到右的顺序输出。参考代码（Python）：pythonfromcollectionsimportdequefromtypingimportList,OptionalclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevelOrder(root:Optional[TreeNode])->List[List[int]]:ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult答案解析：-使用队列实现BFS（广度优先搜索），按层级遍历二叉树。-初始化队列并加入根节点，循环直到队列为空。-每次处理当前层级的所有节点，将子节点加入队列，并将当前层级的值添加到结果中。二、算法题（共3题，每题15分，总分45分）1.字符串处理题：最长回文子串题目描述：给定一个字符串`s`，找到其中最长的回文子串的长度。示例：-输入：`"babad"`-输出：`3`（"bab"或"aba"）要求：-时间复杂度：O(n²)，空间复杂度：O(1)。参考代码（Python）：pythondeflongestPalindrome(s:str)->int:ifnots:return0n=len(s)start,max_len=0,1foriinrange(n):奇数长度回文left,right=i,iwhileleft>=0andright<nands[left]==s[right]:ifright-left+1>max_len:start=leftmax_len=right-left+1left-=1right+=1偶数长度回文left,right=i,i+1whileleft>=0andright<nands[left]==s[right]:ifright-left+1>max_len:start=leftmax_len=right-left+1left-=1right+=1returnmax_len答案解析：-双指针法，分别处理奇数和偶数长度的回文。-固定中心点`i`，向两边扩展，直到不满足回文条件。-记录最长回文子串的起始位置和长度。2.数组处理题：三数之和题目描述：给定一个包含`n`个整数的数组`nums`，找出所有和为`0`的三元组。示例：-输入：`nums=[-1,0,1,2,-1,-4]`-输出：`[[-1,-1,2],[-1,0,1]]`要求：-解集不能包含重复的三元组。参考代码（Python）：pythondefthreeSum(nums:List[int])->List[List[int]]:nums.sort()n=len(nums)result=[]foriinrange(n):ifi>0andnums[i]==nums[i-1]:continuetarget=-nums[i]left,right=i+1,n-1whileleft<right:current_sum=nums[left]+nums[right]ifcurrent_sum==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-=1elifcurrent_sum<target:left+=1else:right-=1returnresult答案解析：-先对数组排序，便于跳过重复元素。-固定第一个数`nums[i]`，使用双指针`left`和`right`查找另外两个数，使得三数之和为`0`。-跳过重复的数，避免解集重复。3.数学与逻辑题：整数反转题目描述：给定一个32位的有符号整数`x`，返回`x`的反转。假设环境不允许存储64位整数（即`int`类型）。如果反转后的整数溢出，则返回`0`。示例：-输入：`x=123`-输出：`321`-输入：`x=-123`-输出：`-321`-输入：`x=120`-输出：`21`（因为末尾的`0`应当被忽略）要求：-不能使用字符串或除法。参考代码（Python）：pythondefreverse(x:int)->int:INT_MAX=231-1INT_MIN=-231result=0whilex!=0:pop=x%10x=x//10检查溢出ifresult>INT_MAX//10or(result==INT_MAX//10andpop>7):return0ifresult<INT_MIN//10or(result==INT_MIN//10andpop<-8):return0result=result10+popreturnresult答案解析：-使用循环模拟数字的反转，每次取末尾的数字并加到结果中。-注意检查反转后的数字是否溢出，即是否在`INT_MIN`到`INT_MAX`范围内。-忽略末尾的`0`，因为反转后不需要保留。三、系统设计题（共1题，25分）1.百度业务场景：设计短链接系统题目描述：设计一个短链接系统，将长链接转换为短链接，并支持以下功能：-用户输入长链接，系统生成短链接。-访问短链接时，系统解析为原始长链接。-支持高并发访问和快速解析。要求：-短链接应具有唯一性和可访问性。-系统需考虑分布式架构，支持水平扩展。-描述主要模块设计、数据结构、存储方式及负载均衡策略。参考设计思路：1.短链接生成：-使用哈希算法（如SHA-256）对长链接进行加密，并取其部分字符作为短链接。-为避免冲突，可添加随机前缀或使用数据库自增ID映射。2.数据存储：-使用Redis或MySQL存储短链接和长链接的映射关系。-Redis适合高并发场景，支持快速查找。3.分布式架