Baidu 面试问题

Baidu 面试重点考察内容

Baidu 常见面试问题

• 给定一个整数数组，找到最长递增子序列。
  好回答应覆盖

  • 动态规划解法：O(n^2)时间，O(n)空间
  • 二分查找优化：维护递增序列，O(n log n)时间
  • 注意处理空数组和单元素数组

  查看范例答案

  最长递增子序列（LIS）问题常用动态规划解决。定义dp[i]为以nums[i]结尾的最长递增子序列长度，转移方程为dp[i] = max(dp[j] + 1) for j < i and nums[j] < nums[i]。初始dp[i]=1，答案为max(dp)。时间复杂度O(n^2)，空间O(n)。优化方法：使用二分查找维护一个tail数组，表示长度为i+1的递增子序列的最小末尾值。遍历每个数，在tail中二分查找第一个大于等于当前数的位置，替换之。最终tail的长度即为LIS长度。时间复杂度O(n log n)。注意处理空数组。

  def lengthOfLIS(nums):
      import bisect
      dp = []
      for x in nums:
          i = bisect.bisect_left(dp, x)
          if i == len(dp):
              dp.append(x)
          else:
              dp[i] = x
      return len(dp)

• 实现一个检测有向图中环的函数。
  好回答应覆盖

  • DFS + 访问标记（0/1/2）检测后向边
  • 拓扑排序（Kahn算法）检测环
  • 注意处理多个连通分量

  查看范例答案

  检测有向图中环的常见方法有DFS和拓扑排序。DFS方法：使用三种状态标记节点——0未访问，1正在访问（在递归栈中），2已访问完成。遍历每个节点，若当前节点状态为1，则存在环。拓扑排序（Kahn算法）：计算每个节点的入度，将入度为0的节点入队，依次出队并减少其邻居的入度，若最终队列处理的节点数等于总节点数则无环，否则有环。两种方法时间复杂度均为O(V+E)。注意图可能不连通，需要遍历所有节点。

  def hasCycle(graph):
      # graph: adjacency list, nodes 0..n-1
      n = len(graph)
      state = [0] * n  # 0=unvisited, 1=visiting, 2=visited
      def dfs(u):
          state[u] = 1
          for v in graph[u]:
              if state[v] == 1:
                  return True
              if state[v] == 0 and dfs(v):
                  return True
          state[u] = 2
          return False
      for i in range(n):
          if state[i] == 0 and dfs(i):
              return True
      return False

• 设计一个类似百度的实时搜索自动补全系统。
  好回答应覆盖

  • 前端：用户输入实时发送请求，节流/防抖
  • 后端：Trie树存储搜索历史，三元组或前缀匹配
  • 缓存：热门查询缓存（Redis），冷数据持久化

  查看范例答案

  设计一个实时搜索自动补全系统，类似于百度的搜索建议。前端通过防抖减少请求，后端使用Trie存储查询词及其频率。每个节点保存前缀的热门建议（前k个）。数据来源是搜索日志，定期训练模型或更新。为处理高并发，引入Redis缓存热点查询，并采用分布式Trie分片。数据流：用户输入->防抖->发送HTTP请求->负载均衡->查询服务->首先查Redis缓存，未命中则查Trie，返回结果并缓存。扩展性：通过增加Trie分片节点和缓存节点来水平扩展。

• 为高流量网站设计一个分布式缓存。
  好回答应覆盖

  • 缓存一致性：缓存与数据库同步（写直达/写回）
  • 缓存策略：LRU、LFU、TTL
  • 高可用：一致性哈希、副本、故障转移

  查看范例答案

  设计一个分布式缓存，核心是数据分片、一致性和高可用。使用一致性哈希将键分布到多个节点，加虚拟节点平衡负载。缓存策略采用LRU和TTL。写操作使用Write-Through确保缓存与数据库一致。为防单点故障，每个节点配置主从复制，自动故障转移。缓存穿透问题使用布隆过滤器处理；缓存击穿使用互斥锁或热点数据不过期；缓存雪崩通过TTL随机化和本地缓存缓解。系统监控关键指标：命中率、延迟、节点健康状态。

