1、你让工人为你工作7天，给工人的回报是一根金条。金条平分成相连的7段 ，你必须在每天结束时给他们一段金条，如果只许你两次把金条弄断，你如何给你 的工人付费？

微软面试100题(含参考答案)

这个是我在微软面试BI工程师的上机题，希望对你有用，非常珍贵喔！不懂可以问我。

六、数据库索引 适用范围：大数据量的增删改查 基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。 七、倒排索引(Inverted index) 适用范围：搜索引擎，关键字查询 基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词 在一个文档或者一组文档中的存储位置的映射。 以英文为例，下面是要被索引的文本： T0 = "it is what it is" T1 = "what is it" T2 = "it is a banana" 我们就能得到下面的反向文件索引： "a": {2} "banana": {2} "is": {0, 1, 2}

密匙二、双层桶划分 双层桶划分----其实本质上还是分而治之的思想，重在“分”的技巧上！ 适用范围：第 k 大，中位数，不重复或重复的数字 基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步

 第一章、左旋转字符串  第二章、字符串是否包含问题  第三章、寻找最小的 k 个数  第三章续、Top K 算法问题的实现  第三章再续：快速选择 SELECT 算法的深入分析与实现  三之三续、求数组中给定下标区间内的第 K 小（大）元素  第四章、现场编写类似 strstr/strcpy/strpbrk 的函数  第五章、寻找满足条件的两个或多个数  第六章、求解 500 万以内的亲和数  第七章、求连续子数组的最大和  第八章、从头至尾漫谈虚函数  第九章、闲话链表追赶问题  第十章、如何给 10 7̂ 个数据量的磁盘文件排序  第十一章、最长公共子序列（LCS）问题  第十二~十五章：数的判断，中签概率，IP 访问次数，回文问题（初稿）  第十六~第二十章：全排列，跳台阶，奇偶排序，第一个只出现一次等问题  第二十一~二十二章：出现次数超过一半的数字，最短摘要的生成  第二十三、四章：杨氏矩阵查找，倒排索引关键词 Hash 不重复编码实践  第二十五章：Jon Bentley：90%无法正确实现二分查找  第二十六章：基于给定的文档生成倒排索引的编码与实践  第二十七章：不改变正负数之间相对顺序重新排列数组 作者声明：本人 July 对以上所有任何内容和资料享有版权，转载请注明作者本人 July 及 出处。向你的厚道致敬。谢谢。二零一一年十月十三日、以诸君为傲。

（1）递归实现 从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如 此递归处理，从而 得到所有元素的全排列。算法实现如下： #include #include using namespace std; template void CalcAllPermutation_R(T perm[], int first, int num) { if (num <= 1) { return; } for (int i = first; i < first + num; ++i) { swap(perm[i], perm[first]); CalcAllPermutation_R(perm, first + 1, num - 1);

(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 时，内部是如何具体实现的？若想将其内存释放，该如何操作？ 二、系统设计 正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过滤系统，