首页 > 试题广场 >

检测帖子

[问答题]
为打击灌水和欺诈信息的发布,58上的帖子从到展示要经历重重检测。检测规则一共有50个,一条帖子可能会同时被同时被多个规则拦截,也可能不被任何规则拦截。现有一个日志文件,每一行都记录着一个帖子ID和若干拦截该帖子的规则ID,日志文件一共9999995行。帖子ID取值为[1,9999999]上的某个整数,且无重复。帖子ID在日志文件中是无序的。
问题:
1.如何计算任意两个规则同时拦截的帖子数量?要求只扫描一遍日志文件。采用尽可能少的存储空间
2.假设一个帖子ID需要用4个字节来存储,请使用2M的内存空间丢失的那4个帖子ID找出来,你的算法扫描了几遍日志文件?
ID             拦截规则
1              A B C 
2              B C D
3              A B D
4              C D E
...                ...

1、计算任意两个规则同时拦截的帖子数量?
    如求A、B这两个规则,按行遍历整个文件,判断ID的拦截规则是否包含A、B这两个,如果包含,则找到一个。
2、使用2M的内存空间丢失的那4个帖子ID找出来?
    帖子ID取值范围:[1,9999999],使用位图法,需要申请 1000万 * 1 bit / 8  = 1.25MB的内存空间。
    按行扫描一次文件,将出现ID对应的 bit标记为1,如果哪一个bit不为1,即为丢失的那4个帖子ID。
发表于 2018-04-01 15:25:43 回复(0)
1、按行读,对每行查找是否符合2个规则
2、位图法,只需要1MB多
发表于 2015-10-20 22:17:14 回复(0)
1,并集
2,数据密集,申请一个1000万的boolean数组就行
发表于 2016-02-28 01:04:34 回复(0)
第2问一次循环即可;50万的数组存储。循环id求余,数组元素+2的id除50万的倍数次方;找到小于2的21次方-1的下标;对其还原找到2进制为0的位数乘50万+下标可得结果
发表于 2015-11-11 16:34:58 回复(1)