一亩三分地论坛

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

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

[算法题] Snapchat BloomFilter Remove

[复制链接] |试试Instant~ |关注本帖
神罗天征 发表于 2016-9-22 01:48:07 | 显示全部楼层 |阅读模式

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

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

x
刷snapchat面经的时候遇到了一道题,关于bloom filter,面试官要求能实现remove,但是问题是,remove不就导致bloom filter不准了吗?我最开始考虑的是用一个counter,add就是++, remove就--,但是感觉还是不对,不知道各位大神有什么想法,多谢

http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311
leixiang5 发表于 2016-9-22 02:07:59 | 显示全部楼层
bloomfilter不支持remove~..如果要remove..要rebuild everything~
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-9-22 02:25:43 | 显示全部楼层
leixiang5 发表于 2016-9-22 02:07
bloomfilter不支持remove~..如果要remove..要rebuild everything~

对呀……所以我觉得面试官问这个不知道啥意思……
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-22 04:48:10 | 显示全部楼层
神罗天征 发表于 2016-9-22 02:25
对呀……所以我觉得面试官问这个不知道啥意思……

会不会是要cuckoo filter?
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-9-22 05:03:55 | 显示全部楼层
leixiang5 发表于 2016-9-22 04:48
会不会是要cuckoo filter?

这个好高级……不过看了一些博客,好像确实可以用counter
回复 支持 反对

使用道具 举报

pinkdatura 发表于 2016-11-2 14:15:14 | 显示全部楼层
应该是counter bloom filter啊,lintcode上有原题目。
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-11-2 14:31:18 | 显示全部楼层
pinkdatura 发表于 2016-11-2 14:15
应该是counter bloom filter啊,lintcode上有原题目。

啊?请问是哪一道题呀
回复 支持 反对

使用道具 举报

pinkdatura 发表于 2016-11-3 07:35:53 | 显示全部楼层
好像是上过设计课的能看到,其实你去他们网站搜一下counter bloom filter的答案就能看懂,其实就是每一位存数字而不是存boolean
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-11-3 08:00:50 | 显示全部楼层
pinkdatura 发表于 2016-11-3 07:35
好像是上过设计课的能看到,其实你去他们网站搜一下counter bloom filter的答案就能看懂,其实就是每一位存 ...

九章的是吗?貌似没有,应该是因为我没有付费……
回复 支持 反对

使用道具 举报

kradnangel 发表于 2016-11-7 12:03:51 | 显示全部楼层
https://en.wikipedia.org/wiki/Bloom_filter#Counting_filters
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 02:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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