算法未总结左程云算法
Source
Edit
History

undefined

大数据题目解题技巧：

1)哈希函数可以把数据按照种类均匀分流

2)布隆过滤器用于集合的建立与查询，并可以节省大量空间

3)一致性哈希解决数据服务器的负载管理问题

4)利用并查集结构做岛问题的并行计算

5)位图解决某一范围上数字的出现情况，并可以节省大量空间 6)利用分段统计思想、并进一步节省大量空间 7)利用堆、外排序来做多个处理单元的结果合并

这类问题面试官希望我们可以提问题，把模糊的问题抽象化

一、题目一

32位无符号整数的范围是0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文 件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有 未出现过的数?

解法一：比特数组，范围是：[0 到 pow(2,32)-1]。如果准备一个 bit 数组，数组需要：pow(2, 32) / 8 = 500M 左右，则可以把所有的整数存储在这个数组中，直接遍历即可

进阶：内存限制为 3KB，但是只用找到一个没出现过的数即可

解法二：利用词频统计不够，划分范围来解决

  1. 比如给内存 3KB，首先要确认数组长度，找到所给内存能申请数组的长度（离2的N次方最近的）（3*1024 / 4 最接近 512）（4 是无符号整数）
  2. 把所给的整数按范围分成 512 份。范围一共是 pow(2, 32) 个数字。 一份是 pow(2,32) / 512 = pow(2, 23) = 8388608 ，比如第一份表示范围 0 - 8388608。第二份表示 8388609 - 8388608+8388608 。依次类推
  3. 然后遍历这 40 亿个无符号整数，这些整数处于那个范围，对应数组的那个元素，就给数组的那个元素自增。因为40 亿个无符号肯定有那个范围的数字没有，导致数组的那个元素的值不为 8388608。找到这个整数范围。在将这个整数范围划分成 512 份，遍历所有整数。依次类推，总能找到没有出现的数字

高级：假设只能申请有限几个变量，找到一个没出现过的数

二分的思路，将这个范围先进行二分，定义两个变量 A 和 B，分别对应两个范围 [0 - pow(2, 16)-1] 和 [pow(2, 16), pow(2, 32)]。 遍历所有整数，落在 [0 - pow(2, 16)-1] 区间的让 A 变量自增，同理，落在 [pow(2, 16), pow(2, 32)] 区间的让 B 变量自增。肯定有个区间，有个变量的不够 pow(2, 16) 这么大，因为只有 40 亿个数字，那就继续在这个区间查找，继续二分。最多 32 次二分，也就是最多遍历 32 次所有整数。即可找到没有出现过的数

二、题目二

有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL

  1. 哈希分流，分流到多个小文件，然后在小文件中进行寻找重复的 URL，然后合并。
  2. 布隆过滤器，但是会有一定的失误率。边添加这个集合的时候边查询，每次添加之前先查询看能否找到这个 URL，如果可以找到就把它记录在最终的文件中

【补充】某搜索公司一天的用户搜索词汇是海量的(百亿数据量)，请设计一种求出每天热门Top100 词汇的可行办法

  1. 哈希分流，将大文件通过哈希函数将 URL 分流到多个小文件。然后分别统计出每个小文件中的词频个数
  2. 每个小文件中的词频通过一个大根堆进行排名，得到一个小文件的词频排名
  3. 建立一个总的大根堆，用于汇总所有的小文件的大根堆。如何汇总。先取所有小根堆上的堆顶元素，放到总的大根堆。然后总的大根堆依次弹出，弹出那个小文件的大根堆的元素，就从那个小文件的大根堆去补元素。即可求出 Top 任意

三、题目三

32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的 内存，找出所有出现了两次的数。

哈希函数分流分成小文件，然后对于每个小文件进行内存操作，最后汇总即可

也可以使用两位（两个bit）来存储每个整数的出现频率。比如：00 表示 0 次，01 表示 1 次，10 表示 2 次，11 表示大于 2 次。那么总共需要 pow(2, 32) * 2 / 8 = pow(2, 30) 字节，差不多刚好 1G 的空间。

【补充】 可以使用最多10MB的内存，怎么找到这40亿个整数的中位数?

划分范围的思想

  1. 有 10M 内存，首先确认数组的长度，找到所给内存能申请数组的最大长度（离 2 的 N 次方最近的）（10M / 4B = 2621440）（4 是无符号整数），假设数组长度为 X 。
  2. 把所给的整数按范围划分成 X 份，整数范围一共是 pow(2, 32) 个数字。划分成 X 份。假设每份会有 Y 个整数。比如第一份是 [0, Y-1] 、[Y, 2*Y-1] 依次类推。
  3. 然后遍历这 40 亿个整数，这些整数处于那个范围，对应到数组上的那个元素，就让数组的那个元素自增。
  4. 然后再遍历数组，因为要找中位数，用一个变量，依次增加数组元素，增加到大于等于 20 亿停止，就确认了中位数存在这个范围。然后再这个范围划分成 X 份，依次进行上述过程。即可最终确定中位数

