i******w
发帖数: 407 | 1 4 arrays, 100K randomly generated int in each array. What's the quickest way
to get the intersection?
我说用hash，结果面试官说不对。
大家有什么想法? |
r*******n
发帖数: 3020 | 2 难道用map reduce?
def map_function(array):
for i, each in enumerate(array):
EmitKeyValue((i,each), 1) // use index and array[index] as key
// to make duplicate elements unique
def reduce_function(key, iterator v):
if sum(v)==4:
EmitKeyValue(key) //this is the key in 4 arrays.
way
【在 i******w 的大作中提到】
: 4 arrays, 100K randomly generated int in each array. What's the quickest way
: to get the intersection?
: 我说用hash，结果面试官说不对。
: 大家有什么想法?
|
y****a
发帖数: 15 | 3 我觉得最快是用bit array 存4组数，
然后AND |
z*********8
发帖数: 2070 | 4 首先intersection的定义是什么？ 任何两个数组有， 还是4个数组都得有？
【在 y****a 的大作中提到】
: 我觉得最快是用bit array 存4组数，
: 然后AND
|
l*n
发帖数: 529 | 5 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
【在 y****a 的大作中提到】
: 我觉得最快是用bit array 存4组数，
: 然后AND
|
r*******n
发帖数: 3020 | 6 bitmap 也是hash方法
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
|
i******w
发帖数: 407 | 7 4个数组都得有
【在 z*********8 的大作中提到】
: 首先intersection的定义是什么？ 任何两个数组有， 还是4个数组都得有？
|
i******w
发帖数: 407 | 8 我就是用hash这么答的，人说不满意。
哪位大牛能把bitmap解释一下吗？
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
|
i******w
发帖数: 407 | 9 EmitKeyValue 是啥语言啊，python里不应该是 yield 吗？
【在 r*******n 的大作中提到】
: 难道用map reduce?
: def map_function(array):
: for i, each in enumerate(array):
: EmitKeyValue((i,each), 1) // use index and array[index] as key
: // to make duplicate elements unique
: def reduce_function(key, iterator v):
: if sum(v)==4:
: EmitKeyValue(key) //this is the key in 4 arrays.
:
:
|
e*******8
发帖数: 94 | 10 我猜是不是因为题目里有假设数据是randomly generated？觉得可以把输入分到若干个
buckets，然后每个bucket找intersection？基本上就是bucket sorting的想法。不过
把数字分到bucket里其实也就是hashing。。。 |
|
|
s*******z
发帖数: 83 | 11 所有数字看做字符串, 用Trie, 最后一遍数所有叶子count为4的那些就是交集.
貌似这样只用过一遍数字 |
s********u
发帖数: 1109 | 12 嗯，如果硬上的话,bitset的范围就是2^32也就是GB级别的内存。
但也不是没有办法解决，就是类似bucket sort那种想法，把2^32分割成几个部分，每
次只统计比如2^20范围内的交集，最后把几个交集合并。
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
|
b*****o
发帖数: 715 | 13 The interviewer says NO for 2 arrays interactions or 4 array intersections
when you answer "hash"?
I think the trick of the problem is: when you intersect 2 randomly generated
100K int arrays, the output is expected to be very small.
So essentially there are questions here:
(1) How to intersect 2 large int arrays.
(2) How to intersect 1 large and 1 small int arrays.
way
【在 i******w 的大作中提到】
: 4 arrays, 100K randomly generated int in each array. What's the quickest way
: to get the intersection?
: 我说用hash，结果面试官说不对。
: 大家有什么想法?
|
s********u
发帖数: 1109 | 14 一语点醒梦中人啊。。
generated
【在 b*****o 的大作中提到】
: The interviewer says NO for 2 arrays interactions or 4 array intersections
: when you answer "hash"?
: I think the trick of the problem is: when you intersect 2 randomly generated
: 100K int arrays, the output is expected to be very small.
: So essentially there are questions here:
: (1) How to intersect 2 large int arrays.
: (2) How to intersect 1 large and 1 small int arrays.
:
: way
|
s*******z
发帖数: 83 | |
s********u
发帖数: 1109 | 16 就是面试官的意思可能是，比如第一、第二个数组用bitmap，然后做出来的结果因为是
input是random所以很可能是一个很小的list。第三个第四个数组在做的时候，只要用
暴力法去查就是了，而不用四个bitmap。
不过说老实话，这个也不比hashtable快啊。如果面试官没提到space cost的话，还是
用一个hashtable最快啊，何况bitmap也很费空间。
【在 s*******z 的大作中提到】
: 醒了的说说啊.
|
e*******8
发帖数: 94 | 17 恩，上面的那个想法的确很好。补充个具体的计算吧：
比如假设数字是从M个数字里uniform的挑选：随机挑选n个数字－A，然后随机挑选n个
数字－B。A与B的intersection的expected大小是
M*(1-2*(1-1/M)^n+(1-1/M)^(2n))
M ~ 4*10^9
n ~10^5
then the size of the intersection of A and B is roughly 2.5 (or at most 3).
So then we are computing the intersection of a set of expected size 3 with
a set of
size 10^5
【在 s********u 的大作中提到】
: 就是面试官的意思可能是，比如第一、第二个数组用bitmap，然后做出来的结果因为是
: input是random所以很可能是一个很小的list。第三个第四个数组在做的时候，只要用
: 暴力法去查就是了，而不用四个bitmap。
: 不过说老实话，这个也不比hashtable快啊。如果面试官没提到space cost的话，还是
: 用一个hashtable最快啊，何况bitmap也很费空间。
|
r*******n
发帖数: 3020 | 18 你当成为代码看，我就是示意一下map reduce的思路
我是刚看了一个map reduce的教程，完全的初学者。
【在 i******w 的大作中提到】
: EmitKeyValue 是啥语言啊，python里不应该是 yield 吗？
|
m**p
发帖数: 189 | 19 你确定你醒了？
【在 s********u 的大作中提到】
: 就是面试官的意思可能是，比如第一、第二个数组用bitmap，然后做出来的结果因为是
: input是random所以很可能是一个很小的list。第三个第四个数组在做的时候，只要用
: 暴力法去查就是了，而不用四个bitmap。
: 不过说老实话，这个也不比hashtable快啊。如果面试官没提到space cost的话，还是
: 用一个hashtable最快啊，何况bitmap也很费空间。
|
