由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 一个实际碰到的问题
相关主题
Google电面被拒,郁闷中请教个面试题
问个Java的HashSet.contains的问题求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
一道算法题讨论一个题目
Java 面试关于map 和setcombinations 有没有 iterative的方法阿 ?
请教一道面试题L家的高频题merge k sorted arrays giving iterators求讨论!
问个最近面试里的题目Google电面
近来比较重复的问题, 求解刷了半天题
问道题,谁给个效率高点的解法Google的这一道题的最优解?继续求助@!
相关话题的讨论汇总
话题: 64话题: hamming话题: bit话题: integers话题: hashmap
进入JobHunting版参与讨论
1 (共1页)
p*****p
发帖数: 379
1
一个很大hashmap里存了64位的long类型hashcode,给定一个long,判断它和其他所有
hashcode是否存在hamming distance不超过3的子集,如果有,返回这些子集
最简单当然是把所有值都计算一遍,但那样太慢了
如果map是有序的,看起来只要找“附近”的值就行了,问题是如何找出这些值,我感
觉组合一下也不少了……
(注:hamming distance就是两个二进制之间不同位的数量之和,如101和110距离是2
l***i
发帖数: 1309
2
suppose you are looking for all 8-bit integer with hamming distance at most
3 with a given integer 10010010, then you can generate all possible 8-bit
integers and try each of them to see if it is in your hashmap.
For 64-bit integers, only (64 choose 3) positions can be different, for each
of the 3 positions you have at most 2^3 bit patterns, so you
only have (64 choose 3) * 2^3 = 10^6 integers to search in your hashmap,
should be
done in less than 1 sec.
p*****p
发帖数: 379
3
All right so that's 64*63*62*8 = 1999872
since the size of the map is not stable so seems to be better to compare the
size to that number, if it's less than that, seems the iteration method
could be faster and vice versa?

most
each

【在 l***i 的大作中提到】
: suppose you are looking for all 8-bit integer with hamming distance at most
: 3 with a given integer 10010010, then you can generate all possible 8-bit
: integers and try each of them to see if it is in your hashmap.
: For 64-bit integers, only (64 choose 3) positions can be different, for each
: of the 3 positions you have at most 2^3 bit patterns, so you
: only have (64 choose 3) * 2^3 = 10^6 integers to search in your hashmap,
: should be
: done in less than 1 sec.

h**6
发帖数: 4160
4
距离为0的数,C(64, 0) = 1个。
距离为1的数,C(64, 1) = 64个。
距离为2的数,C(64, 2) = 2016个。
距离为3的数,C(64, 3) = 41664个。
找找这43745个数在原图中是否存在即可。
l***i
发帖数: 1309
5
nice counting.

【在 h**6 的大作中提到】
: 距离为0的数,C(64, 0) = 1个。
: 距离为1的数,C(64, 1) = 64个。
: 距离为2的数,C(64, 2) = 2016个。
: 距离为3的数,C(64, 3) = 41664个。
: 找找这43745个数在原图中是否存在即可。

1 (共1页)
进入JobHunting版参与讨论
相关主题
Google的这一道题的最优解?继续求助@!请教一道面试题
一道面试题和解法(求指点).问个最近面试里的题目
热腾腾g电面 已挂近来比较重复的问题, 求解
Google onsite面试题全都答出来,能录取么?问道题,谁给个效率高点的解法
Google电面被拒,郁闷中请教个面试题
问个Java的HashSet.contains的问题求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
一道算法题讨论一个题目
Java 面试关于map 和setcombinations 有没有 iterative的方法阿 ?
相关话题的讨论汇总
话题: 64话题: hamming话题: bit话题: integers话题: hashmap