四、题目四

假设有一个 10G 的文件，文件中存储着无序的有符号整数，只给 5G / 5M / 5K 的内存。将这些整数排序，然后输出到一个文件

解法一：范围内统计（小根堆）

  1. 先划分范围，拿到所给定的内存，建立小根堆，堆中元素为[整数、词频]，注意小根堆中是按照整数的大小进行排序的。
  2. 比如，整数占 4 个字节，词频占 4 个字节。堆中一个元素就是 8 个字节。那 5M 的内存可以容纳：5 * pow(2,20) / 8 = pow(2, 19) ，记做 X 。
  3. 然后把有符号整数这个范围 [-pow(2, 31), pow(2, 31)-1] 进行分割，每份 X 个元素，分成 N 个。变成 [0, X-1]、[X, 2*X-1] 等等。这些区间之间就是递增的
  4. 然后遍历这个 10G 的文件，先去填充第一个区间，也就是填充小根堆中整数和词频。第一个区间也就是整个文件最小的数字集合。通过小根堆也就是排好序了，然后输入到结果文件。依次利用小根堆拍第二个区间、第 N 个区间。

解法二：多次遍历记录当前极大值

  1. 拿到给定内存，建立大根堆，堆中元素为[整数、词频]，注意大根堆中是按照整数的大小进行排序的。
  2. 比如，整数占 4 个字节，词频占 4 个字节。堆中一个元素就是 8 个字节。那 5M 的内存可以容纳：5 * pow(2,20) / 8 = pow(2, 19) ，记做 X 。也就是说 这个堆中可以容纳 X 个元素
  3. 然后遍历这个 10G的文件，依次输入大根堆整数，如果相等，就增加词频，如果大于堆顶元素，就跳过，如果小于堆顶元素，就加入到堆中（堆满的时候要弹出最大元素）。这样遍历完之后，我们排序好了堆中的元素。也就是10G 文件中最小的一批元素，我们同时使用一个变量 Y 记住当前的堆顶元素的整数值。然后将这个堆中元素输出到文件中。
  4. 再次遍历这个 10G 的文件，因为在上一次遍历中已经记住了上一批元素的最大整数 Y。这次遍历文件遇到小于等于整数 Y 的直接跳过。遍历完更新 Y 的值，然后输出堆中元素到文件中
  5. 依次遍历，总有一次 Y 的值等于有符号整数范围最大值，或者某次堆中元素不满的情况，就说明总体排序完成。

五、题目五

位运算的题目

给定两个有符号32位整数a和b，返回a和b中较大的。要求：不用做任何比较判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class BitOperation {
private:
    // 请保证参数 n，不是 1 就是 0
    // 参数为 1，返回 0
    // 参数为 0，返回 1
    static int flip(int n) {
        return n ^ 1;
    }
    // 参数为非负数，返回 1
    // 参数为负数，返回 0
    static int sign(int n) {
        return flip((n >> 31) & 1 );
    }

public:
    int getMax_1(int a, int b) {
        int c = a - b;
        int scA = sign(c); // a-b 为非负，scA 为 1；a-b 为负，scA 为 0
        int scB = flip(scA); // scA 为 1，scB 为 0；scA 为 0，scB 为 1
        // scA 和 scB 之间是互斥的，即两个是相反数，如下两种情况
        // scA 为 1，说明 a-b 为非负，a >= b，且 scB 为 0，则返回 a * scA = a
        // scA 为 0，说明 a-b 为负，a < b, 且 scB 为 1，则返回 b * scB = b
        return a * scA + b * scB;
    }
    // getMax_1 有个问题，c = a-b 可能会溢出，比如 a 是负数，b 是正数，因此还有新的方案
    int getMax_2(int a, int b) {
        int c = a - b;
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);
        int difSab = sa ^ sb; // a 和 b 的符号不一样，为 1，一样，为 0
        int sameSab = flip(difSab); // a 和 b 的符号一样，为 1，不一样，为 0
        // 返回 returnA 的条件
        // 1. 如果 a 和 b 符号相同，则 a-b 不会溢出，并且 a-b >= 0 就返回 a
        // 2. 如果 a 和 b 符号不相同，且 a 自己大于 0 (可能会溢出) 就返回 a
        // difSab * sa：a 和 b 符号不同的情况下，a 为非负才返回 a
        // sameSab * sc：a 和 b 符号相同的情况下，a-b >= 0 才返回 a
        // 这两个条件互斥。difSab 和 sameSab 互斥，符号不相同
        int returnA = difSab * sa + sameSab * sc;
        // 返回 returnB 的条件：和 returnA 的条件一定互斥，因为返回 a 一定不会返回 b；返回 b 一定不会返回 a
        int returnB = flip(returnA);
        // returnA 和 returnB 要么为 0 要么为 1，且两者之间互斥。因此：a * returnA 和 b * returnB 两个条件互斥 
        return a * returnA + b * returnB;
    }
};