• 解释 L1 和 L2 正则化的区别以及何时使用它们。
  好回答应覆盖

  • L1 = Lasso: 稀疏解，特征选择，导数不连续
  • L2 = Ridge: 非稀疏，防止过拟合，导数连续
  • L1适用于高维稀疏特征，L2适用于特征交互

  查看范例答案

  L1正则化（Lasso）在损失函数中加入权重的绝对值之和，导致解稀疏，即许多权重变为0，自动特征选择。L2正则化（Ridge）加入权重的平方和，使权重趋于小值但非零，防止过拟合。L1的导数不连续，导致在0处有角点解；L2处处可导，计算更方便。选择上：当特征数量远大于样本数，或希望模型可解释性强时，用L1；当特征之间相关性高，或希望保留所有特征时，用L2。也可结合两者（Elastic Net）。实际中通过交叉验证选择正则化参数。

• 你如何处理分类问题中的类别不平衡？
  好回答应覆盖

  • 重采样：过采样（SMOTE）和欠采样
  • 代价敏感学习：调整样本权重
  • 集成方法：EasyEnsemble，BalanceCascade

  查看范例答案

  处理类别不平衡常用方法：1）数据层面：过采样（如SMOTE生成合成样本）或欠采样（随机删除多数类样本）。SMOTE在少数类样本之间插值，避免过拟合。欠采样可能丢失重要信息。2）算法层面：使用代价敏感学习，在损失函数中给少数类错误分类分配更高权重。如逻辑回归中设置class_weight='balanced'。3）集成方法：如EasyEnsemble，从多数类中抽样子集训练多个模型，然后投票。4）评价指标：不适用准确率，应使用精确率、召回率、F1-score、AUC等。另外，也可以使用异常检测方法（如Isolation Forest）处理极度不平衡。

• 讲述一次你在紧迫的截止日期下交付项目的经历。
  好回答应覆盖

  • 情境：项目截止日期临近，关键功能未完成
  • 任务：确保核心功能交付，质量不受损
  • 行动：优先级排序，加班，寻求帮助，简化测试

  查看范例答案

  在之前工作中，我曾负责一个搜索引擎的索引更新模块，客户要求两周内上线，但开发过程中遇到数据同步问题，导致进度滞后。我立即组织团队评估当前进度，将需求分为P0（必须完成）和P1（可延期）。我与产品经理沟通，同意推迟非核心功能。同时，我协调一名后端工程师协助处理数据管道，自己则集中解决核心算法。我们加班加点，每天站会同步进展，并增加了自动化测试保证质量。最终按时交付了核心功能，客户满意。事后进行了复盘，提出了改进流程：建立Buffer时间，预留应急资源。

• 描述一次你与团队成员意见分歧以及如何解决的经历。
  好回答应覆盖

  • 情境：项目技术选型分歧，一方选微服务，一方选单体
  • 任务：达成共识，不破坏团队关系
  • 行动：组织讨论会，列举利弊，原型验证，投票决定

  查看范例答案

  在一次设计新服务架构时，我与一位同事对使用微服务还是单体架构产生分歧。他认为微服务更灵活，我担心运维复杂度。我提议召开架构评审会，双方提前准备优缺点对比表。会上我们深入讨论了业务规模、团队能力、未来扩展。我建议做一个快速原型验证微服务的可行性，结果发现对于当前团队，微服务导致接口调用复杂且调试困难。最终团队投票决定采用单体起步，并为未来拆分预留接口。事后我与该同事保持良好关系，并约定定期重新评估架构。这次经历让我认识到，用数据和实验说话比单纯争论更有效。

准备技巧

• 掌握数据结构和算法，重点关注动态规划、树和图，因为它们在百度面试中很常见。
• 练习分布式系统的系统设计，尤其是在搜索、推荐和大规模数据处理的背景下。
• 复习核心 ML 概念：监督学习 vs 无监督学习、过拟合、特征选择和模型评估指标。
• 准备好清晰解释你的思维过程，并在白板或共享编辑器上编写无错误的代码。
• 研究百度的产品（如百度搜索、Apollo、DuerOS），以了解他们面临的技术挑战。

常见问题