Twitter
Facebook
Flickr
RSSI like to look at CS 170 as one exponentially large graph search problem. Now, assuming that we began at the same start node of basic 61b algorithm The most important secret to this course is the practice of writing In that vein, approach your homework as if it were a baby lion. It is If one of your many explorations of this solution space When you have reached the coveted solution you will realize the May your base cases always be defined, http://groups.google.com/group/ucb.class.cs170/browse_thread/thread/1f2cc705af705560?pli=1
We have a plethora of information given to us to guide our way (as a
search heuristic) to the goal node, which is achieving algorithmic zen. In
the end, we should eat, sleep, and breathe big O notation. We should
cringe at exponentials of any form. Our hearts should skip a beat when we
read the words "constant time", yet remain brave when staring down an
NP-hard problem. We should be so lucky to have committed to memory all
algorithms we've learned, yet never assume that our machines can commit
much to memory at all. Once you have reached this land, you are in the
enlightened world of efficiency, problem solving, and babes. Well, maybe
not the last part, but you'll still be really, really cool in my books.
knowledge, we want to find this path to our shangri-la in as short a time
as possible. If not solely because we are excited to get there, then at
least because you'll do well on tests if you achieve enlightenment
faster. Given these requirements, what better method than to call upon
the prophet Dijkstra who has graced us with his algorithm? Hence, we
must follow the path of Dijkstra through this land of unintelligible
mathematics and weird newsgroup posts at 3 am on a Saturday. Now, I
cannot give you his specific commandments, as any man delivering
commandments has to have a sweet beard. I do not have a
sweet beard, though not for lack of trying, and thus I can only provide
my worldly wisdom as to the way of Dijkstra.
and analyzing algorithms. As any good kung-fu movie shows us, you need
to have a painful training montage if you are to achieve your goal.
Though, since we are only beginners, we must learn proof techniques from
the masters Rao and Papadimitrou. In the chapter, the problem at hand is
always presented first, and then the algorithm is given. You never
get to experience the frustration and thought put into discovering what
is presented. As an example, have you ever seen master Sinclair smile?
No, for he is tortured by the demons he must wrestle. To really get a
grasp of this learning process, try to write your own algorithm before it
is presented to you in the book. Yes, your answer is nowhere near as good
Papadimitrou's, but you can now compare the approach of an apprentice
to that of a master. To know where you are headed, you must know where
you came from and where you are.
relatively small and beautiful creature, yet it grows to be a dangerous
beast that will eat your entrails if not tamed. Come prepared with reams
of paper and sit in your favorite library for at least 3 hours attacking
the problems by yourself. During this time, you must try every possible
sneaky way of snatching the solutions from the jaws of ignorance. Do not
rush, do not cry, do not leave your seat, just write. If the answer does
not come to you immediately, write a slow inefficient answer. You can
always recycle the paper later. Thomas Edison was famous claiming "I
have not failed. I've just found 10,000 ways that don't work." He
was an amateur. You should have at least O(100!) ways that don't work
efficiently.
does not grant you the solution master Rao seeks, then you must go to
the hours of the office. Though our professors and GSI's do their best
to schedule them at the same time as our classes, this is only done to
to ward off the freeloading answer seekers who are not pure in their
persuit of algorithmic zen. Fret not, for they will meet a negative
cycle in the graph of life from which they will never escape. It is
here that you may ask for guidance AND ONLY GUIDANCE to the one true
solution.
reward of algorithmic glory. Do not worry if your perspiration
increases along with your heart rate, this is normal. You will quake
with excitement as your pen graciously rounds the curves of a paren,
and stabs sharply with the joint of a sigma. It is this feeling that
keeps us going forward. For you not only know the answer, but you
know the dangerous turns to avoid, having taken them yourself.
May your code always elude perplexity,
May your run times always be confined
to the lowest asymptotic complexity.
Someone Writes An Algorithm Zen
pointer 'dirty trick'
ANSI C guarantees that it is safe to cast a pointer to a structure to a pointer to the type of that structure's first element.
example:
struct bst_node {
struct bst_node *link[2];
void *data;
};
struct bst_tree {
struct bst_node *root;
int count;
};
applying the rule:
we know that root is a pointer to bst_node, it's type: bst_node *,
the first element of bst_node is struct bst_node *,too!
so it is safe to cast from struct bst_node * to struct bst_node **,
the latter is a pointer to struct bst_node *,
So if struct bst_tree *t;
then link[0] == (struct bst_node *)&t->root;
reference:http://www.red-bean.com/guile/guile/new/msg02536.html
topological sort taocp 2.2.3,vol 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int indegree[9];
vector<vector<int> > vv(9);
typedef vector<int>::iterator it;
queue<int> q;
bool flag[9];
void init() {
memset(flag, false, sizeof(bool)*9);
memset(indegree, 0, 9*sizeof(int));
vv[0].push_back(2);++indegree[2];
vv[1].push_back(7);++indegree[7];
vv[2].push_back(6);++indegree[6];
vv[3].push_back(5);++indegree[5];
vv[4].push_back(7);++indegree[7];
vv[6].push_back(3);++indegree[3];
vv[6].push_back(4);++indegree[4];
vv[7].push_back(5);++indegree[5];
vv[8].push_back(1);++indegree[1];
vv[8].push_back(4);++indegree[4];
}
void tsort() {
for (int i = 0; i<=8; i++)
if (indegree[i] == 0 && !flag[i]) {
q.push(i);
while(!q.empty()) {
int number = q.front();
cout << number << ' ';
flag[number]= true;
q.pop();
for ( it ii = vv[number].begin(); ii != vv[number].end(); ++ii) {
--indegree[*ii];
if ( indegree[*ii] == 0)
q.push(*ii);
}
}
}
}
int main(){
init();
tsort();
return 0;
}
joke from taocp
Volume 1, p200:
百度一面就被fault了
感谢Nvidia，Tencent，Baidu给机会我面试，是时候总结一下自己的面试经历了。笔试了很多公司，大大小小，像阿里巴巴，微软，朗讯，甲骨文，深信服（舍友就是签了这间的），华为等，他们都因为自己幼稚，水平做题水平低下，没有就会面试。总体来说，每次面试自己对缺乏主动询问自己所申请的职位的相关信息，没有把自己的意愿所表示出来，Nvidia是电话面试，面试官叫阿Ted，感觉他很不错，所问的问题都是很简单的，但是自己感觉对硬件不是很感兴趣，所以明知道他问些简单的数字电路问题，也没有去预先准备，这个不能怪谁，因为我知道自己更喜欢往软件或者互联网方向发展。Tencent的一面感觉自己表现不错，面试官很nice，没有问他的名字，太可惜了，毕竟他是第一个现场面试自己的人。但是二面挂了，理由很简单，他们想招的是网管，而我却说出来自己想当个程序员的欲望，后来经理也特意暗示了我的下场，而且还问了些服务器坏掉的解决方案，明知道我没有哪个方面的东西，还是往那边的问，我也没有办法了，临走时，他就主动跟我说“感谢你参加腾讯的这次招聘活动”，唯有泪奔。昨天刚刚面完baidu，这是第一次正式通过笔试，要知道我可以准备了一个多星期的，在那段日子里，我根本就没有再海投，专心一志，看算法导论，看programming peals，看programming interviews exposed，做n多的面试笔试题目，因为华为也同时过来，所以自己很好的准备一番，但不是知道为何，baidu的笔试过了，而华为的没有通过，问谁都知道baidu的题目更加难，而华为考的是基础题目，这个也很遗憾。不过据说华为要群殴，可惜没有机会参加。baidu的面试官人长得很踏实，我进来的是个昨天刚面完华为的牛逼研究生，他可是没有理会百度当天的面试请求，参加华为的面试的，不过据说晚上百度还是邀请他去面试了，够牛的。因为我的简历写着学习进步奖，所以他问了我的成绩，这个意思人人都知道的，我也没有说什么，只能说自己中等生，但是最好一次有点进步所以得到进步奖了，接着他叫我shell小程序，内容就不说了，很简单的，但是我说自己已经忘记语法了，这个和简历上的东西有点不符合把，他说好了，然后叫我做智力题，我心里感觉很不爽，因为知道飞来同学在面试腾讯的时候被问一个智力题而挂了，我还说自己很少做这类东西的，说完题目，他就去上网了，叫我好好思考，我没有法，只能好好想了，最后还真做出了，回来查网上的解答也是同样的做法，据说是ms的题目，这时他说这次的技术方面的东西就结束了，这之前他还叫我介绍了自己的小小项目，这个好像是例牌来的，没有啥好说，然后开始了提问环节，我估计自己就是在这里失败的，最后他问我还有没有别的问题，还很该死的说外面很漂亮，我想出去走走，我也不知道自己为何会说出这种话的，可能自己太紧张了，这时我想他一定是心里说，那么你以后就别再想有机会进来了，这次打击很大，面对自己喜欢的公司，而无力挽回，实在是很伤心。
笔试概率题目
题目
有两个数组A[n], B[m], n
A中的n个元素互不相同，对B中的每一个元素，
都从A中随机取一个元素放入其中，
求A中的n个元素在B中都出现的概率
解答
从古典概率的角度来考虑，相当于从集合A（a1,a2,....,an)中选择元素放到筐子B1,B2,...,Bm中去，求在这m个框子中包含了全部A中元素的概率。
首先，从A中选择元素放置到框子中的方法有n^m中，是没有问题的，
其次，需要计算这些放置方法中把A中所有元素都取了一遍的方法个数。楼下这种方法给出的是n!*n^(m-n),我可以看成是取了前n个筐子莱放置A中n个元素，那么有n!种方式，然后后面的m-n个筐子可以随便放，有n^(m-n)种方式，所以是n!*n^(n-m)中。但是这种方式减少了可能的次数。考虑将m个不同的元素分成n份，这个数目记为S(m,n), 那么我们需要计算的这个数应该是n!*S(m,n)
那么概率就是 n!*S(m,n)/n^m
因为是有标号的，所以Stirling数前面乘一个n!嘛。
ps:
stirling数
将n个不同颜色的球放人k个无标号的盒子中( n>=k>=1，且盒子不允许为空)的方案数就是stirling数.(即含 n 个元素的集合划分
为 k 个集合的情况数)
递推公式:
S(n,k) = 0 (k > n)
S(n,1) = 1 (k = 1)
s(n,k)=1 (n=k)
S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)
在北京大学2008年开学典礼上的发言
| 各位同学、各位领导： 大家上午好！（掌声） 非常高兴许校长给我这么崇高的荣誉，谈一谈我在北大的体会。（掌声） 可以说，北大是改变了我一生的地方，是提升了我自己的地方，使我从一个农村孩子最后走向了世界的地方。毫不夸张地说，没有北大，肯定就没有我的今天。北大给我留下了一连串美好的回忆，大概也留下了一连串的痛苦。正是在美好和痛苦中间，在挫折、挣扎和进步中间，最后找到了自我，开始为自己、为家庭、为社会能做一点事情。 学生生活是非常美好的，有很多美好的回忆。我还记得我们班有一个男生，每天都在女生的宿舍楼下拉小提琴，（笑声）希望能够引起女生的注意，结果后来被女生扔了水瓶子。我还记得我自己为了吸引女生的注意，每到寒假和暑假都帮着女生扛包。（笑声、掌声）后来我发现那个女生有男朋友，（笑声）我就问她为什么还要让我扛包，她说为了让男朋友休息一下（笑声、掌声）。我也记得刚进北大的时候我不会讲普通话，全班同学第一次开班会的时候互相介绍，我站起来自我介绍了一番，结果我们的班长站起来跟我说：“俞敏洪你能不能不讲日语？”（笑声）我后来用了整整一年时间，拿着收音机在北大的树林中模仿广播台的播音，但是到今天普通话还依然讲得不好。 人的进步可能是一辈子的事情。在北大是我们生活的一个开始，而不是结束。有很多事情特别让人感动。比如说，我们很有幸见过朱光潜教授。在他最后的日子里，是我们班的同学每天轮流推着轮椅在北大里陪他一起散步。（掌声）每当我推着轮椅的时候，我心中就充满了对朱光潜教授的崇拜，一种神圣感油然而生。所以，我在大学看书最多的领域是美学。因为他写了一本《西方美学史》，是我进大学以后读的第二本书。 为什么是第二本呢？因为第一本是这样来的，我进北大以后走进宿舍，我有个同学已经在宿舍。那个同学躺在床上看一本书，叫做《第三帝国的兴亡》。所以我就问了他一句话，我说：“在大学还要读这种书吗？”他把书从眼睛上拿开，看了我一眼，没理我，继续读他的书。这一眼一直留在我心中。我知道进了北大不仅仅是来学专业的，要读大量大量的书。你才能够有资格把自己叫做北大的学生。（掌声）所以我在北大读的第一本书就是《第三帝国的兴亡》，而且读了三遍。后来我就去找这个同学，我说：“咱们聊聊《第三帝国的兴亡》”，他说：“我已经忘了。”（笑声） 我也记得我的导师李赋宁教授，原来是北大英语系的主任，他给我们上《新概念英语》第四册的时候，每次都把板书写得非常的完整，非常的美丽。永远都是从黑板的左上角写起，等到下课铃响起的时候，刚好写到右下角结束。（掌声）我还记得我的英国文学史的老师罗经国教授，我在北大最后一年由于心情不好，导致考试不及格。我找到罗教授说：“这门课如果我不及格就毕不了业。”，罗教授说：“我可以给你一个及格的分数，但是请你记住了，未来你一定要做出值得我给你分数的事业。”（掌声）所以，北大老师的宽容、学识、奔放、自由，让我们真正能够成为北大的学生，真正能够得到北大的精神。 当我听说许智宏校长对学生唱《隐形的翅膀》的时候，我打开视频，感动得热泪盈眶。因为我觉得北大的校长就应该是这样的。（掌声） 我记得自己在北大的时候有很多的苦闷。一是普通话不好，第二英语水平一塌糊涂。尽管我高考经过三年的努力考到了北大——因为我落榜了两次，最后一次很意外地考进了北大。我从来没有想过北大是我能够上学的地方，她是我心中一块圣地，觉得永远够不着。但是那一年，第三年考试时我的高考分数超过了北大录取分数线七分，我终于下定决心咬牙切齿填了“北京大学”四个字。我知道一定会有很多人比我分数高，我认为自己是不会被录取的。没想到北大的招生老师非常富有眼光，料到了三十年后我的今天。（掌声）但是实际上我的英语水平很差，在农村既不会听也不会说，只会背语法和单词。我们班分班的时候，五十个同学分成三个班，因为我的英语考试分数不错，就被分到了A 我也记得自己进北大以前连《红楼梦》都没有读过，所以看到同学们一本一本书在读，我拼命地追赶。结果我在大学差不多读了八百多本书，用了五年时间（掌声）。但是依然没有赶超上我那些同学。我记得我的班长王强是一个书癖，现在他也在新东方，是新东方教育研究院的院长。他每次买书我就跟着他去，当时北大给我们每个月发二十多块钱生活费，王强有个癖好就是把生活费一分为二，一半用来买书，一半用来买饭菜票。买书的钱绝不动用来买饭票。如果他没有饭菜票了就到处借，借不到就到处偷。（笑声）后来我发现他这个习惯很好，我也把我的生活费一份为二，一半用来买书，一半用来买饭菜票，饭票吃完了我就偷他的。（笑声掌声） 毫不夸张地说，我们班的同学当时在北大，真是属于读书最多的班之一。而且我们班当时非常地活跃，光诗人就出了好几个。后来挺有名的一个诗人叫西川，真名叫刘军，就是我们班的。（掌声）我还记得我们班开风气之先，当时是北大的优秀集体，但是有一个晚上大家玩得高兴了，结果跳起了贴面舞，第二个礼拜被教育部通报批评了。那个时候跳舞是必须跳得很正规的，男女生稍微靠近一点就认为违反风纪。所以你们现在比我们当初要更加幸福一点。不光可以跳舞，而且可以手拉手地在校园里面走，我们如果当时男女生手拉手在校园里面走，一定会被扔到未名湖里，所以一般都是晚上十二点以后再在校园里面走。（笑声掌声） 我也记得我们班五十个同学，刚好是二十五个男生二十五个女生，我听到这个比例以后当时就非常的兴奋（笑声），我觉得大家就应该是一个配一个。没想到女生们都看上了那些外表英俊潇洒、风流倜傥的男生。像我这样外表不怎么样，内心充满丰富感情、未来有巨大发展潜力的，女生一般都看不上。（笑声掌声） 我记得我奋斗了整整两年希望能在成绩上赶上我的同学，但是就像刚才吕植老师说的，你尽管在中学高考可能考得很好，是第一名，但是北大精英人才太多了，你的前后左右可能都是智商极高的同学，也是各个省的状元或者说第二名。所以，在北大追赶同学是一个非常艰苦的过程，尽管我每天几乎都要比别的同学多学一两个小时，但是到了大学二年级结束的时候我的成绩依然排在班内最后几名。非常勤奋又非常郁闷，也没有女生来爱我安慰我。（笑声）这导致的结果是，我在大学三年级的时候得了一场重病，这个病叫做传染性侵润肺结核。当时我就晕了，因为当时我正在读《红楼梦》，正好读到林黛玉因为肺结核吐血而亡的那一章，（笑声）我还以为我的生命从此结束，后来北大医院的医生告诉我现在这种病能够治好，但是需要在医院里住一年。我在医院里住了一年，苦闷了一年，读了很多书，也写了六百多首诗歌，可惜一首诗歌都没有出版过。从此以后我就跟写诗结上了缘，但是我这个人有丰富的情感，但是没有优美的文笔，所以终于没有成为诗人。后来我感到非常的庆幸，因为我发现真正成为诗人的人后来都出事了。我们跟当时还不太出名的诗人海子在一起写过诗。后来他写过一首优美的诗歌，叫做《面朝大海，春暖花开》，我们每一个同学大概都能背。后来当我听说他卧轨自杀的时候，嚎啕大哭了整整一天。从此以后，我放下笔，再也不写诗了。（掌声） 记得我在北大的时候，到大学四年级毕业时，我的成绩依然排在全班最后几名。但是，当时我已经有了一个良好的心态。我知道我在聪明上比不过我的同学，但是我有一种能力，就是持续不断的努力。所以在我们班的毕业典礼上我说了这么一段话，到现在我的同学还能记得，我说：“大家都获得了优异的成绩，我是我们班的落后同学。但是我想让同学们放心，我决不放弃。你们五年干成的事情我干十年，你们十年干成的我干二十年，你们二十年干成的我干四十年”。（ 掌声）我对他们说：“如果实在不行，我会保持心情愉快、身体健康，到八十岁以后把你们送走了我再走。”（笑声掌声） 有一个故事说，能够到达金字塔顶端的只有两种动物，一是雄鹰，靠自己的天赋和翅膀飞了上去。我们这儿有很多雄鹰式的人物，很多同学学习不需要太努力就能达到高峰。很多同学后来可能很轻松地就能在北大毕业以后进入哈佛、耶鲁、牛津、剑桥这样的名牌大学继续深造。有很多同学身上充满了天赋，不需要学习就有这样的才能，比如说我刚才提到的我的班长王强，他的模仿能力就是超群的，到任何一个地方，听任何一句话，听一遍模仿出来的绝对不会两样。所以他在北大广播站当播音员当了整整四年。我每天听着他的声音，心头咬牙切齿充满仇恨。（笑声）所以，有天赋的人就像雄鹰。但是，大家也都知道，有另外一种动物，也到了金字塔的顶端。那就是蜗牛。蜗牛肯定只能是爬上去。从低下爬到上面可能要一个月、两个月，甚至一年、两年。在金字塔顶端，人们确实找到了蜗牛的痕迹。我相信蜗牛绝对不会一帆风顺地爬上去，一定会掉下来、再爬、掉下来、再爬。但是，同学们所要知道的是，蜗牛只要爬到金字塔顶端，它眼中所看到的世界，它收获的成就，跟雄鹰是一模一样的。（掌声）所以，也许我们在座的同学有的是雄鹰，有的是蜗牛。我在北大的时候，包括到今天为止，我一直认为我是一只蜗牛。但是我一直在爬，也许还没有爬到金字塔的顶端。但是只要你在爬，就足以给自己留下令生命感动的日子。（掌声） 我常常跟同学们说，如果我们的生命不为自己留下一些让自己热泪盈眶的日子，你的生命就是白过的。我们很多同学凭着优异的成绩进入了北大，但是北大绝不是你们学习的终点，而是你们生命的起点。在一岁到十八岁的岁月中间，你听老师的话、听父母的话，现在你真正开始了自己的独立生活。我们必须为自己创造一些让自己感动的日子，你才能够感动别人。我们这儿有富裕家庭来的，也有贫困家庭来的，我们生命的起点由不得你选择出生在富裕家庭还是贫困家庭，如果你生在贫困家庭，你不能说老爸给我收回去，我不想在这里待着。但是我们生命的终点是由我们自己选择的。我们所有在座的同学过去都走得很好，已经在十八岁的年龄走到了很多中国孩子的前面去，因为北大是中国的骄傲，也可以说是世界的骄傲。但是，到北大并不意味着你从此大功告成，并不意味着你未来的路也能走好，后面的五十年、六十年，甚至一百年你该怎么走，成为了每一个同学都要思考的问题。就本人而言，我觉得只要有两样东西在心中，我们就能成就自己的人生。 第一样叫做理想。我从小就有一种感觉，希望穿越地平线走向远方，我把它叫做“穿越地平线的渴望”。也正是因为这种强烈的渴望，使我有勇气不断地高考。当然，我生命中也有榜样。比如我有一个邻居，非常的有名，是我终生的榜样，他的名字叫徐霞客。当然，是五百年前的邻居。但是他确实是我的邻居，江苏江阴的，我也是江苏江阴的。因为崇拜徐霞客，直接导致我在高考的时候地理成绩考了九十七分。（掌声）也是徐霞客给我带来了穿越地平线的这种感觉，所以我也下定决心，如果徐霞客走遍了中国，我就要走遍世界。而我现在正在实现自己这一梦想。所以，只要你心中有理想，有志向，同学们，你终将走向成功。你所要做到的就是在这个过程要有艰苦奋斗、忍受挫折和失败的能力，要不断地把自己的心胸扩大，才能够把事情做得更好。 第二样东西叫良心。什么叫良心呢？就是要做好事，要做对得起自己对得起别人的事情，要有和别人分享的姿态，要有愿意为别人服务的精神。有良心的人会从你具体的生活中间做的事情体现出来，而且你所做的事情一定对你未来的生命产生影响。我来讲两个小故事，讲完我就结束我的讲话，已经占用了很长的时间。 第一个小故事。有一个企业家和我讲起他大学时候的一个故事，他们班有一个同学，家庭比较富有，每个礼拜都会带六个苹果到学校来。宿舍里的同学以为是一人一个，结果他是自己一天吃一个。尽管苹果是他的，不给你也不能抢，但是从此同学留下一个印象，就是这个孩子太自私。后来这个企业家做成功了事情，而那个吃苹果的同学还没有取得成功，就希望加入到这个企业家的队伍里来。但后来大家一商量，说不能让他加盟，原因很简单，因为在大学的时候他从来没有体现过分享精神。所以，对同学们来说在大学时代的第一个要点，你得跟同学们分享你所拥有的东西，感情、思想、财富，哪怕是一个苹果也可以分成六瓣大家一起吃。（掌声）因为你要知道，这样做你将来能得到更多，你的付出永远不会是白白付出的。 我再来讲一下我自己的故事。在北大当学生的时候，我一直比较具备为同学服务的精神。我这个人成绩一直不怎么样，但我从小就热爱劳动，我希望通过勤奋的劳动来引起老师和同学的的注意，所以我从小学一年级就一直打扫教室卫生。到了北大以后我养成了一个良好的习惯，每天为宿舍打扫卫生，这一打扫就打扫了四年。所以我们宿舍从来没排过卫生值日表。另外，我每天都拎着宿舍的水壶去给同学打水，把它当作一种体育锻炼。大家看我打水习惯了，最后还产生这样一种情况，有的时候我忘了打水，同学就说“俞敏洪怎么还不去打水”。（笑声）。但是我并不觉得打水是一件多么吃亏的事情。因为大家都是一起同学，互相帮助是理所当然的。同学们一定认为我这件事情白做了。又过了十年，到了九五年年底的时候新东方做到了一定规模，我希望找合作者，结果就跑到了美国和加拿大去寻找我的那些同学，他们在大学的时候都是我生命的榜样，包括刚才讲到的王强老师等。我为了诱惑他们回来还带了一大把美元，每天在美国非常大方地花钱，想让他们知道在中国也能赚钱。我想大概这样就能让他们回来。后来他们回来了，但是给了我一个十分意外的理由。他们说：“俞敏洪，我们回去是冲着你过去为我们打了四年水。”（掌声）他们说：“我们知道，你有这样的一种精神，所以你有饭吃肯定不会给我们粥喝，所以让我们一起回中国，共同干新东方吧。”才有了新东方的今天。（掌声） 人的一生是奋斗的一生，但是有的人一生过得很伟大，有的人一生过得很琐碎。如果我们有一个伟大的理想，有一颗善良的心，我们一定能把很多琐碎的日子堆砌起来，变成一个伟大的生命。但是如果你每天庸庸碌碌，没有理想，从此停止进步，那未来你一辈子的日子堆积起来将永远是一堆琐碎。所以，我希望所有的同学能把自己每天平凡的日子堆砌成伟大的人生。（掌声）  |
Find missing number in 4 billinon 32 bit integers
Problem
Given a file with 4 billion 32bit integers, how do you find an missing integer from the file? In other words, which integer didn't show up in this file? You are given only 16MB memory.( not using external sorting)
solution
Like 3 bits. Suppose my list has 0, 1, 2, 3, 4, 6, 7. (sorted for convenience of explanation, but that's not a requirement)
000
001
010
011
100
110
111
Now count the bits:
number of bits from most significant to least significant bit position:
zeros: 4 3 4
ones: 3 4 3
Since the most-significant bit position is missing a 1, the middle bit position is missing a 0, and the least-significant bit position is missing a 1, we get this number to fill in the gaps:
101, or 5 decimal.
code
#include <iostream>
#include <fstream>
using namespace std;
int main() {
unsigned int number;
int bits[2][32] = {0};
ifstream numbers_file;
numbers_file.open("numbers.txt");
int i = 0;
numbers_file >> number;
while( ! numbers_file.eof()) {
for (i =0; i<32; i++){
int shifted = number>>i;
int bit = shifted % 2;
bits[bit][i]++;
}
numbers_file >> number;
}
unsigned int missing = 0;
for (i =31; i> -1; i--){
if(bits[0][i]>bits[1][i]) missing++;
missing = (missing<<1);
}
cout << "missing number is " << missing << endl;
}
面试很热门的抛鸡蛋问题
分析
Q: 只给你二个鸡蛋，你能上100层楼，你想知道鸡蛋的硬度。鸡蛋可能很硬或很脆弱，如果鸡蛋从第m层掉下而没破裂，而从第m+1层掉下就破裂了，那么这个鸡蛋的硬度就是m。你需要找出这个m和在最坏情况下最少试验次数。(经典鸡蛋问题)
A: 计算机学生可能会首先用第一个鸡蛋做二分搜索(O(logN))再用第二个递增做线性搜索（O(N)），最后必将用线性搜索结束因为用第二个鸡蛋时你无法确定最高一层。因此，问题变为如何使用第一个鸡蛋来减少线性搜索。
于是如果第一个蛋破裂在最高点我们要扔x-1次并且我们必须从x层高扔第一个蛋。现在如果第一个蛋的第一次扔没有破裂，如果第一个蛋在第二次扔破了我们要扔x-2次第二个蛋。假如16是答案，我需要扔16次才能找到答案。来验证一下是否可以从16层开始扔，首先从16层扔如果它破裂了，我们尝试所有其下的楼层从1到15；如果没破我们还能扔15次，于是我们将从32层(16+15+1)再扔。原因是如果它在32层破裂我们能尝试其下所有楼层从17到31最坏扔第二个蛋14次（总共能扔16次了）。如果32层并没破，我们还剩下能扔13次，依此类推得：
1 + 15 16 如果它在16层破裂，从1到15层最坏扔15次第二个蛋
1 + 14 31 如果它在31层破裂，从17到30层最坏扔14次第二个蛋
1 + 13 45.....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 在最后我们能轻易地做到因为我们有足够多扔的次数来完成任务
从上表我们能看到最佳的一个在最后一步将需要0次线性搜索。
能把上述规律写为: (1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.
令1+p=q上述式子变为q(q+1)/2>=100,对100解答得到q=14。
扔第一个蛋从层14，27，39，50，60，69，77，84，90，95，99，100直到它破裂，再开始扔第二个蛋。最坏情况只需14次。
代码
设计一个状态f[i][j]，表示有i层楼j个鸡蛋，最坏情况下要扔鸡蛋的次数。
由于一个鸡蛋扔下去就只有破和不破两种可能，所以状态转移就是f[i][j] = min(1+max(f[k-1][j-1], f[i-k][j]))，(1 <= k <= i)。如果要构造出一个可行解的话，稍微修改一下代码，记录下路径就应该可以了吧。
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
const int MAXN = 1001; // change it to the number you want
const int MAXM = 1001;
int n; // the number of floors
int m; // the number of eags
int f[MAXN][MAXM]; // the result
void init()
{
memset(f, 0, sizeof(f));
for (int j=1; j<MAXM; j++)
{
for (int i=1; i<MAXN; i++)
{
if (j == 1)
f[i][j] = i;
else{
for (int k=1; k<=i; k++)
{
int tmp = 1+max(f[k-1][j-1], f[i-k][j]);
if (f[i][j]==0 || f[i][j]>tmp)
f[i][j] = tmp;
}
}
}
}
}
int main()
{
init();
printf("Hey cin n, m\n");
while (scanf("%d%d", &n, &m) != EOF)
printf("%d\n", f[n][m]);
return 0;
}
Nvidia took my first Interview of life
This is a phone interview, i really feel excited about it:-), i hope i could get a pretty offer from such an amazing company!
Understanding reference counting with Objective C
Let's start with retain and release; autorelease is really just a special case once you understand the basic concepts.
In Cocoa, each object keeps track of how many times it is being referenced (specifically, the NSObject base class implements this). By calling retain on an object, you are telling it that you want to up its reference count by one. By calling release, you tell the object you are letting go of it, and its reference count is decremented. If, after calling release, the reference count is now zero, then that object's memory is freed by the system.
The basic way this differs from malloc and free is that any given object doesn't need to worry about other parts of the system crashing because you've freed memory they were using. Assuming everyone is playing along and retaining/releasing according to the rules, when one piece of code retains and then releases the object, any other piece of code also referencing the object will be unaffected.
What can sometimes be confusing is knowing the circumstances under which you should call retain and release. My general rule of thumb is that if I want to hang on to an object for some length of time (if it's a member variable in a class, for instance), then I need to make sure the object's reference count knows about me. As described above, an object's reference count is incremented by calling retain. By convention, it is also incremented (set to 1, really) when the object is created with an "init" method. In either of these cases, it is my responsibility to call release on the object when I'm done with it. If I don't, there will be a memory leak.
Example of object creation:
NSString* s = [[NSString alloc] init]; // Ref count is 1
[s retain]; // Ref count is 2 - silly
// to do this after init
[s release]; // Ref count is back to 1
[s release]; // Ref count is 0, object is freed
Now for autorelease. Autorelease is used as a convenient (and sometimes necessary) way to tell the system to free this object up after a little while. From a plumbing perspective, when autorelease is called, the current thread's NSAutoreleasePool is alerted of the call. The NSAutoreleasePool now knows that once it gets an opportunity (after the current iteration of the event loop), it can call release on the object. From our perspective as programmers, it takes care of calling release for us, so we don't have to (and in fact, we shouldn't).
What's important to note is that (again, by convention) all object creation class methods return an autoreleased object. For example, in the following example, the variable "s" has a reference count of 1, but after the event loop completes, it will be destroyed.
NSString* s = [NSString stringWithString:@"Hello World"];
If you want to hang onto that string, you'd need to call retain explicitly, and then explicitly release it when you're done.
Consider the following (very contrived) bit of code, and you'll see a situation where autorelease is required:
- (NSString*)createHelloWorldString
{
NSString* s = [[NSString alloc] initWithString:@"Hello World"];
// Now what? We want to return s, but we've upped its reference count.
// The caller shouldn't be responsible for releasing it, since we're the
// ones that created it. If we call release, however, the reference
// count will hit zero and bad memory will be returned to the caller.
// The answer is to call autorelease before releasing the string. By
// explicitly calling autorelease, we pass the responsibility for
// releasing the string on to the thread's NSAutoreleasePool, which will
// happen at some later. The consequence is that the returned string
// will still be valid for the caller of this function.
return [[s autorelease] release];
}
I realize all of this is a bit confusing - at some point, though, it will click. Here are a few references to get you going:
* Apple's introduction to memory management.
* Cocoa Programming for Mac OS X (3rd Edition), by Aaron Hillegas - a very well written book will lots of great examples. It reads like a tutorial.
* If you're truly diving in, you could head to Big Nerd Ranch. This is a training facility run by Aaron Hillegas - the author of the book mentioned above. I attended the Intro to Cocoa course there several years ago, and it was a great way to learn.
9 Tips for the aspiring Emacs playboy
I consider myself a beginning Lisper. I've been developing my software in Emacs for 8 months now. At first, I was clumsy at it. Emacs can be difficult and daunting. The terminology is different from what I'm used to, the key bindings are different, and there are just so many commands, configurations, and modes. But I've persevered and I now find myself quite nimble with key bindings and structured editing. And yet there's still more to learn. The subject of what to learn is treated in many online tutorials and printed books. But here, now, I thought I'd share some tips I use to keep the key bindings in my head from being garbage collected. Create your own cheat sheet with ten key bindings you'd like to learn. No more than 10. Don't burden yourself with a gigantic list you'll have to search through. You won't be able to find them quickly enough, and you'll stop referring to the sheet. Make it a point to use bindings from the cheat sheet while you code. At first, your cheat sheet will have the basic commands you need to master. But it will evolve as you do . . . Get rid of the tool bar (tool-bar-mode -1) and the menu bar (menu-bar-mode -1). Don't touch the mouse. If you find yourself using the mouse too much, open up emacs in a terminal instead of in X. When you find yourself reaching for the mouse, think of a way to use the keyboard to get to where you want. In no time, you'll be flying around the text like a crazy rocket-powered hamster on steroids instead of some wimpy mouse. Lots of people post their .emacs file for bragging/demonstration purposes. These often have great tips/insights into a configuration/mode that you didn't know about. This is like getting a look directly into the brain of an experienced Emacs user. Cut and paste and read the comments. Ok, so you've got a cheat sheet. Now what? After a week or two of using a single, ten item cheat sheet, go through the sheet and decide which key bindings you've graduated from. Do you use it often enough not to forget it? Do you want to forget it? Will you remember it without the cheat sheet? Do you remember what it does? When you've whittled down your sheet so that it again contains only those key bindings that you want to remember but don't, add some more from the list of interesting commands you've been keeping. But don't exceed a total list size of ten! There are a lot of key bindings that are universally accepted as standard. When you're still learning, you won't know which those are, and you'll destroy any chance you have of fluency in another Emacs window if you change them. There's nothing worse than sitting down at a terminal and being totally lost with the commands because you're used to rebinding most of them. You might even do something awful. It's like being parachuted into a foreign country where "Hello, I come in peace." means "Your mother is ugly but she's good in bed." But at the same time, you might use some commands so much you want to rebind them to something more useful. It's a dilemma but I suggest keeping as many of the original key bindings as possible, especially at first. Online help is a great help (wow, really bad pun). Some help commands that you might find helpful (not again): Also, watch when you you type a command using M-x. If there is a key binding for it, it will tell it to you. In order to know when it is best to use which command, experimentation is your best option. Try out different commands and learn their strengths and weaknesses. Keyboard macros are a great thing to learn in their own right, but they can help you learn commands like a pro. When recording your macros, you have to think: "How can I do this so that this command will work perfectly a hundred times?". The thought process you have to go through to compose those commands will reinforce all of the possible ways to perform an action.Introduction
1. Post up a cheat sheet
2. Don't use the mouse
The mouse is a crutch for the beginner. It will keep you from learning keyboard commands. Using the keyboard will let you edit faster than the mouse ever can.3. Read other people's .emacs file
4. Write down any interesting commands you discover
While perusing help, reading .emacs files, loitering in the newsgroups, or surfing the web, you'll invariably find an Emacs command that you'll want to remember. You won't remember it unless you write it down. Sure, you may remember some, but not all. Keep a list of key bindings you don't want to forget. You will not be able to find it again.5. Update your cheat sheet
For each item on you cheat sheet, ask yourself these questions:6. Keep your key bindings standard
7. Use help
8. Experiment
In order to strengthen the human-Emacs symbiotic bond, you should experiment with different editing commands and editing modes. Most text editors only offer a couple of ways of navigating text. Here are some common ones: Arrow Keys, Home/End keys, PageUp/PageDown, and find. One of the strengths of Emacs is that you can treat the same text differently depending on what command you use. For instance, you treat it as characters with C-f and C-b. But you treat it as words with M-f and M-b. You treat it as s-exprs with C-M-f and C-M-b. Etc.9. Create keyboard macros
王泛森院士-如果让我重做一次研究生.
如果让我重做一次研究生......
在所里碰到刚从美国读完博士回来的同事，
献什么？」……
一、研究生与大学生的区别
首先跟大家说明一下研究生和大学生的区别。
造新的知识，
是恭喜你对人类的知识有所创新，因此授予你这个学位。」
新，这个创新或大或小，都是对于普遍的知识有所贡献。
究生是不同的。
（一）选择自己的问题取向，学会创新
你一旦是研究生，你就已经进入另一个阶段，
接受知识到创造知识，是身为一个研究生最大的特色，不仅如此，
己。做为研究生不再是对于各种新奇的课照单全收，
有一个关注的焦点，而不能像大学那般漫无目标。
论文，那篇论文是你个人所有武功的总集合，
（二）尝试跨领域研究，主动学习
提出一个重要的问题，跨越一个重要的领域，将决定你未来的成败。
关键，而你自己本身必须是带着问题来探究无限的学问世界，
点，来探究这些知识，产生有机的循环。
是一个主动的探索者，并学会悠游在这学术的领域。
我举一个例子，我们的中央研究院院长李远哲先生，得了诺贝尔奖。
他的故事。
不教他任何东西。可是隔壁那个教授，老师教很多，
说：「如果我知道结果，那我要你来这边念书做什么？
是他自己从这个什么都不教他，永远碰到他只问他「
但是最好的方式就是将这两个方式结合起来。
习「 self-help 」，而不能再像大学时代般，都是纯粹用听的，
域。
然而研究生另外一个重要的阶段就是 Learn how to learn ，不只是学习而已，而是学习如何学习，
要学习拿起那一根针，学会绣出一件漂亮的衣服，
读书，
而应该是要放在领域的普遍人里面。你这篇文章要有新的东西，
新。
二、一个老师怎么训练研究生
第二个，身为老师你要怎么训练研究生。
和同侪间密切的互动和学习是非常重要的，
你往后的生活应该或多或少都和这个探索有相关。
（一）善用与老师的伙伴关系，不断 Research
我常说英文 research 这个字非常有意义， search 是寻找，而 research 是再寻找，所以每个人都要 research ，不
断的一遍一遍再寻找，并进而使你的生活和学习成为一体。
条件一致者强，凡生活与战斗条件不一致者弱。」
长的，当中你所听到的每一句话，都可能带给你无限的启发。
回想当时我在美国念书的研究生生活，
等。所以能帮助解决问题的不单只是你的老师，
用毛泽东的「革命不是请客吃饭！」来跟他讲：「
（二）藉由大量阅读和老师提点，进入研究领域
怎样进入一个领域最好，我个人觉得只有两条路，
学生就会知道这个领域有些什么，
局在讲什么。藉由学生的报告，
碰到问题可以看哪些东西。就像是我在美国念书的时候，
只是不停的开书目，运用这样的方式慢慢训练，
到问题也有能力可以去查询相关的资料。
（三）循序渐进地练习论文写作
到了硕士或博士最重要的一件事，是完成一篇学位论文，
不知道教育方面的论文情况是如何，但是史学的论文都要写二、
体架构组织得通畅可读？首先，必须要从一千字、五千字、
字。这么大规模的论文谁都写得出来，问题是写得好不好，
铜钱；是一间大礼堂，而不是一间小小分割的阁楼。
因为受计算机的影响，我发现很多学生写文章能力都大幅下降。
过慢慢练习会使你的文笔跟思考产生一致的连贯性。
果有好的文笔当然更棒，但那是可遇不可求的，
的还是把内容陈述清楚，从一万字到最后十万字的东西，
我在念书的时候，有一位欧洲史、英国史的大师 Lawrence Stone ，他目前已经过世了，曾经有一本书访问十位最了不起的史学家，
访问中说了一句非常吸引人注意的话，他说他英文文笔相当好，
的地位。内容非常重要，有好的表达工具更是具有加分的作用，
三、研究生如何训练自己
（一）尝试接受挑战，勇于克服
研究生如何训练自己？就是每天、每周或每个月给自己一个挑战，
克服那个挑战，但是要努力去尝试。我在我求学的生涯中，
碰到一个很聪明的人，他就是没办法克服他给自己的挑战，
某一个期限内，无论如何一定要把这三行字改掉，
我挑战三次总会完成一次，完成一次就够了，
你，不一定能做到的事情。不过也要切记，
（二）论文的写作是个训练过程，不能苛求完成精典之作
各位要记得我以前的老师所说的一句话：「
没有办法好好的完成硕士论文，或是博士论文，
后的时间很难再有三年或六年的时间，
教授还要指导学生、上课，因此非常的忙碌，
就一点都不奇怪了。
不一定要刻意强求，要有这是一个训练过程的信念，
是要调整自己的心态，把论文的完成当成一个目标，
摊有一位非常博学多文的旧书店老板，我常常赞叹的对他说：「
文当成要写一本经典，那当然永远写不完。
士那二十几页的论文，不过切记不要把那个当作是目标，
论文，不要一开始就期待它是经典之作。如果你期待它是经典之作，
候我在找一本书，但它并没有在旧书店里面，不过他告诉我：「
个旧书店的老板精熟每一本书，可是他就是永远无法完成，
（三）论文的正式写作
1. 学习有所取舍
到了写论文的时候，要能取也要能舍，因为现在信息爆炸，
树挂相关的东西，但千万不要不断的挂不相关的东西，
这棵知识树要如何形成？第一步你必须对所关心的领域中，
2. 形成你的知识树
我昨天还请教林毓生院士，他今年已经七十几岁了，
五、六本书要读好几遍。」因为林毓生先生是海耶克，
理，虽然你不可能只读那几本重要的书，但是那五、
放一边。生也有涯，知也无涯，你不可能读遍天下所有的好书，
落得普林斯顿街上的那位旧书店的老板一般，
3. 掌握工具
在这个阶段一定要掌握语文与合适的工具。
一个语文，不管是英文、日文、法文 …… 等，一定要有一个语文能够非常流畅的阅读相关书籍，
受限制，因为语文就如同是一扇天窗，
不懂，你就不知道如何找人来帮你或是自己查相关的数据。
具学会。
4. 突破学科间的界线
应该要把跨学科的学习当作是一件很重要的事，
概念，对于本身关心的问题产生另一种不同的启发，
发生在学科交会的地方。为什么会如此？
时候，很多都带有那个时代的思想跟学术背景，比如说，
尔经济奖，这二十年来所颁的奖，
Nash 这位数学家也得诺贝尔经济奖，为什么？
的地方已经 search 太多次了，因此不一定能有很大的创新，
常常一篇硕士论文或博士论文最重要、最关键的，
着手电筒在这个小仓库里面照来照去照太久了，
位数学家为什么会得诺贝尔数学奖？
以用在经济方面来思考，而这个东西在一开始，
关系，在数学的这一个部分也没有大关系，不过两个加在一起，
5. 论文题目要有延展性
对一个硕士生或博士生来说，如果选错了题目，就是失败，
就是要花在这上面，你要不断的跟老师商量寻找一个有意义、
案，就有一万四千个袋子，就要送给一万四千个教授审查。
好，我的著作很好，所以我来申诉。」
常常被拿出来讨论的，就是这个题目不必再做了、
的。
我的学生常常选非常难的题目，我说你千万不要这样，
要挤很多东西，才能筛选出一点点内容，
我写过好几本书，我认为我对每一本书的花的心力都是一样，
好的书，是我二十几岁刚到史语所那一年所写的那本书。
且还是用我以前旧的笔记写的。大陆这些年有许多出版社，
文有错字，因为在军队营区里面随时都要出操、随时就要集合，
有力气校正。
为什么举这个例子呢？我后来想一想，那本书之所以比较好，
剑桥大学出的那一本，不过我认为我最好的书一定是用中文写的，
三分随意，那时候你才可以说对于这一个语文完全理解与精熟，
回到我刚刚讲的，其实每一本书、每一篇论文我都很想把它写好。
的所有训练跟努力才有价值。我在这里建议大家，
可能只有五年，如果你的材料太不集中，
厌数字，但却选了一个全都要靠统计的论文，那是不可能做得好。
6. 养成遵照学术格式的写作习惯
另一个最基本的训练，就是平时不管你写一万字、三万字、
究生的阶段就要培养成为你生命中的一个部份，
几百页，如果一开始弄错了，后来再重头改到尾，一定很耗时费力，
哪一个书名号该在哪里、哪一个地方要用引号、
还很封闭的时候，有一个人从美国回来就说：「
引用。」他的名字就叫 ibid 。所谓 ibid 就是同前作者，这个字是从拉丁文发展出来的，
同编的。英文有一本 The Chicago Manual of Style 就是专门说明这一些写作规范。各位要尽早学会中英文的写作规范，
习，最后随性下笔，就能写出符合规范的文章。
7. 善用图书馆
图书馆应该是研究生阶段最重要的地方，不必读每一本书，
情，就是要把书名看一看。在某些程度上知道书皮就够了，
算机就可以查到书名，可是我还是非常珍惜这种定期去 browse 新到的书的感觉，或去看看相关领域的书长成什么样子。
息教授，他告诉我他在创造力最高峰的时候，
过切记不重要的不要花时间去看，你们生活在信息泛滥的时代，
学生引用一些三流的论文，却引得津津有味，我都替他感到难过，
8. 留下时间，精致思考
还要记得给自己保留一些思考的时间。一篇论文能不能出神入化、
是提醒大家要在一般的层次再提升两三步， conceptualize 你所看到的东西。真切去了解，你所看到的东西是什么？
廓是什么？千万不要被枝节淹没，虽然枝节是你最重要的开始，
难教的东西，我记得我念书时，有位老师信誓旦旦说要开一门课，
的是，在被很多材料和枝节淹没的时候，要适时跳出来想一想，
傅斯年先生来到***以后，