▐ 中位数（单向二分查找）
- 10MB内存，找到100亿整数的中位数
- 内存够：内存够还慌什么啊，直接把100亿个全部排序了，你用冒泡都可以...然后找到中间那个就可以了。但是你以为面试官会给你内存？？
- 内存不够：题目说是整数，我们认为是带符号的int,所以4字节，占32位。
假设100亿个数字保存在一个大文件中，依次读一部分文件到内存(不超过内存的限制)，将每个数字用二进制表示，比较二进制的最高位(第32位，符号位，0是正，1是负)，如果数字的最高位为0，则将这个数字写入file_0文件中；如果最高位为1，则将该数字写入file_1文件中。
从而将100亿个数字分成了两个文件，假设file_0文件中有60亿个数字，file_1文件中有40亿个数字。那么中位数就在file_0文件中，并且是file_0文件中所有数字排序之后的第10亿个数字。（file_1中的数都是负数，file_0中的数都是正数，也即这里一共只有40亿个负数，那么排序之后的第50亿个数一定位于file_0中）
现在，我们只需要处理file_0文件了（不需要再考虑file_1文件）。对于file_0文件，同样采取上面的措施处理：将file_0文件依次读一部分到内存(不超内存限制)，将每个数字用二进制表示，比较二进制的次高位（第31位），如果数字的次高位为0，写入file_0_0文件中；如果次高位为1，写入file_0_1文件中。
现假设file_0_0文件中有30亿个数字，file_0_1中也有30亿个数字，则中位数就是：file_0_0文件中的数字从小到大排序之后的第10亿个数字。
抛弃file_0_1文件，继续对file_0_0文件根据次次高位(第30位)划分，假设此次划分的两个文件为：file_0_0_0中有5亿个数字，file_0_0_1中有25亿个数字，那么中位数就是file_0_0_1文件中的所有数字排序之后的 第5亿个数。
按照上述思路，直到划分的文件可直接加载进内存时，就可以直接对数字进行快速排序，找出中位数了。
▐ 短域名系统（缓存）
- 设计短域名系统，将长URL转化成短的URL.
- 利用放号器，初始值为0，对于每一个短链接生成请求，都递增放号器的值，再将此值转换为62进制（a-zA-Z0-9），比如第一次请求时放号器的值为0，对应62进制为a，第二次请求时放号器的值为1，对应62进制为b，第10001次请求时放号器的值为10000，对应62进制为sBc。
- 将短链接服务器域名与放号器的62进制值进行字符串连接，即为短链接的URL，比如：t.cn/sBc。
- 重定向过程：生成短链接之后，需要存储短链接到长链接的映射关系，即sBc ->URL，浏览器访问短链接服务器时，根据URL Path取到原始的链接，然后进行302重定向。映射关系可使用K-V存储，比如Redis或Memcache。
▐ 海量评论入库（消息队列）
假设有这么一个场景，有一条新闻，新闻的评论量可能很大，如何设计评论的读和写
前端页面直接给用户展示、通过消息队列异步方式入库
读可以进行读写分离、同时热点评论定时加载到缓存
▐ 在线/并发用户数（Redis）
- 显示网站的用户在线数的解决思路
- 维护在线用户表
- 使用Redis统计
- 显示网站并发用户数
- 每当用户访问服务时，把该用户的ID写入ZSORT队列，权重为当前时间；
- 根据权重(即时间)计算一分钟内该机构的用户数Zrange；
- 删掉一分钟以上过期的用户Zrem；
▐ 热门字符串（前缀树）
假设目前有1000w个记录（这些查询串的重复度比较高，虽然总数是1000w，但如果除去重复后，则不超过300w个）。请统计最热门的10个查询串，要求使用的内存不能超过1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）
- HashMap法
虽然字符串总数比较多，但去重后不超过300w，因此，可以考虑把所有字符串及出现次数保存在一个HashMap中，所占用的空间为300w*(255+4)≈777M（其中，4 表示整数占用的4个字节）。由此可见，1G的内存空间完全够用。
- 思路如下
首先，遍历字符串，若不在map中，直接存入map，value记为1；若在map中，则把对应的value加1，这一步时间复杂度O(N)。
接着遍历map，构建一个10个元素的小顶堆，若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小顶堆。
遍历结束后，堆中10个字符串就是出现次数最多的字符串。这一步时间复杂度O(Nlog10)。
- 前缀树法
当这些字符串有大量相同前缀时，可以考虑使用前缀树来统计字符串出现的次数，树的结点保存字符串出现次数，0表示没有出现。
- 思路如下
在遍历字符串时，在前缀树中查找，如果找到，则把结点中保存的字符串次数加1，否则为这个字符串构建新结点，构建完成后把叶子结点中字符串的出现次数置为1。
最后依然使用小顶堆来对字符串的出现次数进行排序。
▐ 红包算法
线性切割法，一个区间切N-1刀。越早越多
二倍均值法，【0~剩余金额 / 剩余人数*2】中随机，相对均匀
▐ 手写快排
public class QuickSort { public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } /* 常规快排 */ public static void quickSort1(int[] arr, int L , int R) { if (L > R) return; int M = partition(arr, L, R); quickSort1(arr, L, M - 1); quickSort1(arr, M + 1, R); } public static int partition(int[] arr, int L, int R) { if (L > R) return -1; if (L == R) return L; int lessEqual = L - 1; int index = L; while (index < R) { if (arr[index] <= arr[R]) swap(arr, index, ++lessEqual); index++; } swap(arr, ++lessEqual, R); return lessEqual; } /* 荷兰国旗 */ public static void quickSort2(int[] arr, int L, int R) { if (L > R) return; int[] equalArea = netherlandsFlag(arr, L, R); quickSort2(arr, L, equalArea[0] - 1); quickSort2(arr, equalArea[1] + 1, R); } public static int[] netherlandsFlag(int[] arr, int L, int R) { if (L > R) return new int[] { -1, -1 }; if (L == R) return new int[] { L, R }; int less = L - 1; int more = R; int index = L; while (index < more) { if (arr[index] == arr[R]) { index++; } else if (arr[index] < arr[R]) { swap(arr, index++, ++less); } else { swap(arr, index, --more); } } swap(arr, more, R); return new int[] { less + 1, more }; } // for test public static void main(String[] args) { int testTime = 1; int maxSize = 10000000; int maxValue = 100000; boolean succeed = true; long T1=0,T2=0; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); int[] arr3 = copyArray(arr1); // int[] arr1 = {9,8,7,6,5,4,3,2,1}; long t1 = System.currentTimeMillis(); quickSort1(arr1,0,arr1.length-1); long t2 = System.currentTimeMillis(); quickSort2(arr2,0,arr2.length-1); long t3 = System.currentTimeMillis(); T1 += (t2-t1); T2 += (t3-t2); if (!isEqual(arr1, arr2) || !isEqual(arr2, arr3)) { succeed = false; break; } } System.out.println(T1+" "+T2); // System.out.println(succeed ? "Nice!" : "Oops!"); } private static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } private static int[] copyArray(int[] arr) { if (arr == null) return null; int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } private static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) return false; if (arr1 == null && arr2 == null) return true; if (arr1.length != arr2.length) return false; for (int i = 0; i < arr1.length; i++) if (arr1[i] != arr2[i]) return false; return true; } private static void printArray(int[] arr) { if (arr == null) return; for (int i = 0; i < arr.length; i++) System.out.print(arr[i] + " "); System.out.println(); } }
