《WM数据结构笔记》introduction
开胃菜
1. 找到丢失的数字
现在你手上有n-1个数字，这些数字的范围是 [1 , n]，且这n-1个数字中没有重复的数字。由上述条件可知：你手上的数字丢失了一个。请编写一段高效的找到该缺失数字的代码。
自己的思考：刚开始看到这个，我就只能想到 Brute Force，完全没头绪啊。本来想用二分法，但是这里根本不知道丢失的是哪一个，根本无法比较，没法用二分查找。
老师的解答：用二分法，首先可以对数组进行排序（这个我没想到）。也可以放在数组里面，一个一个的遍历。最好的方法就是做 “异或”运算。
A^0 = A;A^A=0;A^B^C = B^A^C=C^A^B; 满足交换律。有了这个，就可以用一个 1-n 的数组 和 丢失数的数组 进行“异或”，结果为 1 的那个位置，就是丢失的数字。那么在拓展一下：如果丢失了两个数字呢？又该如何去做？？
总结:
- 必须要明确的是，这道题想考你什么？比如 是不是有排序 等，你可以和面试官交流，这就是个很好的开始。
- 还有你的思路是什么？不一定非要你能想出最优的方法，但是一定要展现出你对这个问题的看法，思考过程。
2. 找到亚马逊中前K个最经常被搜索的物品
- 这可是亚马逊！那得有多少个商品？
- 老板着急要答案 • 如何能做实时显示呢？
- 比如说每5分钟？
自己的思考：用一个 HashTable 把搜索的物品保存起来，然后计数，之后再排序，取出前 K 个。
老师的解答: 首先这是一个很模糊的题目，你要能够和面试官去交流。你不要一上来就，“我要写一个 for 循环，for…”。第二个，题目定义好之后，你要能给出思路，第一步怎么做，第二步怎么做。第三点，你要能够分析 时间复杂度 和 空间复杂度。第四点，用代码实现。第五点，写一个测试用例测试你的代码。