花了一晚上看完了《编程之美--微软技术面试心得》,里面要么是些智力题,要么是些稀里古怪的问题,都值得我们思考,题目描述也很有意思。解答也很精彩,一般都会给出好几个方法,极力荐之!!
还有个感觉就是搞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。
编程之美—读后感
对“编程之美—读后感”的回应
《编程之美》热门书评
-
迟来的书评和感想──给喜爱编程的朋友
181有用 3无用 Milo 2010-02-24
这本书我读了两遍,分別是两个印次。读第一遍是这书刚出版的时候买的第一版,读第二遍是因为最近认识了本书作者及编辑,我说以前看到本书的一些小错处,出版社就寄了第7次印刷本给我。在新年前花了一个星期把书尽量仔细地看了一遍,发现这印次仍有一些小问题及程序的bugs,已连同其他意见回馈给作者。 我其实不太喜欢...
-
我所了解的微软面试
81有用 0无用 蓬山远 2012-11-11
2014 05 22本文是一年半以前写的了。这一年半之间微软发生了很大的变化,我自己也发生了很大的变化,时过境迁,世殊事异。大家就看个乐子好了,不宜再当作经验去套用了。------------------------------------------------------------------...
-
数据结构和算法是程序的根本——为什么?!
49有用 0无用 bluedavy 2009-07-10
转自博客。应该是差不多两个月前收到了这本书,一直到最近才抽出时间来看了下,这本书的开篇的第一题现在基本已经成了经典中的经典了,相信很多人都因为这个控制CPU使用率的题从而买了这本书的,在我自己看过这本书后我同时相信买了这本书的人应该会觉得非常的值得,要写出合理实现需求、高性能以及大数据量的程序,数据...
-
一本未看完的书 一段未走完的旅途
21有用 3无用 Dear Al 2010-03-29
答应了Lisa写这篇书评 买这本书是大四的时候了 大学接近尾声 作为一名计算机软件方向的本科毕业生 我们学校竟未开过一门类似于算法导论之类的课程 哦 对了 是有一门类似的数据结构 它和Linux是我大学阶段最喜欢的专业课了 不过那些内容 唉 那时候很喜欢在CSDN上瞎晃 于是便迷恋上了高纳德 接受了...
-
享受用程序语言思维的乐趣
20有用 0无用 gaomiao 2009-07-17
闲暇时喜欢翻书,但也许是习惯了屏幕前飞快的阅读速度,如今看书已不像原先啃书那般细致。阅读时往往对引出道理的故事很感兴趣,而到了讲道理的细节,便一扫而过。然而最近在读的《编程之美》一书,却是无论如何也无法像读其他书籍那样浮光掠影般翻看,而是字斟句酌,生怕遗漏了半点细节。如果说在看《算法导论》这样的经典...