经典的C语言程序设计习题，共100题，内附有答案与习题简略解析；
题目：有1、2、3、4 个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？
1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件
的排列。
2.程序源代码：
2021-08-20 14:22:45
384KB
1
同时，程序员编程艺术系列将重新开始创作，第十一章以后的部分题目来源将取自下文
中的 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（注意会有一
定的错误率）。
2021-08-14 02:57:53
4.43MB
1
一、算法设计
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 时，内部是如何具体实现的？若想将其内存释放，该如何操作？
二、系统设计
正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过滤系统，
2021-08-14 02:22:11
4.43MB
1
（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;
2021-08-14 01:53:32
4.43MB
1