logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
问 Facebook Onsite 一题
avatar
问 Facebook Onsite 一题# JobHunting - 待字闺中
w*x
1 楼
find number of unique numbers in a stream input of integers. need
accurate number if the result is small, need rough number if the result is
large.
avatar
i*7
2 楼
HashMap?
avatar
w*x
3 楼
用bit作map好像还不到1g空间啊...
avatar
l*a
4 楼
判断一个整数是否出现过用bitmap 是什么样的复杂度？

【在 w****x 的大作中提到】
: 用bit作map好像还不到1g空间啊...
avatar
i*7
5 楼
用bit做map你怎么数不是unique的呢？

【在 w****x 的大作中提到】
: 用bit作map好像还不到1g空间啊...
avatar
w*x
6 楼

弄错了, 傻X了. 那用两个bit表示3种状态也就1G啊

【在 l*****a 的大作中提到】
: 判断一个整数是否出现过用bitmap 是什么样的复杂度？
avatar
w*x
7 楼

数据多的话怎么计算大致unique number呢

【在 i*********7 的大作中提到】
: HashMap?
avatar
l*b
8 楼
一个bit就足够了吧。是0就计数器加一，否则减一。
问题是不一定是整数阿？
avatar
w*x
9 楼

不对啊, 那一个数出现3次岂不是成unique的了?

【在 l*********b 的大作中提到】
: 一个bit就足够了吧。是0就计数器加一，否则减一。
: 问题是不一定是整数阿？
avatar
l*b
10 楼
你是对的 需要2bits
avatar
p*2
11 楼

int是64位吧？

【在 w****x 的大作中提到】
:
: 不对啊, 那一个数出现3次岂不是成unique的了?
avatar
w*x
12 楼

64位integer怎么做?? 那就是说这题是受到了内存限制.
那是不是可以做一个模除的bit array
long long % 2^32 的bit为1, 然后计算一个概率来估计是否相等??

【在 p*****2 的大作中提到】
:
: int是64位吧？
avatar
l*b
13 楼
如果不需要精确解，从2个bit想到用两个bloom filter:
如果bloom 2是true，skip。
如果bloom1是false, increase counter by one. Insert the number to bloom1.
否则如果bloom1是true，decrease counter by one. Insert the number to bloom2.
avatar
a*o
14 楼
搞俩bloom filter?

【在 w****x 的大作中提到】
:
: 64位integer怎么做?? 那就是说这题是受到了内存限制.
: 那是不是可以做一个模除的bit array
: long long % 2^32 的bit为1, 然后计算一个概率来估计是否相等??
avatar
i*7
15 楼
两个Bit应该就差不多了吧。除模的话感觉就有些HashMap的思想了
avatar
w*x
16 楼

如果是32位操作系统读入64位数据呢?

【在 i*********7 的大作中提到】
: 两个Bit应该就差不多了吧。除模的话感觉就有些HashMap的思想了
avatar
i*7
17 楼
二维bit数组来表示，你觉得怎样？
另外32位操作系统输入了64位数据，不应该是会出现数据溢出导致读进来的数字出错吗？
bool flag[2][INT_MAX][INT_MAX];
因为你本身就要两个bit表示一个数字，那么你一个[INT_MAX]只能表示INT_MAX/2的数
据，所以对于一个数字，flag[0][x][y]来作为一个bit标记，flag[1][x][y]作为另一
个标记。
[INT_MAX][INT_MAX]主要是考虑到你所说的64位数据，否则一个二维数组应该就够用了
。flag[2][INT_MAX]应该就够用了吧。
不过只要取rough number的话，我觉得是不是可以这么设计。
flag[4][INT_MAX];
flag[2]和flag[3]表示高32位，
flag[0]和flag[1]表示低32位。
然后通过高低位配对组合来判断是否Unique。
智商拙计，只能提出这样菜的一样。还有望大牛指出。。

【在 w****x 的大作中提到】
:
: 如果是32位操作系统读入64位数据呢?
avatar
h*n
18 楼
你这个counter是神马，
一个counter？
想来想去还不如直接上counting bloom filter，一个就够了

【在 l*********b 的大作中提到】
: 如果不需要精确解，从2个bit想到用两个bloom filter:
: 如果bloom 2是true，skip。
: 如果bloom1是false, increase counter by one. Insert the number to bloom1.
: 否则如果bloom1是true，decrease counter by one. Insert the number to bloom2.
avatar
w*x
19 楼

吗？
32位操作系统只能对4GB寻址, bool flag[2][INT_MAX][INT_MAX]这玩艺直接爆了....

