百度技术研发岗位面试技巧与面试题集

2026年百度技术研发岗位面试技巧与面试题集一、编程能力测试（5题，每题10分，共50分）1.题目：实现一个函数，输入一个正整数`n`，返回`n`的二进制表示中`1`的个数。例如，输入`5`（二进制为`101`），返回`2`。要求：-时间复杂度O(logn)-不能使用内置函数（如Python的`bin()`或JavaScript的`toString(2)`）答案：pythondefcount_bits(n):count=0whilen:count+=n&1n>>=1returncount解析：通过位运算`n&1`获取最低位是否为`1`，然后右移一位继续统计。时间复杂度为O(logn)，空间复杂度为O(1)。2.题目：给定一个字符串`s`，找到其中不重复的最长子串的长度。例如，输入`"abcabcbb"`，返回`3`（最长子串为`"abc"`）。要求：-时间复杂度O(n)-不能使用哈希表以外的数据结构答案：pythondeflength_of_longest_substring(s):left=0max_len=0seen={}forright,charinenumerate(s):ifcharinseenandseen[char]>=left:left=seen[char]+1seen[char]=rightmax_len=max(max_len,right-left+1)returnmax_len解析：使用滑动窗口技术，`left`和`right`指针分别表示子串的左右边界。通过字典`seen`记录字符上一次出现的位置，如果重复则移动`left`。时间复杂度为O(n)，空间复杂度为O(1)（假设字符集固定）。3.题目：实现一个LRU（LeastRecentlyUsed）缓存，支持`get`和`put`操作。缓存容量为`capacity`。要求：-`get(key)`返回键对应的值，如果不存在返回`-1`-`put(key,value)`将键值对插入缓存，如果已存在则更新值，如果超出容量则删除最久未使用的项答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：使用字典`cache`存储键值对，列表`order`记录访问顺序。`get`操作时移动键到末尾表示最近使用，`put`操作时先删除最久未使用的项（如果超出容量）。4.题目：给定一个链表，判断是否为回文链表。例如，输入`1->2->2->1`，返回`True`。要求：-时间复杂度O(n)-空间复杂度O(1)答案：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefis_palindrome(head:ListNode)->bool:ifnotheadornothead.next:returnTrue找到中点slow=headfast=headwhilefastandfast.next:slow=slow.nextfast=fast.next.next反转后半部分prev=Nonewhileslow:temp=slow.nextslow.next=prevprev=slowslow=temp对比前后半部分left,right=head,prevwhileright:ifleft.val!=right.val:returnFalseleft=left.nextright=right.nextreturnTrue解析：通过快慢指针找到中点，反转后半部分链表，然后对比前后半部分是否相同。时间复杂度为O(n)，空间复杂度为O(1)。5.题目：实现快速排序算法，不使用递归。要求：-使用迭代方式实现-输入一个数组，返回排序后的数组答案：pythondefquick_sort_iterative(arr):stack=[(0,len(arr)-1)]whilestack:left,right=stack.pop()ifleft>=right:continuepivot=arr[right]i=left-1forjinrange(left,right):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[right]=arr[right],arr[i+1]stack.append((left,i))stack.append((i+2,right))returnarr解析：使用栈模拟递归，每次选择右边界作为基准，分区后继续处理左右子数组。时间复杂度为O(nlogn)，空间复杂度为O(logn)。二、系统设计（2题，每题25分，共50分）1.题目：设计一个高并发的短链接系统（如`tinyurl`）。要求：-输入长链接，返回短链接-支持高并发访问-短链接应唯一且可快速生成答案：plaintext1.基础架构：-使用分布式缓存（如Redis）存储短链接与长链接的映射-短链接使用Base62编码（a-z,A-Z,0-9）降低长度-每个节点分配一段Base62编码空间，避免冲突2.高并发处理：-使用熔断器（如Hystrix）防止雪崩效应-短链接生成使用分布式锁或CAS操作保证唯一性-异步处理请求，提高吞吐量3.数据一致性：-短链接生成后写入Redis，并同步到分布式数据库（如MongoDB）-使用事务或最终一致性方案处理写入失败解析：-Base62编码：将ID转换为短字符串，如`1`→`a`，`62`→`az`-分布式缓存：Redis高性能读写，避免数据库压力-并发控制：分布式锁或CAS保证ID唯一性2.题目：设计一个实时推荐系统，输入用户行为日志，输出个性化推荐结果。要求：-支持百万级用户实时行为接入-推荐结果基于协同过滤或深度学习模型-系统需可水平扩展答案：plaintext1.架构设计：-数据采集层：使用Kafka或Pulsar收集用户行为日志-处理层：-实时计算：Flink或SparkStreaming进行用户画像和相似度计算-离线计算：每日批处理历史数据训练推荐模型-推荐服务：使用微服务架构，按用户隔离模型，支持热加载2.核心算法：-协同过滤：基于用户的物品相似度或物品的用户相似度-深度学习：使用DNN或GNN捕捉用户隐式反馈3.扩展性：-数据库分片：用户表按地域或用户ID分片-推荐服务限流：使用令牌桶算法防止过载解析：-实时性：Flink可处理1万+QPS的行为日志-推荐模型：结合离线（LRU模型）和在线（实时相似度）提升效果-扩展性：微服务按用户隔离，避免单点过载三、算法与数据结构（3题，每题25分，共75分）1.题目：给定一个无序数组，找到其中第`k`大的元素。例如，输入`[3,2,1,5,6,4]`，`k=2`，返回`5`。要求：-时间复杂度O(nlogk)-不能使用排序答案：pythonimportheapqdeffind_kth_largest(nums,k):returnheapq.nlargest(k,nums)[-1]解析：使用堆（Python的`heapq`）维护大小为`k`的最小堆，时间复杂度为O(nlogk)，空间复杂度为O(k)。2.题目：实现一个Trie（前缀树），支持插入和查询操作。要求：-支持插入字符串-支持前缀查询（返回所有以该前缀开头的字符串）答案：pythonclassTrieNode:def__init__(self):self.children={}self.is_end=FalseclassTrie:def__init__(self):self.root=TrieNode()definsert(self,word:str)->None:node=self.rootforcharinword:ifcharnotinnode.children:node.children[char]=TrieNode()node=node.children[char]node.is_end=Truedefsearch(self,word:str)->bool:node=self._find(word)returnnodeisnotNoneandnode.is_enddefstarts_with(self,prefix:str)->List[str]:node=self._find(prefix)ifnotnode:return[]returnself._dfs(node,prefix)def_find(self,prefix:str):node=self.rootforcharinprefix:ifcharnotinnode.children:returnNonenode=node.children[char]returnnodedef_dfs(self,node,prefix):res=[]ifnode.is_end:res.append(prefix)forchar,childinnode.children.items():res.extend(self._dfs(child,prefix+char))returnres解析：Trie树通过节点和子节点映射实现，`is_end`标记单词结束。前缀查询通过DFS遍历所有子路径。3.题目：设计一个分布式任务队列，支持任务分片和优先级调度。要求：-任务可动态分片，例如大文件上传分块处理-高优先级任务抢占低优先级任务资源-可恢复性（任务失败后重新分配）答案：plaintext1.核心组件：-任务队列：使用Redis或Kafka分区存储任务-调度器：按优先级（如CPU/内存占用率）调度任务-监控：Prometheus+Grafana监控队列状态2