以后的部分题目来源将取自下文-introduction to 3d game programming with directx12 (龙书dx12版) pdf

同时，程序员编程艺术系列将重新开始创作，第十一章以后的部分题目来源将取自下文 中的 17 道海量数据处理的面试题。因为，我们觉得，下文的每一道面试题都值得重新思考， 重新深究与学习。再者，编程艺术系列的前十章也是这么来的。若您有任何问题或建议，欢 迎不吝指正。谢谢。 第一部分、十五道海量数据处理面试题 1. 给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让 你找出 a、b 文件共同的 url？ 方案 1：可以估计每个文件安的大小为 50G×64=320G，远远大于内存限制的 4G。所 以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。 1. 遍历文件 a，对每个 url 求取 1000)%(urlhash ，然后根据所取得的值将 url 分别存 储到 1000 个小文件（记为 99910 ,,, aaa  ）中。这样每个小文件的大约为 300M。 2. 遍历文件 b，采取和 a 相同的方式将 url 分别存储到 1000 小文件中（记为 99910 ,,, bbb  ）。这样 处理 后，所 有可能 相同的 url 都在 对应的 小文件 （ 9999991100 ,,, bvsabvsabvsa  ）中，不对应的小文件不可能有相同的 url。然后 我们只要求出 1000 对小文件中相同的 url 即可。 3. 求每对小文件中相同的 url 时，可以把其中一个小文件的 url 存储到 hash_set 中。 然后遍历另一个小文件的每个 url，看其是否在刚才构建的 hash_set 中，如果是， 那么就是共同的 url，存到文件里面就可以了。 方案 2：如果允许有一定的错误率，可以使用 Bloom filter，4G 内存大概可以表示 340 亿 bit。将其中一个文件中的 url 使用 Bloom filter 映射为这 340 亿 bit，然后挨个读取另外一 个文件的 url，检查是否与 Bloom filter，如果是，那么该 url 应该是共同的 url（注意会有一 定的错误率）。