大数据开发场景题【大厂面试常问】
推荐阅读文章列表：大数据开发面试笔记V4.0 || 面试聊数仓第一季 || 小白大数据学习路线
很多大厂的面试官都会问这种大数据量下如何计算的问题，所以大家提前准备好答题套路，吊打面试官
1亿个整数中找出最大的10000个数
- 首先想到的就是全局排序，那么需要判断内存是否能够装的下？1*10^9*4B = 4GB，需要4G的内存，如果机器的内存小于4G，显然是不行的
- 第二种方法就是分治法，将这1亿个数通过hash算法，分为1000份，每份100万个数据，找到每份数据中最大的10000个数，最后在100*10000中找出最大的10000个数，最大占用内存为 1000000*4B = 4MB。从100万个数中找到最大的10000个数的方法是快速排序的方法，但是我们没有必要将这100万个数排序，只用找到前10000个数，大致的思路是：将第一个数字设置为基准元素，然后将这100万个数分为两堆，如果大于基准的堆的个数大于10000个，那么继续对该堆进行一次快速排序，如果此时大的堆的个数n小于10000个，那么在小的堆中找到前10000-n的数字。
- 【重点】第三种方法就是小顶堆，首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度是O(m)，然后遍历后续的数字，并与堆顶元素（最小）进行比较，如果比堆顶元素小，则继续遍历后面的数字即可；如果比堆顶元素大，则替换堆顶元素并重新调整堆为最小堆。直至遍历完所有的数字，最后输出当前堆的所有数字就可以了。整体的时间复杂度是O(mn)
在2.5亿个整数中找出不重复的整数
- 采用2bit的bitmap（00表示不存在，01表示出现1次，10表示出现多次，11表示无意义），共需内存 2^32*2bit=1GB内存，可以接受，然后扫描这2.5亿个整数，查看bitmap中相对应的位，如果是00变01,01变10,10保持不变，扫描完后，查看bitmap，把对应为是01的整数输出。
大整数相乘
- 分治法【递归】
- 当我们输入两个大整数num1,num2,长度分别为n，m，计算机无法直接计算其结果，采用分而治之的思想，我们可以分别将两个数均分为四个部分，记作A，B，C，D，其中： A为num1的前n/2, B为num1的后n/2, C为num2的前m/2D为num2的后m/2
- num1 * num2 = (A * 10^(n/2) + B) * (C * 10^(m/2) + D)= AC * 10^(n/2+m/2) + AD * 10^(n/2) + BC * 10^(m/2) + BD
- 此时将一个大整数的乘法分为了四个相对较小的整数相乘，此时，我们就可以采用递推的思想，再将每个相乘的数进行拆分相乘再相加，当递推到相乘的值较小时，我们可以求出相应的值然后对其进行相加，将结果依次返回，最终得到大整数相乘的结果。
- 乘法变加法【遍历】
- 同字符串相乘