六、题目六

判断一个32位正数是不是2的幂、4的幂

2 的幂含义：一个数的二进制所有位上只有一个位为 1

x & (x-1) == 0 可以判断。或者把那个位上的 1 取出来，和原数（2^n）比较即可。

4 的幂含义：首先这个数的二进制所有位上只有一个位上为 1，并且这个位在 0、2、4、6... 位置

  1. 首先判断是不是只有一个 1，也就是判断是 2 的幂
  2. 然后 x & 010101...01 判断是否为 0，为 0 则不是，不为 0 则是
1
2
3
4
5
6
bool is2Power(int n) {
	return (n & (n-1)) == 0;
}
bool is4Power(int n) {
	return (n & (n-1)) == 0 && (n & 0x55555555) != 0;
}

七、题目七

给定两个有符号32位整数a和b，不能使用算术运算符，分别实现a和b的加、减、乘、除运 算

【要求】如果给定a、b执行加减乘除的运算结果就会导致数据的溢出，那么你实现的函数不必对此 负责，除此之外请保证计算过程不发生溢出

两数相加：

  • 两个二进制数异或不会产生进位，也称为无进位相加
  • 两个二进制数相与，然后向左移一位，结果就是两数相加之后的进位信息

因此，两数相加等于 （这两个数异或的值 + 这两个数相与然后左移一位的值），那么括号里的相加又等于 （两个数异或的值 + 两个数相与然后左移一位的值）。依次类推，直到进位为0，也就是两个数相与为 0 时。两数异或的结果就是最终值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// a+b 不能溢出
int add(int a, int b) {
	int sum = a;
	while (b != 0) {
		sum = a ^ b; // 无进位相加的结果
		b = (a & b) << 1; // 进位信息
		a = sum;
	}
	return sum;
}
// 如果一个正数和一个负数除符号位不同，其他位均相同的话，那么他们互为相反数。从这个规则可知，如果我们将一个正数的符号位取反，那么将得到这个数用原码表示的相反数。同时，我们知道计算机里面的数是用补码形式存储的，而且负数的补码是原码除符号位外其余位取反加1
// 返回一个数的相反数。任何一个数的相反数就是这个数取反+1 
int negNum(int n) {
	return add(~n, 1);
}
// 减法，就是 a 和 b 的相反数相加 
int minus(int a, int b) {
	return add(a, negNum(b));
}

两数相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int multi(int a, int b) {
    int res = 0;
    // 转换成无符号数，便于下面移动时带上符号一起移动。
    unsigned unsigned_b = (unsigned)b;
    while (unsigned_b != 0) {
    	// b 的最右的那一位不为 0 
        if ((unsigned_b & 1) != 0) {
            res = add(res, a);
        }
        a <<= 1;
        unsigned_b >>= 1;
    }
    return res;
}

两数相除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool isNeg(int n) {
    return n < 0;
}
int div(int a, int b) {
    int x = isNeg(a) ? negNum(a) : a;
    int y = isNeg(b) ? negNum(b) : b;
    int res = 0;
    for (int i = 31; i > -1; i = minus(i, 1)) {
        // y 左移可能会溢出，因此让 x 右移保证安全
        // 也就是说，将 y 左移到一个合适的位置（刚好不比 x 大的位置）。那么移动的这一位肯定是因子的一个位
        if ((x >> i) >= y) {
            res |= (1 << i);
            x = minus(x, y << i);
        }
    }
    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}
// 需要处理除法负数的问题
int divide(int a, int b) {
    if (b == 0) {
        std::cout << "divisor is 0" << std::endl;
        throw ("divisor is 0");
    }
    if (a == INT_MIN && b == INT_MIN) {
        return 1;
    } else if (b == INT_MIN) {
        return 0;
    } else if (a == INT_MIN) {
        int res = div(add(a, 1), b);
        return add(res, div(minus(a, multi(res, b)), b));
    } else {
        return div(a, b);
    }
}