牛客678303729

2021-07-12 12:06 算法工程师

关注

Shopee后端研发开放式问答

问，十亿的数据量，每条数据4个字节，如何去重，或者统计每条数据出现的次数；

面试官开始没有说数据量，我回答是，在不考虑空间复杂度的情况下，用集合或哈希表；

面试官后来加入了数据量，和内存不够的条件，我没啥思路，乱答的前缀树做压缩；

这个有什么方法吗？

#shopee校招##Shopee##面试题目#

全部评论

推荐最新楼层

牛客200478187号

Java

如果只考虑去重、不考虑统计次数的话，可以用布隆过滤器。假设数据量 10^9，失误率 0.1，计算器敲除所需位数换算成内存大小是 571MB，感觉还是有点大。。。没有实操经验，不太懂

1 回复

发布于 2021-07-15 19:49

Java

位图

点赞回复

发布于 2021-07-12 14:16

阅文集团

校招火热招聘中

官网直投

字节跳动_服务端

hyperloglog

点赞回复

发布于 2021-07-12 14:51

Java

布隆过滤器了解一下

点赞回复

发布于 2021-07-12 17:27

滴滴_国际化_后台研发

最小计数

点赞回复

发布于 2021-07-12 17:46

你瞅啥？？

Java

bitmap

点赞回复

发布于 2021-07-14 19:41

C++

位图最简单

点赞回复

发布于 2021-07-15 20:04

Garena_游戏客户端

布隆过滤器只能判断一个元素是否一定不存在，怎么统计个数?不懂你们这些说布隆过滤器的?

点赞回复

发布于 2021-07-18 01:11

03-17 01:29

已编辑

中南大学计算机类

2024-3-16美团笔试题(A~E)

提前一小时AK纪念A:概述：有n个商品，价值ai 元，有一个x元的满减，一个y元的优惠卷，保证一定可以用到满减和优惠卷，问购买这n个商品需要多少元思路：求和，减去x,y即可 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) using namespa...

投递美团等公司10个岗位 >

点赞评论收藏

转发

03-30 22:20

University of Southern California 计算机类

腾讯笔试问题

给两个数k和q。需要判断q为分母时是否有循环小数。如果有，其循环部分的长度是否能达到k。测试用例1  63 371 41000 3答案True, True, False, True

投递腾讯等公司10个岗位

点赞评论收藏

转发

吃花椒的妙酱

03-24 12:05

已编辑

华南农业大学生物学

3.24字节笔试题解

分享题解攒人品（写题能力严重退化~第一题题意：凸多边形有n条边，每条边上ai个标记，问选三个标记组成三角形的方案数，对1e9+7取模(n<=1e5, ai <=1e9)思路：dpdp[i][j]表示前i条边取了j个标记，有转移式dp[i][j+k] += dp[i-1][j] + C(ai, k) 第i条边取了k个标记。由于j不超过3，k不超过2，且C(ai, k)可以直接乘除得到，复杂度O(n) 看到有大佬容斥思路做的，很妙，没想到哈哈哈。第二题题意: 给定一个字符串，求包含"byte"或者"dance&quo...

投递字节跳动等公司10个岗位 >

点赞评论收藏

转发

Java八股吟唱大法好

03-21 23:19

已编辑

门头沟学院计算机类

3/21 美团暑期一面凉经

暑期第一面凉，来攒攒人品。面试官人很好，就是不太爱问八股，偏实际应用，回答的都不是很全面- 自我介绍- 拷打实习和项目- 如何解决bug？- redis为什么比sql快- 热点数据一定适合放在Redis中嘛？- Kafka延迟写入有什么问题，不包括消息丢失，重复消费，顺序消费- hashmap为啥不安全- 算法：约瑟夫环   很多年没做了，讲了思路，写了没来及测试，时间到了。

点赞评论收藏

转发

03-31 22:05

已编辑

西安电子科技大学计算机类

腾讯2024后台实习生笔试 473/500

小红的图上染色（100%）1e5点数的无向图，有些边是红色，定义一个“好点”当且仅当该点所有邻边都是红边碰到无色的边则标记两个点，最后未被标记的点数就是答案小红的链表断裂（100%）总长1e5的链表，元素不重复，如果可以把该链表一分为二重新拼接后升序则返回true，否则返回false遍历一遍如果没有降序则为true，碰到第一个降序则标记位置重新拼接，整体升序返回true，否则false小红的连通图（100%）1e5点数的无向图，有多少种方法使得添加一条边后图连通并查集合并，最后统计各个集合的点数，若：只有一个集合：答案为n * (n - 1) / 2 - m（n个点m条边）两个集合：答案为两个...

投递腾讯等公司9个岗位 >

点赞评论收藏

转发

点赞 29 评论

招聘动态

博乐游戏

24届春招&25届实习生招聘

联想

24届应届+25届实习

24届春招硬件高薪职位集合

阅文集团2024春季校招

百信银行

全站热榜

正在热议

# 牛客帮帮团来啦！有问必答 #

76082次浏览 1988人参与

# 你会选择考研还是直接就业 #

51075次浏览 583人参与

# 都在说24和25届，谁来管21-23届呢 #

63405次浏览 816人参与

# 辞职后的日常 #

3679次浏览 49人参与

# Offer比较，你最看重什么？ #

37976次浏览 395人参与

# 学历对求职的影响 #

104325次浏览 1115人参与

# 腾讯音乐工作体验 #

127305次浏览 2554人参与

# 比亚迪求职进展汇总 #

102218次浏览 905人参与

# 你觉得通信/硬件有必要实习吗？ #

16066次浏览 366人参与

# 转眼已经银四了，你收到offer了吗 #

81227次浏览 642人参与

# 0offer是寒冬太冷还是我太菜 #

310000次浏览 3974人参与

# 设计人如何选offer #

9925次浏览 244人参与

# 25届非技术实习投递记录 #

29670次浏览 427人参与

# 视觉/交互/设计工作体验 #

4212次浏览 134人参与

# 选了这个offer，你有没有后悔？ #

67770次浏览 590人参与

# 快手工作体验 #

30649次浏览 621人参与

# 想辞职但是不敢的原因 #

2356次浏览 59人参与

# 夸夸我的求职搭子 #

51940次浏览 603人参与

# 双非本科求职如何逆袭 #

150233次浏览 2246人参与

# 23届的你们都什么时候入职？ #

66574次浏览 570人参与

# 春招已经启动啦硬件uu开始投了吗？ #

74512次浏览 567人参与

# 秋招的第一个offer，大家都拿到了吗 #

95428次浏览 1706人参与

牛客网
牛客企业服务