数据处理面试题(2)

时间：2024-07-19 09:48:11 学人智库我要投稿

相关推荐

数据处理面试题(2)

　　方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(100w*100)。

数据处理面试题(2)

　　方案3：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。

　　13. 寻找热门查询：

　　搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

　　(1) 请描述你解决这个问题的思路;

　　(2) 请给出主要的处理流程，算法，以及算法的复杂度。

　　方案1：采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

　　14. 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数中的中数?

　　方案1：先大体估计一下这些数的范围，比如这里假设这些数都是32位无符号整数(共有2^32个)。我们把0到2^32-1的整数划分为N个范围段，每个段包含(2^32)/N个整数。比如，第一个段位0到2^32/N-1，第二段为(2^32)/N到(2^32)/N-1，…，第N个段为(2^32)(N-1)/N到2^32-1。然后，扫描每个机器上的N个数，把属于第一个区段的数放到第一个机器上，属于第二个区段的数放到第二个机器上，…，属于第N个区段的数放到第N个机器上。注意这个过程每个机器上存储的数应该是O(N)的。下面我们依次统计每个机器上数的个数，一次累加，直到找到第k个机器，在该机器上累加的数大于或等于(N^2)/2，而在第k-1个机器上的累加数小于(N^2)/2，并把这个数记为x。那么我们要找的中位数在第k个机器中，排在第(N^2)/2-x位。然后我们对第k个机器的数排序，并找出第(N^2)/2-x个数，即为所求的中位数的复杂度是O(N^2)的。

　　方案2：先对每台机器上的数进行排序。排好序后，我们采用归并排序的思想，将这N个机器上的数归并起来得到最终的排序。找到第(N^2)/2个便是所求。复杂度是O(N^2*lgN^2)的。

　　15. 最大间隙问题

　　给定n个实数，求着n个实数在实轴上向量2个数之间的最大差值，要求线性的时间算法。

　　方案1：最先想到的方法就是先对这n个数据进行排序，然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法：

　　找到n个数据中最大和最小数据max和min。

　　用n-2个点等分区间[min, max]，即将[min, max]等分为n-1个区间(前闭后开区间)，将这些区间看作桶，编号为，且桶i 的上界和桶i+1的下届相同，即每个桶的大小相同。每个桶的大小为：。实际上，这些桶的边界构成了一个等差数列(首项为min，公差为)，且认为将min放入第一个桶，将max放入第n-1个桶。

　　将n个数放入n-1个桶中：将每个元素x[i] 分配到某个桶(编号为index)，其中，并求出分到每个桶的最大最小数据。

　　最大间隙：除最大最小数据max和min以外的n-2个数据放入n-1个桶中，由抽屉原理可知至少有一个桶是空的，又因为每个桶的大小相同，所以最大间隙不会在同一桶中出现，一定是某个桶的上界和气候某个桶的下界之间隙，且该量筒之间的桶(即便好在该连个便好之间的桶)一定是空桶。也就是说，最大间隙在桶i的上界和桶j的下界之间产生j>=i+1。一遍扫描即可完成。

　　16. 将多个集合合并成没有交集的集合

　　给定一个字符串的集合，格式如：。要求将其中交集不为空的集合合并，要求合并完成的集合之间无交集，例如上例应输。

　　(1) 请描述你解决这个问题的思路;

　　(2) 给出主要的处理流程，算法，以及算法的复杂度;

　　(3) 请描述可能的改进。

　　方案1：采用并查集。首先所有的字符串都在单独的并查集中。然后依扫描每个集合，顺序合并将两个相邻元素合并。例如，对于，首先查看aaa和bbb是否在同一个并查集中，如果不在，那么把它们所在的并查集合并，然后再看bbb和ccc是否在同一个并查集中，如果不在，那么也把它们所在的并查集合并。接下来再扫描其他的集合，当所有的集合都扫描完了，并查集代表的集合便是所求。复杂度应该是O(NlgN)的。改进的话，首先可以记录每个节点的根结点，改进查询。合并的时候，可以把大的和小的进行合，这样也减少复杂度。

　　17. 最大子序列与最大子矩阵问题

　　数组的最大子序列问题：给定一个数组，其中元素有正，也有负，找出其中一个连续子序列，使和最大。

　　方案1：这个问题可以动态规划的思想解决。设b[i]表示以第i个元素a[i]结尾的最大子序列，那么显然。基于这一点可以很快用代码实现。

　　最大子矩阵问题：给定一个矩阵(二维数组)，其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。

　　方案2：可以采用与最大子序列类似的思想来解决。如果我们确定了选择第i列和第j列之间的元素，那么在这个范围内，其实就是一个最大子序列问题。如何确定第i列和第j列可以词用暴搜的方法进行。

　　第二部分、海量数据处理之Bti-map详解

　　Bloom Filter已在上一篇文章海量数据处理之Bloom Filter详解中予以详细阐述，本文接下来着重阐述Bit-map。有任何问题，欢迎不吝指正。

　　什么是Bit-map

　　所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

　　如果说了这么多还没明白什么是Bit-map，那么我们来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit(1Bytes)，首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0(如下图：)

　　然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending),因为是从零开始的，所以要把第五位置为一(如下图)：

　　然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：

　　然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出(2，3，4，5，7)，这样就达到了排序的目的。下面的代码给出了一个BitMap的用法：排序。

　　view plain

　　//定义每个Byte中有8个Bit位

　　#include

　　#define BYTESIZE 8

　　void SetBit(char *p, int posi)

　　{

　　for(int i=0; i < (posi/BYTESIZE); i++)

　　{

　　p++;