【在 i*********7 的大作中提到】
: 二维bit数组来表示，你觉得怎样？
: 另外32位操作系统输入了64位数据，不应该是会出现数据溢出导致读进来的数字出错吗？
: bool flag[2][INT_MAX][INT_MAX];
: 因为你本身就要两个bit表示一个数字，那么你一个[INT_MAX]只能表示INT_MAX/2的数
: 据，所以对于一个数字，flag[0][x][y]来作为一个bit标记，flag[1][x][y]作为另一
: 个标记。
: [INT_MAX][INT_MAX]主要是考虑到你所说的64位数据，否则一个二维数组应该就够用了
: 。flag[2][INT_MAX]应该就够用了吧。
: 不过只要取rough number的话，我觉得是不是可以这么设计。
: flag[4][INT_MAX];
avatar
i*7
20 楼
所以我才后来给了一个flag[4][INT_MAX]啊。
或者要考虑到除模的话，就是flag[2][INT_MAX]
然后所有数在存之前都mod INT_MAX。
感觉这就有点象哈希表了

【在 w****x 的大作中提到】
:
: 吗？
: 32位操作系统只能对4GB寻址, bool flag[2][INT_MAX][INT_MAX]这玩艺直接爆了....
avatar
w*x
22 楼
靠, 这个思路太牛叉了
avatar
i*7
23 楼
那个人的解法代码足足178行啊。。。。

【在 w****x 的大作中提到】
: 靠, 这个思路太牛叉了
avatar
N*n
24 楼
说了只要大致数字，那就bloomfilter把

【在 w****x 的大作中提到】
: 靠, 这个思路太牛叉了
avatar
w*x
27 楼
find number of unique numbers in a stream input of integers. need
accurate number if the result is small, need rough number if the result is
large.
avatar
i*7
28 楼
HashMap?
avatar
w*x
29 楼
用bit作map好像还不到1g空间啊...
avatar
l*a
30 楼
判断一个整数是否出现过用bitmap 是什么样的复杂度？

【在 w****x 的大作中提到】
: 用bit作map好像还不到1g空间啊...
avatar
i*7
31 楼
用bit做map你怎么数不是unique的呢？

【在 w****x 的大作中提到】
: 用bit作map好像还不到1g空间啊...
avatar
w*x
32 楼

弄错了, 傻X了. 那用两个bit表示3种状态也就1G啊

【在 l*****a 的大作中提到】
: 判断一个整数是否出现过用bitmap 是什么样的复杂度？
avatar
w*x
33 楼

数据多的话怎么计算大致unique number呢

【在 i*********7 的大作中提到】
: HashMap?
avatar
l*b
34 楼
一个bit就足够了吧。是0就计数器加一，否则减一。
问题是不一定是整数阿？
avatar
w*x
35 楼

不对啊, 那一个数出现3次岂不是成unique的了?

【在 l*********b 的大作中提到】
: 一个bit就足够了吧。是0就计数器加一，否则减一。
: 问题是不一定是整数阿？
avatar
l*b
36 楼
你是对的 需要2bits
avatar
p*2
37 楼

int是64位吧？

【在 w****x 的大作中提到】
:
: 不对啊, 那一个数出现3次岂不是成unique的了?
avatar
w*x
38 楼

64位integer怎么做?? 那就是说这题是受到了内存限制.
那是不是可以做一个模除的bit array
long long % 2^32 的bit为1, 然后计算一个概率来估计是否相等??

【在 p*****2 的大作中提到】
:
: int是64位吧？
avatar
l*b
39 楼
如果不需要精确解，从2个bit想到用两个bloom filter:
如果bloom 2是true，skip。
如果bloom1是false, increase counter by one. Insert the number to bloom1.
否则如果bloom1是true，decrease counter by one. Insert the number to bloom2.
avatar
a*o
40 楼
搞俩bloom filter?

【在 w****x 的大作中提到】
:
: 64位integer怎么做?? 那就是说这题是受到了内存限制.
: 那是不是可以做一个模除的bit array
: long long % 2^32 的bit为1, 然后计算一个概率来估计是否相等??
avatar
i*7
41 楼
两个Bit应该就差不多了吧。除模的话感觉就有些HashMap的思想了
avatar
w*x
42 楼

如果是32位操作系统读入64位数据呢?

