BAT大数据的面试题 快收藏！

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

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

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

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

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

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

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

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

• 方案 1：在前面的题中，我们已经提到了，用一个含 100 个元素的最小堆完成。复杂度为O(100wlg100)。
• 方案 2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比 100 多的时候，采用传统排序算法排序，取前 100 个。复杂度为 O(100w100)。
• 方案 3：采用局部淘汰法。选取前 100 个元素，并排序，记为序列 L。然后一次扫描剩余的元素 x，与排好序的 100 个元素中最小的元素比，如果比这个最小的 要大，那么把这个最小的元素删除，并把 x 利用插入排序的思想，插入到序列 L 中。依次循环，直到扫描了所有的元素。复杂度为 O(100w*100)。

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

• 分析： 常规方法是先排序，在遍历一次，找出重复最多的前 10 条。但是排序的算法复杂度最低为nlgn。
• 可以设计一个 hash_table, hash_mapstring, int，依次读取一千万条短信，加载到hash_table 表中，并且统计重复的次数，与此同时维护一张最多 10 条的短信表。 这样遍历一次就能找出最多的前 10 条，算法复杂度为 O(n)。

【编辑推荐】

1. 耗时两个月，国内传统企业对Hadoop到底什么态度？
2. 扫盲：Hadoop分布式文件系统（HDFS）基础概念讲解！
3. 使用Scala开发Apache Kafka的TOP 20大好用实践
4. 使用Ambari接管线上Hadoop游戏数据集群的避坑秘籍
5. Hadoop体系结构中的服务解决介绍

（编辑：青岛站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!