面试题库 › C++ / 后端 › 求X与百万个数二进制最长公共前缀长度

求X与百万个数二进制最长公共前缀长度

难度 ★★★在 1 场真实面经中被问到 方向:C++ / 后端考点:TopK与海量数据

哪些公司问过

阶跃星辰1

答案要点

  1. 公共前缀长度 = X 异或 y 的前导零个数,相等时为 32
  2. 二进制 Trie 从高位插入,查询沿 X 的位下走,O(32),但节点多内存大
  3. 排序后二分,最长前缀只可能是 X 的前驱或后继,查询 O(log N)
  4. 按无符号数排序和比较
  5. 单次查询直接线性扫描 O(N) 即可

易错点

面试官常见追问

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

相关面试题