前言介绍

对自己的审视：我是一个未入职场的小白，从本科就读的专业就是计算机科学与技术，可时间匆匆，并未把握好大学的时光，从来到北京读研之后，越来越觉得大学本科是我的舒适圈，太舒适而淡忘了自己的专业和技能，重新认识自己和认清技能缺失的我，开始了改变自己的学习之路。

  读研期间的专业是大数据专业，选择这个专业也是说来话长，复试过后，预选专业是虚拟现实，在入学之前，一段实习经历改变了我对虚拟现实技术的看法，或者是出于从众于热门专业和就业的考虑，我开始在人工智能和大数据之间徘徊不定，上网查阅了很多关于两者的难度和就业面，以及家里的“由简入深”原则，最终报道那天，做出了决定，从此开始了我的第二所大学的生活。

在第一学年里边，我被快节奏的上课讲课进度以及老师们严格的作业考察忙得死去活来，可回过头来想想，自己好像只了解了大数据的大致轮廓，就是数据采集、数据预处理、数据统计/分析、数据挖掘。。。。。。这认识也太片面了吧，自己又看了一些杂七杂八的书，比如Hadoop中HDFS、MapReduce、YARN的原理，Hive、HBase、Spark的架构等等，结果忙来忙去，又很长时间过去了，自己还是处于迷茫状态，心里的疑问：大数据到底是什么？

慢慢地，时间一点点过去，研一马上就要过去，心想：总要找个实习赚点钱减轻负担吧，因为第一次实习有过Web的相关经验，所以自认为这方面是自己会的最多的了，可依然很菜，自己掌握的知识真的不值一提，登不上台面，所以有公司录用就直接去了，本着学点东西的原则，结果发现：上了贼船。不但没有实际的技术工作，只要眼力好，耐得住，页面英文翻译汉语总会的吧！所以就开始了长达三个月的“搬砖工”，自己抽时间学习了自己最不会的机器学习，为什么自己不会大数据又选了人工智能了？导师的项目有数据分析，动不动就是要用的，本人又没有时间学习，趁实习不是特别忙，就开始学习吧。所以又又又换了学习的方向，哎，写到这里，我自己都服了自己举棋不定的样子。我内心渴望能入行，哪怕有一丝机会，但没有坚持。

自从自己写博客之后，感觉自己肯踏实做事了，至少自己的努力以博客的形式展现了出来，虽然没有几个人看，但我自己看着也是一份动力。所以我每天做一点事情，都记录了下来。慢慢的，我拖延的毛病越来越少了，有什么事就尽快去办，有什么东西不懂就学，我终于走到了正确的轨道上。

偶然的机遇和挑战

  正赶上秋招的时候，我因为上边的诸多原因，和意识的肤浅，没有准备，但打算蹭一下秋招的热度，投投简历，试试自己的水平，通过碰壁的方式，我可能才能清醒的认识到自己的不足。于是我抽了一个晚上专门改，经验有限并且没有实际项目的加持，让我并没有写出漂亮的敲门砖，但我还是广撒网的投递了一波，获得了几个面试邀请。

面试的第一家，竟然是百度，对大厂的憧憬和期待，让我有些恐慌，我不敢相信大厂会面试我这种小白，毫无面试经验的我不懂的包装自己和伪装，我决定实话实说。上午得到面试邀请，约到下午去公司面试，我准备了几个小时的复习，准备的不充分且小紧张。

骑着共享单车，慢悠悠的来到了百度的大楼下，刹那间，我被大厂的排场就镇住了，百度的大楼不仅有层次感，而且造型很独特，每层楼的间距是很高的，心里开始做上了“如果我在这里工作就好了”的白日梦，转眼间就到了面试约定的时间。。。。。。

一面

  面试官有两位，其中一位从前台把我带到了面试大厅的一个小桌子，我坐到位置上，把书包挂在坐的椅子上，心里就开始有点紧张了，另一位面试官比较腼腆，全程没有怎么说话，只是我和他独自坐在一起的时候说了几句，“你本科是在哪儿读的，简历没有写”，“你比较熟悉Java呀”，等到第一位接待我的面试官重新回到座位，说“补个自我介绍吧”，我就巴拉巴拉开始说，说道跟着老师做项目的时候，开始问一些细节问题，项目的问题就不在这做记录了，根据自己情况发挥吧。

  接下来问了一些数据结构的问题，可以列一下：

