编程之美—读后感

花了一晚上看完了《编程之美--微软技术面试心得》，里面要么是些智力题，要么是些稀里古怪的问题，都值得我们思考，题目描述也很有意思。解答也很精彩，一般都会给出好几个方法，极力荐之！！

还有个感觉就是搞acm的在这方面绝对是有优势的，只要能有面试机会，像里面的面试题目基本都能秒杀的，里面的有些问题就是acm中的水题，像nim游戏（博弈），连连看算法（搜索），饮料供货（dp），求二叉树中节点的最大距离（dp），求前k大的数（堆排，归并排序）；这些在regional中是绝对的水题，基本是用来稳定军心的。所以请搞acm的战友们不要轻易放弃，虽然不一定要拿牌，但它给我们带来的思维的升华绝对是无价的。

还有我发现里面有一道题目其实《寻找发帖“水王”》是有更快的解法的，题目描述是这样的：

Tango是微软亚洲研究院的一个实验项目。研究院的员工和实习生都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？

书中给出的标准解法是:每次删除两个不同的id，在剩下的id中水王仍然是占一半以上的，缩小问题范围，直到最后只剩下水王的id，o(n)。

而我感觉可以从另一个角度思考：

1.水王发帖的数量是很多的，每次找出一个id很可能就是他的。

2.然后可以随机取出k个id，统计id出现个数，出现次数最多的那个id就是水王的id。

3.只要k取的合适，既能保证正确性，又能保证算法有很好的速度。复杂度O(k),k<=n,k一般不会很大，可以通过计算来确定一个最优的k，不过本菜概率学的不好，就不算了，一般k取个1000的话，正确性肯定很高了。

还有个o(n)的算法：

对id设计个hash函数，初始化a数组为0，每次某个id出现一次，a[hash(id)]++;全部遍历一下所有id，a[hash(id)]最大的那个id就是水王的id。