求X与百万个数二进制最长公共前缀长度
哪些公司问过
答案要点
- 公共前缀长度 = X 异或 y 的前导零个数,相等时为 32
- 二进制 Trie 从高位插入,查询沿 X 的位下走,O(32),但节点多内存大
- 排序后二分,最长前缀只可能是 X 的前驱或后继,查询 O(log N)
- 按无符号数排序和比较
- 单次查询直接线性扫描 O(N) 即可
易错点
- 用有符号整数排序,高位为 1 的数排序错乱
- Trie 内存估算不足,百万级数据可能占用数百 MB
- X 与某个数相同时没有返回 32
面试官常见追问
- 为什么只需看前驱和后继?
- 如何求 X 与这些数的最大异或值?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。