【15】大数据题目等

这篇文章介绍了【15】大数据题目等，分享给大家做个参考，收藏Python资料网收获更多编程知识

目录

 

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

二.找重复的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 -> 1
	public static int flip(int n) {
		return n ^ 1;
	}

	// n是非负数，返回1
	// n是负数，返回0
	public 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为0
		int 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， 一样， 返回0
		int 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 overflow
		System.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);
		}
	}

版权声明：本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！