面试题64(有1千万条有重复的短信,以文本文件的形式保存,一行一条,也有重复。请用5 分钟时间找出重复出现最多的前10 条短信)

1·有1千万条有重复的短信,以文本文件的形式保存,一行一条,也有重复。请用5 分钟时间找出重复出现最多的前10 条短信。?

正确解析如下...

解析: 对于本题来说,某些面试者想用数据库的办法实现,首先将文本导入数据库,再利用select 语句的方法得出前10 个短信。但实际上用数据库是绝对满足不了5分钟解决这个条件的。这是因为1千万条短信即使1秒钟导入1万条(这已经算是很快的数据导入了),5分钟才3 百万条,即便真的能在5分钟内录完1千万条,也必须先建索引,否则SQL语句在5 分钟内肯定得不出结果。但对1千万条记录建索引,在5 分钟内也不能完成。所以用数据库的办法不行。

这种类型的题之所以会出现,这是因为互联网公司每时每刻需要处理由用户产生的海量数据/日志,所以海量数据的题现在很热,互联网公司招聘时基本上都会考。重点考查求职者的数据结构设计与算法基本功。类似题目是如何根据关键词搜索访问最多的前10 个网站。

正确答案在下面!

正确答案:

方法1: 用哈希表的方法。

可以将1千万条短信分成若干组,进行边扫描边建散列表的方法。第一次扫描,取首字节、尾字节、中间任意两字节作为Hash Code,插入到hash table中,并记录其地址、信息长度和重复次数。同hash code 且等长就疑似相同,比较一下。相同记录只加1次进hash table,但将重复次数加1。一次扫描以后,已经记录各自的重复次数,进行第二次hash table 的处理。用线性时间选择可在O(n)的级别上完成前10 条的寻找。分组后每组中的top10 必须保证各不相同,可用hash 来保证,也可直接按hash值的大小来分类。

方法2: 采用从小到大排序的办法。

根据经验,除非是群发的过节短信,否则字数越少的短信,出现重复的概率越高。建议从字数少的短信开始找起,比如一开始搜个字的短信,找出重复出现的top10 并分别记录出现次数,然后搜两个字的,以此类推。对于对相同字数的比较长的短信的搜索,除了hash 之类的算法外,可以选择只抽取头、中和尾等几个位置的字符进行粗判,因为此种判断方式是为了加快查找速度,但未必能得到真正期望的top10,因此,需要做标记,如此搜索一遍后,可以从各次top10结果中找到备选的top10,如果这次top10 中有刚才做过标记的,则对其对应字数的所有短信进行精确搜索,以找到真正的topl0 并再次比较。

方法3: 采用内存映射办法。

首先,1千万条短信按现在的短信长度将不会超过1GB 空间,使用内存映射文件比较合适,可以一次映射(如果有更大的数据量,可以采用分段映射),由于不需要频繁使用文件I/O 和频繁分配小内存,这将大大提高了數据的加载速度。其次,对每条短信的第i (i 从0到70) 个字母按ASCII码进行分组,也就是创建树。i是树的深度,也是短信第i 个字母。

该问题主要是解决两方面的内容,一是内容加载,二是短信内容的比较。采用文件内存映射技术可以解决内容加载的性能问题(不仅仅不需要调用文件I/O 函数,而且也不需要每读出一条短信都要分配一小块内存),而使用树技术可以有效地减少比较的次数。

原文发布于微信公众号 - java学习(javaxxf)

原文发表时间:2018-01-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Kirito的技术分享

八个层面比较 Java 8, RxJava, Reactor

这是一篇译文,原文出处(http://alexsderkach.io/comparing-java-8-rxjava-reactor/)。其实很久以前我就看完了...

1.1K60
来自专栏数据小魔方

高级筛选到底有多“高级”!

今天跟大家分享excel筛选功能中隐藏的高级筛选功能! excel中的筛选窗口中,一直隐藏着一个不起眼的小菜单——高级:(如下图) ? 按照微软软件一贯风格,藏...

36150
来自专栏Python爬虫与算法进阶

爬虫之全站爬取方法

其实这个很好理解。比如说知乎,一个大V有100W粉丝,从这个大V出发,抓取粉丝的粉丝,一直循环下去。(可能是个死循环)

46030
来自专栏CSDN技术头条

十五条有用的Golang编程经验

本文作者在很短的时间内就从对Golang一无所知到开发出真正的产品。在学习Golang的过程中,他总结出十五条编程经验以分享给读者。以下是译文。 ? 像许多其他...

35080
来自专栏Crossin的编程教室

【每周一坑】校验文件哈希

先说个通知,给参与了码上行动的同学:又一期展示学习成果的编程擂台活动开始了,即是练手的好机会,又能得到助教的全程支持,还可以得积分赢奖金。赶紧来报名吧!从课程首...

367110
来自专栏Android开发经验

ExpandableStickyListHeadersListView遇到的一个问题

15540
来自专栏安恒网络空间安全讲武堂

护网杯REFINAL——write up

根据前面的一些信息,判断出长度为0x30,经过如下设置,我们可以很快开始进行动态调试。

18520
来自专栏码匠的流水账

java降低竞争锁的一些方法

本文介绍一下提升并发可伸缩性的一些方式:减少锁的持有时间,降低锁的粒度,锁分段、避免热点域以及采用非独占的锁或非阻塞锁来代替独占锁。

12710
来自专栏小小挖掘机

数据城堡参赛代码实战篇(二)---使用pandas进行数据去重

小编们最近参加了数据城堡举办的“大学生助学金精准资助预测”比赛,分组第19名的成绩进入了复赛,很激动有木有!在上一篇文章中,小编带你使用pandas并结合官方给...

38680
来自专栏申龙斌的程序人生

零基础学编程005:打印一行复利数据

问题 上次文章《集成开发环境IDE》里留了一道练习题: 如何用Python打印这篇枯燥的《复利数据表》: (1+0.01) ^ 1 = 1.01 (1+0.0...

34490

扫码关注云+社区

领取腾讯云代金券