百度算法工程师助理面试题集

2026年百度算法工程师助理面试题集一、编程基础与数据结构（3题，每题15分，共45分）1.题目：实现一个无重复字符的最长子串长度计算函数。给定一个字符串`s`，返回其最长无重复字符的子串的长度。例如，输入`s="abcabcbb"`，输出`3`（对应子串`"abc"`）。答案：pythondeflength_of_longest_substring(s:str)->int:char_map={}start=0max_length=0forendinrange(len(s)):ifs[end]inchar_map:start=max(start,char_map[s[end]]+1)char_map[s[end]]=endmax_length=max(max_length,end-start+1)returnmax_length解析：使用滑动窗口技术，`start`和`end`分别表示子串的左右边界。遍历字符串时，若当前字符已存在于`char_map`中，则将`start`移动到重复字符的下一个位置（`max(start,char_map[s[end]]+1)`）。每次更新`char_map`记录字符的最新索引，并计算当前窗口长度`end-start+1`与`max_length`的最大值。2.题目：给定一个包含`n`个整数的数组`nums`，返回所有和为`target`的唯一四元组（不重复的数字组合）。例如，输入`nums=[1,0,-1,0,-2,2]`，`target=0`，输出`[[-2,-1,1,2],[-2,0,0,2]]`。答案：pythondeffour_sum(nums,target):nums.sort()n=len(nums)res=[]foriinrange(n):ifi>0andnums[i]==nums[i-1]:continueforjinrange(i+1,n):ifj>i+1andnums[j]==nums[j-1]:continueleft,right=j+1,n-1whileleft<right:total=nums[i]+nums[j]+nums[left]+nums[right]iftotal==target:res.append([nums[i],nums[j],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解析：首先对数组排序，避免重复解。固定前两个数`nums[i]`和`nums[j]`，使用双指针`left`和`right`扫描剩余部分。若三数之和等于`target-nums[i]-nums[j]`，则记录解并跳过重复数字；若小于`target`，则左指针右移；否则右指针左移。3.题目：设计一个LRU（LeastRecentlyUsed）缓存系统，支持`get`和`put`操作。`get(key)`返回键对应的值，若不存在返回`-1`；`put(key,value)`插入或更新键值对，当缓存容量满时，移除最久未使用的键。答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache=OrderedDict()defget(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`维护键值对，其中`move_to_end`方法将访问的键移动到末尾，表示最近使用。`put`时若超出容量，则删除最早的键（`popitem(last=False)`）。LRU的核心是记录访问顺序，避免重复存储。二、算法设计（2题，每题20分，共40分）1.题目：设计一个算法，统计一个字符串中所有不同字母的所有子串的异或和。例如，输入`s="abc"`，异或和为`0^1^2^1^2^3^2^3^4=4`（所有子串异或的累积结果）。答案：pythondefxor_substring(s:str)->int:xor_sum=0foriinrange(len(s)):bit=ord(s[i])-ord('a')xor_sum^=(1<<bit)returnxor_sum解析：异或具有交换律和结合律，因此所有子串的异或可简化为原字符串中所有字符的异或。遍历字符串，将每个字符的ASCII值转换为`0-25`的数字，然后进行位异或操作。2.题目：给定一个由`'.'`（空地）、`'W'`（墙）和`'S'`（起始点）组成的二维网格，返回从起始点出发到达所有空地的最短路径数。路径只能上下左右移动，不能穿过墙。答案：pythonfromcollectionsimportdequedefshortest_path_all_empty(grid):n,m=len(grid),len(grid[0])start=Nonedirections=[(0,1),(1,0),(0,-1),(-1,0)]queue=deque()visited=[[False]mfor_inrange(n)]找起始点foriinrange(n):forjinrange(m):ifgrid[i][j]=='S':start=(i,j)queue.append((i,j,0))visited[i][j]=Truebreakifstart:breakwhilequeue:x,y,dist=queue.popleft()fordx,dyindirections:nx,ny=x+dx,y+dyif0<=nx<nand0<=ny<mandnotvisited[nx][ny]andgrid[nx][ny]=='.':visited[nx][ny]=Truequeue.append((nx,ny,dist+1))统计所有空地total=0foriinrange(n):forjinrange(m):ifgrid[i][j]=='.'andvisited[i][j]:total+=1returntotal解析：使用BFS从起始点向外扩散，记录每个空地是否可达。遍历完成后，统计所有标记为可达的空地数量。注意避免重复访问和穿过墙。三、系统设计（1题，30分）1.题目：设计一个高并发的短链接生成与解析系统。要求：（1）短链接长度不超过6位；（2）支持高并发请求；（3）解析时能快速定位原始长链接；（4）保证唯一性和幂等性。答案：pythonimporthashlibimportrandomfromthreadingimportLockclassShortLinkSystem:def__init__(self):self.lock=Lock()self.base62="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"self.map={}def_hash(self,long_url:str)->int:hash_obj=hashlib.md5(long_url.encode())returnint(hash_obj.hexdigest(),16)def_encode(self,num:int)->str:res=[]whilenum:res.append(self.base62[num%62])num//=62return''.join(res[::-1]).zfill(6)defgenerate(self,long_url:str)->str:withself.lock:num=self._hash(long_url)short_url=self._encode(num)whileshort_urlinself.map:num=(num+1)%(626)short_url=self._encode(num)self.map[short_url]=long_urlreturnf"/{short_url}"defresolve(self,short_url:str)->str:short_code=short_url.split('/')[-1]returnself.map.get(short_code