1.手写一个排序算法（任意一个）我当时复习的不够好，手写了一个冒泡排序法，写完了之后，面试官让我讲了一下思想后，问了一下冒泡排序法相比于快速排序法的优点和缺点。(完毕)

2.手写一个MR的WordCount程序有一点时间不写了，一些继承的类和方法名字忘记了，于是我征求了意见，写了一个python版本的，勉强算过吧。（完毕）

3.聚类算法有了解过吗？。。。（完毕）

后来面试官问完之后，很爽快的给了二面的机会。

二面

我本来以为就这么简单的通过了，哈哈哈，看来还是想的太多了。二面的面试官一看就是高材生，酷酷的，甚至有点不想多言语。

1.机器学习算法有了解过吗? 描述一下Logistic逻辑回归的整个训练过程。。。。。（完毕）

2.手写一个折半查找。用递归的方式写了一版。（完毕）

3.在A字符串（比如：abc。。。edf。。。）中找B字符串(比如：df，长度不定)，如果存在，请返回B字符串的位置。写了一版很奇葩的写法，应该是错掉了。（完毕）

到此，面试结束了，面试时长不到两个小时，二面的面试官告诉我：如果录用会有通知的，没消息就是被刷了。这也太真实了吧！

总结

虽然过程比较痛苦，准备的十分不足，总之还是非常有价值的一次经历，不经历风雨，怎么知道自己有多菜呢，既然又刷新了认知，那就赶紧补习自己的功课，就冲着大厂的华丽外表也值得争取，加油，奋斗的自己和为了生活的大家。

大数据面试题总结

1、kafka的message包括哪些信息

一个Kafka的Message由一个固定长度的header和一个变长的消息体body组成

header部分由一个字节的magic(文件格式)和四个字节的CRC32(用于判断body消息体是否正常)构成。当magic的值为1的时候，会在magic和crc32之间多一个字节的数据：attributes(保存一些相关属性，比如是否压缩、压缩格式等等)；如果magic的值为0，那么不存在attributes属性，

body是由N个字节构成的一个消息体，包含了具体的key/value消息。

2、怎么查看kafka的offset

0.9版本以上，可以用最新的Consumer client 客户端，有consumer.seekToEnd() / consumer.position() 可以用于得到当前最新的offset：

3、hadoop的shuffle过程

一、Map端的shuffle

　　Map端会处理输入数据并产生中间结果，这个中间结果会写到本地磁盘，而不是HDFS。每个Map的输出会先写到内存缓冲区中，当写入的数据达到设定的阈值时，系统将会启动一个线程将缓冲区的数据写到磁盘，这个过程叫做spill。

　　在spill写入之前，会先进行二次排序，首先根据数据所属的partition进行排序，然后每个partition中的数据再按key来排序。partition的目是将记录划分到不同的Reducer上去，以期望能够达到负载均衡，以后的Reducer就会根据partition来读取自己对应的数据。接着运行combiner(如果设置了的话)，combiner的本质也是一个Reducer，其目的是对将要写入到磁盘上的文件先进行一次处理，这样，写入到磁盘的数据量就会减少。最后将数据写到本地磁盘产生spill文件(spill文件保存在{mapred.local.dir}指定的目录中，Map任务结束后就会被删除)。

　　最后，每个Map任务可能产生多个spill文件，在每个Map任务完成前，会通过多路归并算法将这些spill文件归并成一个文件。至此，Map的shuffle过程就结束了。

二、Reduce端的shuffle

　　Reduce端的shuffle主要包括三个阶段，copy、sort(merge)和reduce。

　　首先要将Map端产生的输出文件拷贝到Reduce端，但每个Reducer如何知道自己应该处理哪些数据呢？因为Map端进行partition的时候，实际上就相当于指定了每个Reducer要处理的数据(partition就对应了Reducer)，所以Reducer在拷贝数据的时候只需拷贝与自己对应的partition中的数据即可。每个Reducer会处理一个或者多个partition，但需要先将自己对应的partition中的数据从每个Map的输出结果中拷贝过来。

　　接下来就是sort阶段，也成为merge阶段，因为这个阶段的主要工作是执行了归并排序。从Map端拷贝到Reduce端的数据都是有序的，所以很适合归并排序。最终在Reduce端生成一个较大的文件作为Reduce的输入。

