美瞳的功效# Joke - 肚皮舞运动
i*w
1 楼
4 arrays, 100K randomly generated int in each array. What's the quickest way
to get the intersection?
我说用hash，结果面试官说不对。
大家有什么想法?
to get the intersection?
我说用hash，结果面试官说不对。
大家有什么想法?
b*o
2 楼
☆─────────────────────────────────────☆
fella (latio) 于 (Wed Oct 21 10:59:36 2009, 美东) 提到:
不是下腹痛，很奇怪的，就是阴道时不时抽抽的痛几下。有jm像我这样的吗？痛的地方
也不深，不到子宫颈那里，大概是在中部吧。想问问ob,但是这种抽痛用英文怎么说啊?
☆─────────────────────────────────────☆
JieXiangHM (小丫丫) 于 (Wed Oct 21 12:54:21 2009, 美东) 提到:
很正常 ：）没事
☆─────────────────────────────────────☆
HappyF1 (幸福的学生) 于 (Wed Oct 21 13:08:17 2009, 美东) 提到:
我也有类似症状，不过不是阴道
是腹腔里不知道什么东东，线状抻着疼
有时候在左边有时候在右边
不严重，就是偶尔稍微疼一下，感觉怪怪的
啊?
☆─────────────────────────────────────☆
chee
fella (latio) 于 (Wed Oct 21 10:59:36 2009, 美东) 提到:
不是下腹痛，很奇怪的，就是阴道时不时抽抽的痛几下。有jm像我这样的吗？痛的地方
也不深，不到子宫颈那里，大概是在中部吧。想问问ob,但是这种抽痛用英文怎么说啊?
☆─────────────────────────────────────☆
JieXiangHM (小丫丫) 于 (Wed Oct 21 12:54:21 2009, 美东) 提到:
很正常 ：）没事
☆─────────────────────────────────────☆
HappyF1 (幸福的学生) 于 (Wed Oct 21 13:08:17 2009, 美东) 提到:
我也有类似症状，不过不是阴道
是腹腔里不知道什么东东，线状抻着疼
有时候在左边有时候在右边
不严重，就是偶尔稍微疼一下，感觉怪怪的
啊?
☆─────────────────────────────────────☆
chee
p*g
3 楼
r*n
4 楼
难道用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，结果面试官说不对。
: 大家有什么想法?
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，结果面试官说不对。
: 大家有什么想法?
e*3
5 楼
恶
y*a
6 楼
我觉得最快是用bit array 存4组数，
然后AND
然后AND
z*8
7 楼
首先intersection的定义是什么？ 任何两个数组有， 还是4个数组都得有？
【在 y****a 的大作中提到】
: 我觉得最快是用bit array 存4组数，
: 然后AND
【在 y****a 的大作中提到】
: 我觉得最快是用bit array 存4组数，
: 然后AND
l*n
8 楼
不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
【在 y****a 的大作中提到】
: 我觉得最快是用bit array 存4组数，
: 然后AND
把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
【在 y****a 的大作中提到】
: 我觉得最快是用bit array 存4组数，
: 然后AND
r*n
9 楼
bitmap 也是hash方法
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
i*w
10 楼
4个数组都得有
【在 z*********8 的大作中提到】
: 首先intersection的定义是什么？ 任何两个数组有， 还是4个数组都得有？
【在 z*********8 的大作中提到】
: 首先intersection的定义是什么？ 任何两个数组有， 还是4个数组都得有？
i*w
11 楼
我就是用hash这么答的，人说不满意。
哪位大牛能把bitmap解释一下吗？
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
哪位大牛能把bitmap解释一下吗？
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
i*w
12 楼
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.
:
:
【在 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
13 楼
我猜是不是因为题目里有假设数据是randomly generated？觉得可以把输入分到若干个
buckets，然后每个bucket找intersection？基本上就是bucket sorting的想法。不过
把数字分到bucket里其实也就是hashing。。。
buckets，然后每个bucket找intersection？基本上就是bucket sorting的想法。不过
把数字分到bucket里其实也就是hashing。。。
s*z
14 楼
所有数字看做字符串, 用Trie, 最后一遍数所有叶子count为4的那些就是交集.
貌似这样只用过一遍数字
貌似这样只用过一遍数字
s*u
15 楼
嗯，如果硬上的话,bitset的范围就是2^32也就是GB级别的内存。
但也不是没有办法解决，就是类似bucket sort那种想法，把2^32分割成几个部分，每
次只统计比如2^20范围内的交集，最后把几个交集合并。
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
但也不是没有办法解决，就是类似bucket sort那种想法，把2^32分割成几个部分，每
次只统计比如2^20范围内的交集，最后把几个交集合并。
的。
【在 l*n 的大作中提到】
: 不知道数的范围就上bitmap的话，岂不是要有很多浪费？hashmap就是专治稀疏数据的。
: 把A数组hash一下，然后过一遍B就知道AB的交集，同理CD pair也过一遍。然后AB的结
: 果跟CD的结果再过一遍。因为是随机的数，AB的交集肯定很小了。
b*o
16 楼
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，结果面试官说不对。
: 大家有什么想法?
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
17 楼
一语点醒梦中人啊。。
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
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
18 楼
醒了的说说啊.
s*u
19 楼
就是面试官的意思可能是，比如第一、第二个数组用bitmap，然后做出来的结果因为是
input是random所以很可能是一个很小的list。第三个第四个数组在做的时候，只要用
暴力法去查就是了，而不用四个bitmap。
不过说老实话，这个也不比hashtable快啊。如果面试官没提到space cost的话，还是
用一个hashtable最快啊，何况bitmap也很费空间。
【在 s*******z 的大作中提到】
: 醒了的说说啊.
input是random所以很可能是一个很小的list。第三个第四个数组在做的时候，只要用
暴力法去查就是了，而不用四个bitmap。
不过说老实话，这个也不比hashtable快啊。如果面试官没提到space cost的话，还是
用一个hashtable最快啊，何况bitmap也很费空间。
【在 s*******z 的大作中提到】
: 醒了的说说啊.
e*8
20 楼
恩，上面的那个想法的确很好。补充个具体的计算吧：
比如假设数字是从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也很费空间。
比如假设数字是从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
21 楼
你当成为代码看，我就是示意一下map reduce的思路
我是刚看了一个map reduce的教程，完全的初学者。
【在 i******w 的大作中提到】
: EmitKeyValue 是啥语言啊，python里不应该是 yield 吗？
我是刚看了一个map reduce的教程，完全的初学者。
【在 i******w 的大作中提到】
: EmitKeyValue 是啥语言啊，python里不应该是 yield 吗？
m*p
22 楼
你确定你醒了？
【在 s********u 的大作中提到】
: 就是面试官的意思可能是，比如第一、第二个数组用bitmap，然后做出来的结果因为是
: input是random所以很可能是一个很小的list。第三个第四个数组在做的时候，只要用
: 暴力法去查就是了，而不用四个bitmap。
: 不过说老实话，这个也不比hashtable快啊。如果面试官没提到space cost的话，还是
: 用一个hashtable最快啊，何况bitmap也很费空间。
【在 s********u 的大作中提到】
: 就是面试官的意思可能是，比如第一、第二个数组用bitmap，然后做出来的结果因为是
: input是random所以很可能是一个很小的list。第三个第四个数组在做的时候，只要用
: 暴力法去查就是了，而不用四个bitmap。
: 不过说老实话，这个也不比hashtable快啊。如果面试官没提到space cost的话，还是
: 用一个hashtable最快啊，何况bitmap也很费空间。
相关阅读
我也 澄清一下发包子反悔事件。 (转载)这个人是屌丝吗？女人, 就是要对自己狠一点这是哪个黑帮片啊？要海归了，如何运枪回国是谁想的画马方法的 (转载)住户爬钢筋回家好吃的要分享姑娘，你真是条汗子你看画，我看看你！神一样的android app，神一样的reviewua is suck!！太黑了，背后捅刀子一个新加坡人在中国杀了一个英国人(zz)打黑英雄王立军：Who's your daddy now?卖票的伤不起...女星车晓与山西首富结婚15个月后离婚 赡养费3亿 (转载)来分享一下上班迟到早退的心得。。。 (转载)Re: 想认真找个男朋友以结婚为目的, 想在德州范围内找, 所以就(转载)这个段子很有才啊~ (转载)