一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1869|回复: 12
收起左侧

snapchat 电面

[复制链接] |试试Instant~ |关注本帖
epochou 发表于 2015-12-17 08:14:38 | 显示全部楼层 |阅读模式

() @ - -  |

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
面完snapchat 觉得最近人品太差了,还是得发发面经求人品。

准备的题目一道也没用上,搜了下才知道是onsite题,让实现下个bloom filter, 听都没听过。实现 add(), contains(), 还要实现resize()。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
求onsite, 二面也好。.1point3acres缃

人品太差,google 上周一电面到现在都没消息...上周还跪了个非常喜欢的square onsite,觉得还是发发面经攒点人品吧。

评分

4

查看全部评分

wcyz666 发表于 2015-12-17 15:06:23 | 显示全部楼层
bloom filter的硬伤不就是不能resize么。。。感觉必须得保留旧filter同时开一个新的大filter。。。?
回复 支持 反对

使用道具 举报

 楼主| epochou 发表于 2015-12-17 15:48:57 | 显示全部楼层
那样的话就是改Hash(String) % k 中 k的值,比较麻烦,我就直接增加一个同样大小的array, 感觉不是最优的方法。
回复 支持 反对

使用道具 举报

 楼主| epochou 发表于 2015-12-17 15:49:18 | 显示全部楼层
wcyz666 发表于 2015-12-17 02:06
bloom filter的硬伤不就是不能resize么。。。感觉必须得保留旧filter同时开一个新的大filter。。。?

那样的话就是改Hash(String) % k 中 k的值,比较麻烦,我就直接增加一个同样大小的array, 感觉不是最优的方法。
回复 支持 反对

使用道具 举报

wcyz666 发表于 2015-12-17 16:22:01 | 显示全部楼层
epochou 发表于 2015-12-17 15:49
那样的话就是改Hash(String) % k 中 k的值,比较麻烦,我就直接增加一个同样大小的array, 感觉不是最优的 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
我跟你差不多,有一个list保存所有的bloom filter,当前没有就去之前的filter里面查,查到了在当前的filter里面rehash一下,要resize的话就新开一个两倍大的数组放在list开头。

bloom filter我当时学的时候记得因为他不存key,所以不可能原地rehash/resize。。。
回复 支持 反对

使用道具 举报

beefcurtain5 发表于 2015-12-17 18:20:31 | 显示全部楼层
from https://en.wikipedia.org/wiki/Talk%3ABloom_filter
A bloom filter cannot resize without storing keys - if you think it can, I would love to see you try and build a bloom filter that can rehash and resize for optimal m and k as per p and n. In fact, I would take great pleasure at seeing you attempt this impossible programming feat

我看了看google guava bloomfilter的source code, 也没有resize这个functionality。
回复 支持 反对

使用道具 举报

 楼主| epochou 发表于 2015-12-17 23:03:10 | 显示全部楼层
wcyz666 发表于 2015-12-17 03:22
我跟你差不多,有一个list保存所有的bloom filter,当前没有就去之前的filter里面查,查到了在当前的filt ...

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 我之前都没听过,不知道他到底想怎么expand, 看人品了。
回复 支持 反对

使用道具 举报

 楼主| epochou 发表于 2015-12-17 23:04:22 | 显示全部楼层
beefcurtain5 发表于 2015-12-17 05:20
from https://en.wikipedia.org/wiki/Talk%3ABloom_filter
A bloom filter cannot resize without storing ...

那假如一个array全填满了,全是1,怎么解决的?不太懂..
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2015-12-18 00:21:55 | 显示全部楼层
请问你用的是什么 hash 函数?都是自己写的吗?.鐣欏璁哄潧-涓浜-涓夊垎鍦

resize 我的想法也是加一个相同 size 的 filter。一个元素如果所有的filter都没有,那么一定没有,如果其中一个显示有,那么就可能有。

但是这样的话不太会算 false positive 的概率是多少?
回复 支持 反对

使用道具 举报

 楼主| epochou 发表于 2015-12-18 00:24:53 | 显示全部楼层
Gianluigi 发表于 2015-12-17 11:21
请问你用的是什么 hash 函数?都是自己写的吗?

resize 我的想法也是加一个相同 size 的 filter。一个元 ...
. From 1point 3acres bbs
hash 函数不用自己写,假设给了一个List<HashFucntion>,我最后implement的方法基本就那样, 也是那么解释的,也不知道面试官认不认可。
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2015-12-18 00:43:25 | 显示全部楼层
epochou 发表于 2015-12-18 00:24
hash 函数不用自己写,假设给了一个List,我最后implement的方法基本就那样, 也是那么解释的,也不知道面 ...
.1point3acres缃
多谢。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
那么 resize 如果是加一个同样 size 的 filter,如果一个数在前一个filter里有,你在查询到它之后,会再移到当前的新filter里吗?还是只会把新的 element (如果旧filter没有的话)放到新 filter 里呢?
回复 支持 反对

使用道具 举报

 楼主| epochou 发表于 2015-12-18 01:31:59 | 显示全部楼层
Gianluigi 发表于 2015-12-17 11:43.1point3acres缃
多谢。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
那么 resize 如果是加一个同样 size 的 filter,如果一个数在前一个filter里有,你在查询到它 ...

我没移,只是放在新filter里。
回复 支持 反对

使用道具 举报

Gianluigi 发表于 2015-12-18 01:45:47 | 显示全部楼层
epochou 发表于 2015-12-18 01:31
我没移,只是放在新filter里。

多谢。

我刚看到一篇文献: http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf. From 1point 3acres bbs

按它的意思 size 逐渐增大比较好,可以控制 false positive rate。

比如按 power of 2 增长。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 22:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表