　　最后就是Reduce过程了，在这个过程中产生了最终的输出结果，并将其写到HDFS上。

4、spark集群运算的模式

Spark 有很多种模式，最简单就是单机本地模式，还有单机伪分布式模式，复杂的则运行在集群中，目前能很好的运行在 Yarn和 Mesos 中，当然 Spark 还有自带的 Standalone 模式，对于大多数情况 Standalone 模式就足够了，如果企业已经有 Yarn 或者 Mesos 环境，也是很方便部署的。

standalone(集群模式)：典型的Mater/slave模式，不过也能看出Master是有单点故障的；Spark支持ZooKeeper来实现 HA

on yarn(集群模式)： 运行在 yarn 资源管理器框架之上，由 yarn 负责资源管理，Spark 负责任务调度和计算

on mesos(集群模式)： 运行在 mesos 资源管理器框架之上，由 mesos 负责资源管理，Spark 负责任务调度和计算

on cloud(集群模式)：比如 AWS 的 EC2，使用这个模式能很方便的访问 Amazon的 S3;Spark 支持多种分布式存储系统：HDFS 和 S3

5、HDFS读写数据的过程

读：

1、跟namenode通信查询元数据，找到文件块所在的datanode服务器

2、挑选一台datanode（就近原则，然后随机）服务器，请求建立socket流

3、datanode开始发送数据（从磁盘里面读取数据放入流，以packet为单位来做校验）

4、客户端以packet为单位接收，现在本地缓存，然后写入目标文件

写：

1、根namenode通信请求上传文件，namenode检查目标文件是否已存在，父目录是否存在

2、namenode返回是否可以上传

3、client请求第一个 block该传输到哪些datanode服务器上

4、namenode返回3个datanode服务器ABC

5、client请求3台dn中的一台A上传数据（本质上是一个RPC调用，建立pipeline），A收到请求会继续调用B，然后B调用C，将真个pipeline建立完成，逐级返回客户端

6、client开始往A上传第一个block（先从磁盘读取数据放到一个本地内存缓存），以packet为单位，A收到一个packet就会传给B，B传给C；A每传一个packet会放入一个应答队列等待应答

7、当一个block传输完成之后，client再次请求namenode上传第二个block的服务器。

6、RDD中reduceBykey与groupByKey哪个性能好，为什么

reduceByKey：reduceByKey会在结果发送至reducer之前会对每个mapper在本地进行merge，有点类似于在MapReduce中的combiner。这样做的好处在于，在map端进行一次reduce之后，数据量会大幅度减小，从而减小传输，保证reduce端能够更快的进行结果计算。

groupByKey：groupByKey会对每一个RDD中的value值进行聚合形成一个序列(Iterator)，此操作发生在reduce端，所以势必会将所有的数据通过网络进行传输，造成不必要的浪费。同时如果数据量十分大，可能还会造成OutOfMemoryError。

通过以上对比可以发现在进行大量数据的reduce操作时候建议使用reduceByKey。不仅可以提高速度，还是可以防止使用groupByKey造成的内存溢出问题。

7、spark2.0的了解

更简单：ANSI SQL与更合理的API

速度更快：用Spark作为编译器

更智能：Structured Streaming

8、 rdd 怎么分区宽依赖和窄依赖

宽依赖：父RDD的分区被子RDD的多个分区使用 例如 groupByKey、reduceByKey、sortByKey等操作会产生宽依赖，会产生shuffle

窄依赖：父RDD的每个分区都只被子RDD的一个分区使用 例如map、filter、union等操作会产生窄依赖

9、spark streaming 读取kafka数据的两种方式

这两种方式分别是：

Receiver-base

使用Kafka的高层次Consumer API来实现。receiver从Kafka中获取的数据都存储在Spark Executor的内存中，然后Spark Streaming启动的job会去处理那些数据。然而，在默认的配置下，这种方式可能会因为底层的失败而丢失数据。如果要启用高可靠机制，让数据零丢失，就必须启用Spark Streaming的预写日志机制（Write Ahead Log，WAL）。该机制会同步地将接收到的Kafka数据写入分布式文件系统（比如HDFS）上的预写日志中。所以，即使底层节点出现了失败，也可以使用预写日志中的数据进行恢复。

