(1) 请描述你解决这个问题的思路； (2) 请给出主要的处理流程，算法，以及算法的复杂度。 方案 1：采用 trie 树，关键字域存该查询串出现的次数，没有出现为 0。最后用 10 个 元素的最小推来对出现频率进行排序。 关于此问题的详细解答，请参考此文的第 3.1 节：第三章续、Top K 算法问题的实现。 14. 一共有 N 个机器，每个机器上有 N 个数。每个机器最多存 O(N)个数并对它们操作。如 何找到 N^2 个数中的中数？ 方案 1：先大体估计一下这些数的范围，比如这里假设这些数都是 32 位无符号整数（共 有 2 3̂2 个）。我们把 0 到 2 3̂2-1 的整数划分为 N 个范围段，每个段包含（2 3̂2）/N 个整 数。比如，第一个段位 0 到 2 3̂2/N-1，第二段为（2 3̂2）/N 到（2^32）/N-1，…，第 N 个 段为（2 3̂2）（N-1）/N 到 2 3̂2-1。然后，扫描每个机器上的 N 个数，把属于第一个区段的 数放到第一个机器上，属于第二个区段的数放到第二个机器上，…，属于第 N 个区段的数 放到第 N 个机器上。注意这个过程每个机器上存储的数应该是 O(N)的。下面我们依次统计

同时，程序员编程艺术系列将重新开始创作，第十一章以后的部分题目来源将取自下文 中的 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（注意会有一 定的错误率）。

一、算法设计 1、设 rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为 R 的圆内找随机 n 个点，并给出时间复杂度分析。 2、为分析用户行为，系统常需存储用户的一些 query，但因 query 非常多，故系统不能全 存，设系统每天只存 m 个 query，现设计一个算法，对用户请求的 query 进行随机选择 m 个，请给一个方案，使得每个 query 被抽中的概率相等，并分析之，注意：不到最后一刻， 并不知用户的总请求量。 3、C++ STL 中 vector 的相关问题： （1）、调用 push_back 时，其内部的内存分配是如何进行的？ （2）、调用 clear 时，内部是如何具体实现的？若想将其内存释放，该如何操作？ 二、系统设计 正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过滤系统，

（2）合并链表 ANSWER Reversing a linked list. Already done. What do you mean by merge? Are the original lists sorted and need to be kept sorted? If not, are there any special requirements? I will only do the sorted merging. Node * merge(Node * h1, Node * h2) { if (h1 == NULL) return h2; if (h2 == NULL) return h1; Node * head; if (h1->data>h2->data) { head = h2; h2=h2->next; } else { head = h1; h1=h1->next; } Node * current = head; while (h1 != NULL && h2 != NULL) { if (h1 == NULL || (h2!=NULL && h1->data>h2->data)) { current->next = h2; h2=h2->next; current = current->next; } else { current->next = h1; h1=h1->next; current = current->next; } } current->next = NULL; return head;

Frank D. Luna 龙书 最新版 DX12

版权归作者所有，任何形式转载请联系作者。 作者：breaker（来自豆瓣） 来源：https://book.douban.com/review/5729576/ 1. 读完龙书是做不了你当初想象中的 3D 游戏的。 2. 龙书对 Engine Programmer 和 Gameplay Programmer 都有意义，毕竟是 D3D 入门之入门，但读法上需有差异：引擎程序员需精研提炼为我而用，游戏性程序员应略读练习了解功能。 3. 请从这个版本开始读 Introduction to 3D Game Programming with DirectX 9.0c: A Shader Approach

DX12龙书用的框架代码,博客会有一系列使用教程

myd3d12book 源码

DX12 3D游戏开发 ！！！英文版！！！！ 配套书籍C++源码

源代码