TWTR 面镜 给许多64-bit integers，要求查询的时候找出来与给定的int最多有2个bit不同的ints(求好思路）

Job Hunting Interview
, , ,
1

TWTR 面镜 给许多64-bit integers，要求查询的时候找出来与给定的int最多有2个bit不同的ints

2

说个一种思路：
给定的int可以变成 8 个 8-bit 的mask，这样只要累加每个mask的diff。
另外不确定题目要求，可否预处理所有的64-bit integers。如果可以，可以按照 8 bit mask 归类。
甚至可以拆成16个 4-bit 的mask。

4

没看出这个hashmap有什么优化啊？

6

补充一下，就是每个mask 做了 ^ 操作后可以check 是否等于0，然后用 Remove last bit 操作 A&(A-1)

参考

7

最多2个bit不同包括：
0位不同：1个，数字0
1位不同：64个，1,2,4,8,16…2^63
2位不同：63+62+61+…+1个=64*63/2=2016个
把这些数字放到HashSet里，O(1)
分别异或所求数字和那些64位整数，结果在HashSet说明参与异或的两个数字不同bit数小于等于2。O(N)
总共O(N)
方案2:
异或后求64bit中1的个数,小于等于2满足要求
O(N)*O(64)也是O(N)

8

HashSet 感觉不会是正解