Direct

Spark1.3中引入Direct方式，用来替代掉使用Receiver接收数据，这种方式会周期性地查询Kafka，获得每个topic+partition的最新的offset，从而定义每个batch的offset的范围。当处理数据的job启动时，就会使用Kafka的简单consumer api来获取Kafka指定offset范围的数据。

10、kafka的数据存在内存还是磁盘

Kafka最核心的思想是使用磁盘，而不是使用内存，可能所有人都会认为，内存的速度一定比磁盘快，我也不例外。在看了Kafka的设计思想，查阅了相应资料再加上自己的测试后，发现磁盘的顺序读写速度和内存持平。

而且Linux对于磁盘的读写优化也比较多，包括read-ahead和write-behind，磁盘缓存等。如果在内存做这些操作的时候，一个是JAVA对象的内存开销很大，另一个是随着堆内存数据的增多，JAVA的GC时间会变得很长，使用磁盘操作有以下几个好处：

磁盘缓存由Linux系统维护，减少了程序员的不少工作。

磁盘顺序读写速度超过内存随机读写。

JVM的GC效率低，内存占用大。使用磁盘可以避免这一问题。

系统冷启动后，磁盘缓存依然可用。

11、怎么解决kafka的数据丢失

producer端：

宏观上看保证数据的可靠安全性，肯定是依据分区数做好数据备份，设立副本数。

broker端：

topic设置多分区，分区自适应所在机器，为了让各分区均匀分布在所在的broker中，分区数要大于broker数。

分区是kafka进行并行读写的单位，是提升kafka速度的关键。

Consumer端

consumer端丢失消息的情形比较简单：如果在消息处理完成前就提交了offset，那么就有可能造成数据的丢失。由于Kafka consumer默认是自动提交位移的，所以在后台提交位移前一定要保证消息被正常处理了，因此不建议采用很重的处理逻辑，如果处理耗时很长，则建议把逻辑放到另一个线程中去做。为了避免数据丢失，现给出两点建议：

enable.auto.commit=false 关闭自动提交位移

在消息被完整处理之后再手动提交位移

12、fsimage和edit的区别？

大家都知道namenode与secondary namenode 的关系，当他们要进行数据同步时叫做checkpoint时就用到了fsimage与edit，fsimage是保存最新的元数据的信息，当fsimage数据到一定的大小事会去生成一个新的文件来保存元数据的信息，这个新的文件就是edit，edit会回滚最新的数据。

13、列举几个配置文件优化？

1）Core-site.xml 文件的优化

a、fs.trash.interval，默认值： 0；说明： 这个是开启hdfs文件删除自动转移到垃圾箱的选项，值为垃圾箱文件清除时间。一般开启这个会比较好，以防错误删除重要文件。单位是分钟。

b、dfs.namenode.handler.count，默认值：10；说明：hadoop系统里启动的任务线程数，这里改为40，同样可以尝试该值大小对效率的影响变化进行最合适的值的设定。

c、mapreduce.tasktracker.http.threads，默认值：40；说明：map和reduce是通过http进行数据传输的，这个是设置传输的并行线程数。

14、datanode 首次加入 cluster 的时候，如果 log 报告不兼容文件版本，那需要namenode 执行格式化操作，这样处理的原因是？

1）这样处理是不合理的，因为那么 namenode 格式化操作，是对文件系统进行格式化，namenode 格式化时清空 dfs/name 下空两个目录下的所有文件，之后，会在目录 dfs.name.dir 下创建文件。

2）文本不兼容，有可能时 namenode 与 datanode 的 数据里的 namespaceID、clusterID 不一致，找到两个 ID 位置，修改为一样即可解决。

15、MapReduce 中排序发生在哪几个阶段？这些排序是否可以避免？为什么？

1）一个 MapReduce 作业由 Map 阶段和 Reduce 阶段两部分组成，这两阶段会对数据排序，从这个意义上说，MapReduce 框架本质就是一个 Distributed Sort。

2）在 Map 阶段，Map Task 会在本地磁盘输出一个按照 key 排序（采用的是快速排序）的文件（中间可能产生多个文件，但最终会合并成一个），在 Reduce 阶段，每个 Reduce Task 会对收到的数据排序，这样，数据便按照 Key 分成了若干组，之后以组为单位交给 reduce（）处理。

