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系统布局中的处事办理先容

（编辑：湖南网）

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