Shopee后端研发 开放式问答

问,十亿的数据量,每条数据4个字节,如何去重,或者统计每条数据出现的次数;
面试官开始没有说数据量,我回答是,在不考虑空间复杂度的情况下,用集合或哈希表;
面试官后来加入了数据量,和内存不够的条件,我没啥思路,乱答的前缀树做压缩;
这个有什么方法吗?
#shopee校招##Shopee##面试题目#
全部评论
如果只考虑去重、不考虑统计次数的话,可以用布隆过滤器。假设数据量 10^9,失误率 0.1,计算器敲除所需位数换算成内存大小是 571MB,感觉还是有点大。。。没有实操经验,不太懂
1 回复 分享
发布于 2021-07-15 19:49
布隆过滤器只能判断一个元素是否一定不存在,怎么统计个数?不懂你们这些说布隆过滤器的?
点赞 回复 分享
发布于 2021-07-18 01:11
位图最简单
点赞 回复 分享
发布于 2021-07-15 20:04
bitmap
点赞 回复 分享
发布于 2021-07-14 19:41
最小计数
点赞 回复 分享
发布于 2021-07-12 17:46
布隆过滤器了解一下
点赞 回复 分享
发布于 2021-07-12 17:27
hyperloglog
点赞 回复 分享
发布于 2021-07-12 14:51
位图
点赞 回复 分享
发布于 2021-07-12 14:16

相关推荐

09-02 11:14
已编辑
四川大学 Java
吴offer选手:这种面试是最烦的,学不到东西,然后还被挂的莫名其妙。之前看到一种说法是面试官如果不想要你了,就会问一些很简单的问题,防止你举报他
点赞 评论 收藏
分享
小肥罗:此乃引蛇出洞之计,勾出你想去杭州的原因再告诉你不在杭州,让你打脸,自己离开。好一招抛砖引玉,虾仁猪心。你回复:计划去杭州,但我心中第一选择是宁波~巧了! 这计名叫“阿Q精神胜利法之厚脸皮不要脸我不尴尬谁爱尴尬谁尴尬去”之计!克制一切!
这个工作能去吗
点赞 评论 收藏
分享
评论
点赞
29
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务