3）很多人的误解在 Map 阶段，如果不使用 Combiner便不会排序，这是错误的，不管你用不用 Combiner，Map Task 均会对产生的数据排序（如果没有 Reduce Task，则不会排序，实际上 Map 阶段的排序就是为了减轻 Reduce端排序负载）。

4）由于这些排序是 MapReduce 自动完成的，用户无法控制，因此，在hadoop 1.x 中无法避免，也不可以关闭，但 hadoop2.x 是可以关闭的。

16、hadoop的优化？

1）优化的思路可以从配置文件和系统以及代码的设计思路来优化

2）配置文件的优化：调节适当的参数，在调参数时要进行测试

3）代码的优化：combiner的个数尽量与reduce的个数相同，数据的类型保持一致，可以减少拆包与封包的进度

4）系统的优化：可以设置linux系统打开最大的文件数预计网络的带宽MTU的配置

5）为 job 添加一个 Combiner，可以大大的减少shuffer阶段的maoTask拷贝过来给远程的 reduce task的数据量，一般而言combiner与reduce相同。

6）在开发中尽量使用stringBuffer而不是string，string的模式是read-only的，如果对它进行修改，会产生临时的对象，二stringBuffer是可修改的，不会产生临时对象。

7）修改一下配置：以下是修改 mapred-site.xml 文件

a、修改最大槽位数：槽位数是在各个 tasktracker 上的 mapred-site.xml 上设置的，默认都是 2

mapred.tasktracker.map.tasks.maximum

2

mapred.tasktracker.reduce.tasks.maximum

2

b、调整心跳间隔：集群规模小于 300 时，心跳间隔为 300 毫秒

mapreduce.jobtracker.heartbeat.interval.min 心跳时间

mapred.heartbeats.in.second 集群每增加多少节点，时间增加下面的值

mapreduce.jobtracker.heartbeat.scaling.factor 集群每增加上面的个数，心跳增多少

c、启动带外心跳

mapreduce.tasktracker.outofband.heartbeat 默认是 false

d、配置多块磁盘

mapreduce.local.dir

e、配置 RPC hander 数目

mapred.job.tracker.handler.count 默认是 10，可以改成 50，根据机器的能力

f、配置 HTTP 线程数目

tasktracker.http.threads 默认是 40，可以改成 100 根据机器的能力

g、选择合适的压缩方式，以 snappy 为例：

mapred.compress.map.output

true

mapred.map.output.compression.codec

org.apache.hadoop.io.compress.SnappyCodec

17、设计题

1）采集nginx产生的日志，日志的格式为user ip time url htmlId 每天产生的文件的数据量上亿条，请设计方案把数据保存到HDFS上，并提供一下实时查询的功能（响应时间小于3s）

A、某个用户某天访问某个URL的次数

B、某个URL某天被访问的总次数

实时思路是：使用Logstash + Kafka + Spark-streaming + Redis + 报表展示平台

离线的思路是：Logstash + Kafka + Elasticsearch + Spark-streaming + 关系型数据库

A、B、数据在进入到Spark-streaming 中进行过滤，把符合要求的数据保存到Redis中

18、有 10 个文件，每个文件 1G，每个文件的每一行存放的都是用户的 query，每个文件的query 都可能重复。要求你按照 query 的频度排序。 还是典型的 TOP K 算法，

解决方案如下：

1）方案 1：

顺序读取 10 个文件，按照 hash(query)%10 的结果将 query 写入到另外 10 个文件（记为）中。这样新生成的文件每个的大小大约也 1G（假设 hash 函数是随机的）。 找一台内存在 2G 左右的机器，依次对用 hash_map(query, query_count)来统计每个query 出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的 query 和对应的 query_cout 输出到文件中。这样得到了 10 个排好序的文件（记为）。 对这 10 个文件进行归并排序（内排序与外排序相结合）。

2）方案 2：

一般 query 的总量是有限的，只是重复的次数比较多而已，可能对于所有的 query，一次性就可以加入到内存了。这样，我们就可以采用 trie 树/hash_map等直接来统计每个 query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。

3）方案 3：

与方案 1 类似，但在做完 hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如 MapReduce），最后再进行合并。

19、在 2.5 亿个整数中找出不重复的整数，注，内存不足以容纳这 2.5 亿个整数。

