面试题库 › 算法 / 大模型 › 路灯覆盖所有房屋的最小半径

路灯覆盖所有房屋的最小半径

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:查找算法

哪些公司问过

字节跳动1

常见岗位:推荐搜索广告

答案要点

  1. 问题转化:答案 = 所有房屋到最近路灯距离的最大值
  2. 朴素做法每个房屋枚举所有路灯,O(n·m)
  3. 优化:路灯排序后对每个房屋二分,比较左右两个候选路灯
  4. 二分法复杂度 O((n+m) log m);也可两数组排序后双指针
  5. 边界:房屋在所有路灯左侧或右侧时只有一个候选,注意越界与溢出

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题