练习

[TOC]

1. 如何找到无序数组第k大元素，如果在O(n)时间内怎么做

利用快排是细想，每次取区间后面的元素P，小于他的放左边，大于P的放右边，这样一趟之后P的大小位置确定，如果P小于K，则说明K在右边，就在右边的区间冲入如此。理想状态每次遍历元素少一半，每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+…+1。即2n-1, 故时间复杂度为O(n) 注：时间复杂度O(n)，不代表就必须是n，还是可以有系数和其他常数，低阶的

2. 如何给100万人按年龄数据排序

年龄这个数，一般都介于0~120之间，比较适合计数排序。有点像桶排序即如果数数据的分布范围不大，加入最大的数为k，申请k个桶，可用数组实现，每个桶中放统一年龄的人，比如所有1岁的人，都放第一个桶中。时间复杂度O(n)

3. 如何给10万手机号排序

手机号码特点位数比较长，单纯的桶排序和计数排序不太适合。基于数据的位数排序。比较对10万手机号排序。先按个位排序，再按十位排序，一次类推。权重大的放后面排。每次遍历都用桶排序，申请0到9的bucket（桶），时间复杂度O(n);经过11次遍历就有序了。总时间为O(k*n),k为待排数据长度，如果k不是很大，比如手机号11，还是能近似认为时间复杂度为O(n)

4. 有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？

用外排序，分治法；堆排序分成100份，每份月100M左右，用快排使得每份时有序的。然后合并，比如先从每份中抽取一个数据，构建小顶堆（考虑到磁盘io，可以每次加载以批到内存），堆顶为最小的，取出来，再从取出来的这个元素来自的那份中再取一个，放入堆中。重复进行。

5.如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次

同如何给100万人按年龄数据排序差不多

6. 假设我们有 1000 万个整型数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？我们希望这个功能不要占用太多的内存空间，最多不要超过 100MB，你会怎么做呢？

利用位图，借助位操作如按位与按位或来实现。如果样本更大的话，还可以借助布隆过滤器实现。如果位图还是不够高效，可以使用roaring bitmap。

7. 单链表反转，链表中环的检测，两个有序的链表合并。

单链表反转，两个有序的链表合并：主要是注意代码实现细节链表中环的检测：方式一：借助快慢指针，快指针步长2，慢指针步长1，有环的话两个指针必然会相遇。方式二：借助类似拓扑排序中的kahn算法，即先找出入度为0的点，从图（链表）中删除，继续找出入度为0的点并删除，最后如果删除的点少于总数则说明有环。

8. 如何实现一个单向链表的逆序输出

先遍历，改变指针方向，把链表反转，即头变尾，尾变头；在遍历输出即可

9. 删除链表倒数第 n 个结点，求链表的中间结点等。

删除链表倒数第 n 个结点：类似逆序输出，先反转链表，再删除。求链表的中间结点：利用快慢指针，快指针步长2，慢指针步长1，快指针到结尾了，满指针正好到中间。

10. 二分查找的四个变体:

元素从小到排列，存在相同的数，查找第一个值等给定值的元素；查找最后一个值等于给定值的元素；查找第一个值大于等于给定值的元素；查找最后一个值小于等于给定值的元素

11. 在爬虫系统中，如何10亿级的url做重复判断，避免爬虫重复爬取。怎么节省内存，还要快速实现

最适合用布隆过滤器来实现了

12. 满 200 元减 50 元，购物车中有 n 个（n>100）想买的商品，从里面选几个，在凑够满减条件的前提下，让选出来的商品价格总和最大程度地接近满减条件（200 元）。

动态规划

13. 0-1背包问题，n 个物品，每个物品的重量不等，并且不可分割。期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？如果每个物品有一定的价值，怎么在不超重的情况求出价值最大的组合？

动态规划

14. 矩阵最短路径的问题，求二阶 `{ {1, 3, 5, 9},{2, 1, 3, 4},{5, 2, 6, 7},{6, 8, 4, 3} }` 左上到右下经过点和最小的路径，即经过的点的值相加最小。

	public int minDistance = Integer.MAX_VALUE;
	/**
	 *    回溯
	 * @param matrix
	 * @param x
	 * @param y
	 * @param distance
	 */
	public void matrixDistance(int[][] matrix, int x, int y, int distance) {
		if (x == matrix.length - 1 && y == matrix[0].length - 1)
			if (distance < minDistance)
				minDistance = distance;
		if (y < matrix[0].length - 1)
			matrixDistance(matrix, x, y+1, distance + matrix[x][y+1]);
		if (x < matrix.length - 1)
			matrixDistance(matrix, x + 1, y, distance + matrix[x+1][y]);
	}

	/**
	 * 动态规划，求二阶左上到右下经过点和最小的路径
	 * @param matrix
	 * @param x
	 * @param y
	 * @param distance
	 */
	public void matrixD(int[][] matrix, int x, int y) {
		int[][] d = new int[x][y];
		int d1 = Integer.MAX_VALUE, d2 = Integer.MAX_VALUE;
		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				if (i == 0 && j == 0) {
					d[0][0] = matrix[0][0];
					continue;
				}
				
				if (j > 0)
					d1 = d[i][j-1];  	//左边点到起点的距离
				
				if (i > 0)
					d2 = d[i-1][j];		//上边点到起点的距离
				
				d[i][j] = matrix[i][j] + Math.min(d1, d2);
			}
		}
		System.out.println(d[x-1][y-1]);
	}

15. 图的中环检测

借助类似拓扑排序中的kahn算法，即先找出入度为0的点，从图（链表）中删除，继续找出入度为0的点并删除，最后如果删除的点少于总数则说明有环。

16. 搜索引擎的输入纠错功能怎么实现。如“faeebook”变为“facebook”，“基你太美”变为“鸡你太美”。

如果只是英文的话，构造trie树，

17. 一个数字序列包含 n 个不同的数字，如何求出这个序列中的最长递增子序列长度？如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，长递增子序列就是 2, 3, 5, 7，所以最长递增子序列的长度是 4。

多阶段决策，回溯最为简单粗暴

	public int maxSeq = 0;
	public void increaseSeq(int[] n, int m, int preMax, int max) {
		if (max > maxSeq) {
			maxSeq = max;
		}
		
		for (int i = m; i < n.length; i++) {
			//第i个不进入序列时
			increaseSeq(n, i+1, preMax ,max);
			//第i个进入序列
			if (n[i] > preMax) {
				increaseSeq(n, i+1, n[i], max+1);
			}
		}
	}

18. 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

(斐波那契)

	//斐波那契数列
	//F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）  如：0、1、1、2、3、5、8、13、21、34、……
	//输入n求F(n)
	public static int fb(int n) {
		if (n < 2) {
			return n;
		}
		return fb(n - 1) + fb(n - 2);
	}