【校招VIP】java大数据面试算法题- 校招VIP

文章声明：转载声明：https://blog.csdn.net/zoe_ranxiaosu/article/details/88722610

针对海量数据的处理，可以使用的方法非常多，常见的方法有Hash法、Bit-map(位图)法、Bloom filter法、数据库优化发、倒排索引法、外排序法、Trie树、堆、双层桶法以及MapReduce法等。
其中Hash法、Bit-map(位图)法、Trie树、堆等方法的考查频率最高、使用范围最为广泛。

1.如何从大量的url中找出相同的url
题目：给定a、b两个文件，各存放50亿个url，每个url各占64个字节，内存限制是4GB，请找出a、b两个文件共同的url.

解答：
因为每个url需要占64个字节，所以50亿个url占用空间的大小为50亿*64=5GB*64=320GB。
由于内存大小只有4GB，因此不可能一次性把所有的url都加载到内存中处理。
对于这个类型的题目，一般都需要使用分治法，即把一个文件中的url按照某一特征分成多个文件，使得每个文件的内容都小于4GB，这样就可以把这个文件一次性读到内存中进行处理

主要思路：
(1) 遍历文件a，对遍历到的url求hash(url)%500,根据计算结果把遍历到的url分别存储到a0,a1,a2,~,a499(计算结果为i的url存储到文件ai中)，这样每个文件的大小约为600MB。当某一文件中url的大小超过2GB时，可以按照类似的思路把这个文件继续分为更小的子文件（例如，如果a1大小超过2GB时，那么可以把文件继续分为a11,a12,~）

(2)使用同样的方法遍历文件b，把文件b中的url分别存储到文件b0,b1,~,b499中。

(3)通过上面的划分，与ai中url相同的url一定在bi中。由于ai与bi中所有的url的大小不会超过4GB，因此可以把它们同时读入到内存中进行处理。
具体思路：遍历文件ai，把遍历到的url存入到hash_set中，接着遍历文件bi中的url，如果这个url在hash_set中存在，那么说明这个url是这两个文件共同的url，可以把这个url保存到另外一个单独的文件中。当把文件a0~a499都遍历完成后，就找到了两个文件共同的url。

2.如何从大量数中找到高频词
题目：有一个1GB大小的文件，文件里面每一行是一个词，没个词的大小不超过16个字节，内存大小限制是1MB，要求返回频率最高的100个词。

解答：
由于文件大小为1GB，而内存大小只有1MB，因此不可能一次把所有的词读入到内存中处理，需要采用分治的方法，把一个大的文件分解成多个小的子文件，从而保证每个文件的大小都小于1MB，进而可以直接被读取到内存中处理。

具体思路：
（1）遍历文件，对遍历到的每一个词，执行如下hash操作：hash(x)%2000,将结果为i的词存放到文件ai中。
通过这个分解步骤，可以使每个子文件的大小为400KB左右。如果这个操作后某个文件的大小超过1MB了，那么就可以采用相同的方法对这个文件继续分解，直到文件小于1MB为止。

（2）统计出每个文件中出现频率最高的100个词。
最简单的方法为，使用hash_map来实现，具体实现方法：遍历文件中的所有词，对遍历到的词，如果在hash_map中不存啊，那么把这个词存入hash_map中，如果这个词在hash_map中已经存在了，那么把这个词对应的值加1。遍历完后可以非常容易低找出出现频率最高的100个词。

（3）第二步找出了每个文件出现频率最高的100个词，这一步可以通过维护一个小顶堆来找出所有词中出现频率最高的100个。
具体方法：遍历第一个文件，把第一个文件中出现频率最高的100个词构建成一个小顶堆（如果第一个文件中词的个数小于100，可以继续遍历第二个文件，直到构建好有100个结点的小顶堆为止）。
继续遍历，如果遍历到的词的出现次数大于顶堆上词的出现次数，可以用新遍历到的词替换堆顶的词，然后重新调整这个堆为小顶堆。
当遍历完所有的文件后，这个小顶堆中的词就是出现频率最高的100个词。
当然这一步也可以采用类似归并排序的方法把所有文件中出现频率最高的100个词排序，最终找出出现频率最高的100个词。

其实就是hadoop中mapreduce方法的一个Java设计

3.如何找出某一天访问百度网站最多的IP
问题：现有海量日志数据堡村在一个超级大的文件中，该文件无法直接读入内存，要求从中提取某天访问百度次数最多的那个IP
解答：
依然采用分而治之，但这个大文件分为多少小文件是一个重点。
以IPv4为例，由于一个IP地质占用32位，因此最多会有2^32种取值情况。
如果使用hash(IP)%1024值，那么就把海量IP日志分别存储到1024个小文件种。
这样，每个小文件最多包含4MB个IP地质。如果使用2048个小文件，那么每个文件就会最多包含2MB个IP地址。
因此，对于这类题目而言，首先需要确定可用内存的大小，然后确定数据的大小。
由这两个参数就可以确定hash函数应该怎么设置才能保证每个文件的大小都不超过内存大小，从而可以保证每个小的文件都能被一次性加载到内存中。

4.如何在大量的数据中找出不重复
题目：在2.5亿个整数中找出不重复的整数。注意：内存不足以容纳这2.5亿个整数。

解答：
分治法（略）
位图法：
对于整数相关的算法的求解，位图法是一种非常实用的算法。
对本题而言，如果可用内存空间超过1GB就可以使用这种方法。

具体思路：
假设整数占用4个字节（如果占用8个字节，则求解思路类似，只不过需要占用更大的内存），4个字节也就是32位，可以表示的整数的个数为2^32。
由于本题只查找不重复的数，而不关心具体数字出现的次数，因此可以分别使用2个bit来表示各个数字的状态：用00表示这个数字没有出现过，01表示出现过1次，10表示出现了多次，11暂不使用。

根据上述逻辑，在遍历这2.5亿个整数时，如果这个整数对应的位图中的位为00，那么就修改成01；
如果为01则修改为10；如果为10则保持原值不变。这样当所有数据遍历完成后，可以再遍历一遍位图，位图中为01对应的数字就没有重复的数字。