【在 i*********7 的大作中提到】
: 两个Bit应该就差不多了吧。除模的话感觉就有些HashMap的思想了
avatar
i*7
43 楼
二维bit数组来表示，你觉得怎样？
另外32位操作系统输入了64位数据，不应该是会出现数据溢出导致读进来的数字出错吗？
bool flag[2][INT_MAX][INT_MAX];
因为你本身就要两个bit表示一个数字，那么你一个[INT_MAX]只能表示INT_MAX/2的数
据，所以对于一个数字，flag[0][x][y]来作为一个bit标记，flag[1][x][y]作为另一
个标记。
[INT_MAX][INT_MAX]主要是考虑到你所说的64位数据，否则一个二维数组应该就够用了
。flag[2][INT_MAX]应该就够用了吧。
不过只要取rough number的话，我觉得是不是可以这么设计。
flag[4][INT_MAX];
flag[2]和flag[3]表示高32位，
flag[0]和flag[1]表示低32位。
然后通过高低位配对组合来判断是否Unique。
智商拙计，只能提出这样菜的一样。还有望大牛指出。。

【在 w****x 的大作中提到】
:
: 如果是32位操作系统读入64位数据呢?
avatar
h*n
44 楼
你这个counter是神马，
一个counter？
想来想去还不如直接上counting bloom filter，一个就够了

【在 l*********b 的大作中提到】
: 如果不需要精确解，从2个bit想到用两个bloom filter:
: 如果bloom 2是true，skip。
: 如果bloom1是false, increase counter by one. Insert the number to bloom1.
: 否则如果bloom1是true，decrease counter by one. Insert the number to bloom2.
avatar
w*x
45 楼

吗？
32位操作系统只能对4GB寻址, bool flag[2][INT_MAX][INT_MAX]这玩艺直接爆了....

【在 i*********7 的大作中提到】
: 二维bit数组来表示，你觉得怎样？
: 另外32位操作系统输入了64位数据，不应该是会出现数据溢出导致读进来的数字出错吗？
: bool flag[2][INT_MAX][INT_MAX];
: 因为你本身就要两个bit表示一个数字，那么你一个[INT_MAX]只能表示INT_MAX/2的数
: 据，所以对于一个数字，flag[0][x][y]来作为一个bit标记，flag[1][x][y]作为另一
: 个标记。
: [INT_MAX][INT_MAX]主要是考虑到你所说的64位数据，否则一个二维数组应该就够用了
: 。flag[2][INT_MAX]应该就够用了吧。
: 不过只要取rough number的话，我觉得是不是可以这么设计。
: flag[4][INT_MAX];
avatar
i*7
46 楼
所以我才后来给了一个flag[4][INT_MAX]啊。
或者要考虑到除模的话，就是flag[2][INT_MAX]
然后所有数在存之前都mod INT_MAX。
感觉这就有点象哈希表了

【在 w****x 的大作中提到】
:
: 吗？
: 32位操作系统只能对4GB寻址, bool flag[2][INT_MAX][INT_MAX]这玩艺直接爆了....
avatar
w*x
48 楼
靠, 这个思路太牛叉了
avatar
i*7
49 楼
那个人的解法代码足足178行啊。。。。

【在 w****x 的大作中提到】
: 靠, 这个思路太牛叉了
avatar
N*n
50 楼
说了只要大致数字，那就bloomfilter把

【在 w****x 的大作中提到】
: 靠, 这个思路太牛叉了
avatar
l*h
53 楼
bloom filter主要好处之一是可以避免hash产生的collision,
但是这一题输入的已经是数字了，没有Hash的问题，没有必要用bloom filter.
大家怎么看?

【在 N**n 的大作中提到】
: 说了只要大致数字，那就bloomfilter把
avatar
w*e
54 楼
这道题是否可以用sampling来做？
如果采样m个样本，m本身足够大，又足够放到内存里，应该可以拿m个样本的uniq
count来估算整个stream input的uniq count
这样就转化成了经典题目怎么在stream data里均匀采样m个样本
伪码：
int array[m];
int cur_cnt = 0;
while read num {
if (cur_cnt < m) {
array[cur_cnt++] = num;
} else {
int hash_code = rund() % N;
if (hash_code < m) array[hash_code] = num;
}
}
//count uniq number using hashmap or sth....

【在 w****x 的大作中提到】
:
: 哇, 大牛居然在这出现了, Onsite前加你做个reference吧
相关阅读
Apple 待遇不行啊H1B transfer批下来了，还能改上班日期吗？可以帮助内推Groupon这个雅虎 offer 是不是太滥了微软的principal dev lead大概多少钱啊？请问uber电面难度新人求问 谢谢请问有没有oracle headquarter 400楼的同学想转组的？如何用leetcode刷题呢？Epic 邮件问题Liveramp 怎么样 onsite 去不去pinterest on-site面试的soft skill如何提高？问一个f家发offer流程preipo 的选择，形式很明朗了Biostatistician/Analyst Job Position Available (转载)[面经]YELP家不刷题的惨烈后果如果老板跟我说招postdoc的可能性Not very likely报一个Amazon的package7个onsite, 一个offer都没有
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。