1）方案 1：采用 2-Bitmap（每个数分配 2bit，00 表示不存在，01 表示出现一次，10 表示多次，11 无意义）进行，共需内存 2^32 * 2 bit=1 GB 内存，还可以接受。然后扫描这 2.5亿个整数，查看 Bitmap 中相对应位，如果是 00 变 01，01 变 10，10 保持不变。所描完事后，查看 bitmap，把对应位是 01 的整数输出即可。

2）方案 2：也可采用与第 1 题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

20、腾讯面试题：给 40 亿个不重复的 unsigned int 的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那 40 亿个数当中？

1）方案 1：oo，申请 512M 的内存，一个 bit 位代表一个 unsigned int 值。读入 40 亿个数，设置相应的 bit 位，读入要查询的数，查看相应 bit 位是否为 1，为 1 表示存在，为 0 表示不存在。

2）方案 2：这个问题在《编程珠玑》里有很好的描述，大家可以参考下面的思路，探讨一下： 又因为 2^32 为 40 亿多，所以给定一个数可能在，也可能不在其中； 这里我们把 40 亿个数中的每一个用 32 位的二进制来表示 ，假设这 40 亿个数开始放在一个文件中。 然后将这 40 亿个数分成两类:

1.最高位为 0

2.最高位为 1

并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20 亿，而另一个>=20 亿（这相当于折半了）； 与要查找的数的最高位比较并接着进入相应的文件再查找 再然后把这个文件为又分成两类:

1.次最高位为 0

2.次最高位为 1

并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10 亿，而另一个>=10 亿（这相当于折半了）； 与要查找的数的次最高位比较并接着进入相应的文件再查找。

以此类推，就可以找到了,而且时间复杂度为 O(logn)，方案 2 完。

3)附：这里，再简单介绍下，位图方法： 使用位图法判断整形数组是否存在重复 ,判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。

位图法比较适合于这种情况，它的做法是按照集合中最大元素 max 创建一个长度为 max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上 1，如遇到 5 就给新数组的第六个元素置 1，这样下次再遇到 5 想置位时发现新数组的第六个元素已经是 1 了，这说明这次的数据肯定和以前的数据存在着重复。这 种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为 2N。如果已知数组的最大值即能事先给新数组定长的话效 率还能提高一倍。

21、怎么在海量数据中找出重复次数最多的一个？

1）方案 1：先做 hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。

22、上千万或上亿数据（有重复），统计其中出现次数最多的钱 N 个数据。

1）方案 1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用 hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前 N 个出现次数最多的数据了，可以用第 2 题提到的堆机制完成。

23、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词，给出思想，给出时间复杂度分析。

1）方案 1：这题是考虑时间效率。用 trie 树统计每个词出现的次数，时间复杂度是 O(n*le)（le表示单词的平准长度）。然后是找出出现最频繁的前 10 个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是 O(n*lg10)。所以总的时间复杂度，是 O(n*le)与 O(n*lg10)中较大的哪一 个。

24、100w 个数中找出最大的 100 个数。

1）方案 1：在前面的题中，我们已经提到了，用一个含 100 个元素的最小堆完成。复杂度为O(100w*lg100)。

2）方案 2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比 100 多的时候，采用传统排序算法排序，取前 100 个。复杂度为 O(100w*100)。

3）方案 3：采用局部淘汰法。选取前 100 个元素，并排序，记为序列 L。然后一次扫描剩余的元素 x，与排好序的 100 个元素中最小的元素比，如果比这个最小的 要大，那么把这个最小的元素删除，并把 x 利用插入排序的思想，插入到序列 L 中。依次循环，直到扫描了所有的元素。复杂度为 O(100w*100)。

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

1）分析： 常规方法是先排序，在遍历一次，找出重复最多的前 10 条。但是排序的算法复杂度最低为nlgn。

2）可以设计一个 hash_table, hash_map<string, int>，依次读取一千万条短信，加载到hash_table 表中，并且统计重复的次数，与此同时维护一张最多 10 条的短信表。 这样遍历一次就能找出最多的前 10 条，算法复杂度为 O(n)。

大数据面试题大全

需要领取这套大数据面试题的朋友，可以转发此文关注小编，+++V X ：bjmashibing001 来获取啦~~