【15】大数据题目等

一.大数据题目的解题技巧编辑

二.找重复的URL

三.利用小内存找出所有出现两次的数。

四.位运算题目

五.面试原题

六,.判断一个32位正数是不是2的幂，4的幂

七.位运算实现加减乘除

加法

减法

乘法

除法

一.大数据题目的解题技巧

二.找重复的URL

方法一是使用布隆过滤器（边添加边查询，存在很小的失误率）

方法二是哈希分流（哈希分类可可以较匀地将文件分流到几个小文件，相同的文件一定会被分到同一个文件中，然后进一步查找重复的URL）。每个小文件都维护一个Top100的大根堆，然后取每个小文件大根堆的堆顶元素放到总堆中，然后每次取总堆堆顶就是频次最高的词汇。例如取出甲，知道甲是第二个堆的，那么就将甲弹出，然后将下一个最大值丙放入总堆中。。。周而复始

三.利用小内存找出所有出现两次的数。

方法一：Hash函数按种类均匀分流，将40亿个数根究允许的内存大小，用Hash函数分成多个小文件（使用的是银硬盘空间），然后再在每个小文件中在内存中进行查找出现两次的数，最后将所有小文件中出现两次的数汇总就是答案。

方法二：使用位图，用2个bit位来表示一个数的状态，【00 01 10 11】 = 【0次 1次 2次 >2次】。这样处理的话，需要使用的空间是2^32*2/8Byte空间，1GB是可以搞定的。

四.位运算题目

技巧：将互斥的两个条件可以用加号连接。

	// 请保证参数n，不是1就是0的情况下// 1 -> 0// 0 -> 1public static int flip(int n) {return n ^ 1;}// n是非负数，返回1// n是负数，返回0public static int sign(int n) {return flip((n >> 31) & 1);} public static int getMax1(int a, int b) {int c = a - b;int scA = sign(c); // a-b位非负, scA为1. a-b是负, scA为0int scB = flip(scA); // scA为0， return a * scA + b * scB;}public static int getMax2(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， 一样， 返回0int sameSab = flip(difSab); // a和b符号一样， 返回1，不一样， 返回0 int returnA = difSab * sa + sameSab * sc;int returnB = flip(returnA);return a * returnA + b * returnB;}public static void main(String[] args) {int a = -16;int b = 1;System.out.println(getMax1(a, b));System.out.println(getMax2(a, b));a = 2147483647;b = -2147480000;System.out.println(getMax1(a, b)); // wrong answer because of overflowSystem.out.println(getMax2(a, b));}

五.面试原题

有一个10G的无序有符号整数文件，如何通过5G的内存生成一个新文件，要求文件里面的数据是有序的。

为什么是统计词频，而不是将小范围的数值直接放入到小根堆中？

这是因为可以某些数的重复次数过多，然后可能会爆掉小根堆。然而换成统计词频（不论某个数出现多少次，占用的内存都是一个定值而已）

六,.判断一个32位正数是不是2的幂，4的幂

判断是否为2的幂：

方法一：取到最右侧的1，然后判断和原数相不相等。

方法二：判断x&(x-1)==0是否成立。

判断是否为4的幂：

七.位运算实现加减乘除

加法

	public static int add(int a, int b) {int sum = a;while (b != 0) {sum = a ^ b;b = (a & b) << 1;a = sum;}return sum;}

减法

	public static int add(int a, int b) {int sum = a;while (b != 0) {sum = a ^ b;b = (a & b) << 1;a = sum;}return sum;}public static int negNum(int n) {return add(~n, 1);}public static int minus(int a, int b) {return add(a, negNum(b));}

乘法

	public static int multi(int a, int b) {int res = 0;while (b != 0) {if ((b & 1) != 0) {res = add(res, a);}a <<= 1;b >>>= 1;}return res;}

除法

	public static boolean isNeg(int n) {return n < 0;}public static 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)) {if ((x >> i) >= y) {res |= (1 << i);x = minus(x, y << i);}}return isNeg(a) ^ isNeg(b) ? negNum(res) : res;}public static int divide(int a, int b) {if (b == 0) {throw new RuntimeException("divisor is 0");}if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {return 1;} else if (b == Integer.MIN_VALUE) {return 0;} else if (a == Integer.MIN_VALUE) {int res = div(add(a, 1), b);return add(res, div(minus(a, multi(res, b)), b));} else {return div(a, b);}}