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:

Little old lady，riding a bus."Little boy, can you tell me how to get off at Pasadena Street?"

Little boy. "just watch me, and get off two stops before I do."

百度一面就被fault了

感谢Nvidia，Tencent，Baidu给机会我面试，是时候总结一下自己的面试经历了。笔试了很多公司，大大小小，像阿里巴巴，微软，朗讯，甲骨文，深信服（舍友就是签了这间的），华为等，他们都因为自己幼稚，水平做题水平低下，没有就会面试。总体来说，每次面试自己对缺乏主动询问自己所申请的职位的相关信息，没有把自己的意愿所表示出来，Nvidia是电话面试，面试官叫阿Ted，感觉他很不错，所问的问题都是很简单的，但是自己感觉对硬件不是很感兴趣，所以明知道他问些简单的数字电路问题，也没有去预先准备，这个不能怪谁，因为我知道自己更喜欢往软件或者互联网方向发展。Tencent的一面感觉自己表现不错，面试官很nice，没有问他的名字，太可惜了，毕竟他是第一个现场面试自己的人。但是二面挂了，理由很简单，他们想招的是网管，而我却说出来自己想当个程序员的欲望，后来经理也特意暗示了我的下场，而且还问了些服务器坏掉的解决方案，明知道我没有哪个方面的东西，还是往那边的问，我也没有办法了，临走时，他就主动跟我说“感谢你参加腾讯的这次招聘活动”，唯有泪奔。昨天刚刚面完baidu，这是第一次正式通过笔试，要知道我可以准备了一个多星期的，在那段日子里，我根本就没有再海投，专心一志，看算法导论，看programming peals，看programming interviews exposed，做n多的面试笔试题目，因为华为也同时过来，所以自己很好的准备一番，但不是知道为何，baidu的笔试过了，而华为的没有通过，问谁都知道baidu的题目更加难，而华为考的是基础题目，这个也很遗憾。不过据说华为要群殴，可惜没有机会参加。baidu的面试官人长得很踏实，我进来的是个昨天刚面完华为的牛逼研究生，他可是没有理会百度当天的面试请求，参加华为的面试的，不过据说晚上百度还是邀请他去面试了，够牛的。因为我的简历写着学习进步奖，所以他问了我的成绩，这个意思人人都知道的，我也没有说什么，只能说自己中等生，但是最好一次有点进步所以得到进步奖了，接着他叫我shell小程序，内容就不说了，很简单的，但是我说自己已经忘记语法了，这个和简历上的东西有点不符合把，他说好了，然后叫我做智力题，我心里感觉很不爽，因为知道飞来同学在面试腾讯的时候被问一个智力题而挂了，我还说自己很少做这类东西的，说完题目，他就去上网了，叫我好好思考，我没有法，只能好好想了，最后还真做出了，回来查网上的解答也是同样的做法，据说是ms的题目，这时他说这次的技术方面的东西就结束了，这之前他还叫我介绍了自己的小小项目，这个好像是例牌来的，没有啥好说，然后开始了提问环节，我估计自己就是在这里失败的，最后他问我还有没有别的问题，还很该死的说外面很漂亮，我想出去走走，我也不知道自己为何会说出这种话的，可能自己太紧张了，这时我想他一定是心里说，那么你以后就别再想有机会进来了，这次打击很大，面对自己喜欢的公司，而无力挽回，实在是很伤心。

同宿舍的同学已经有找到不错的工作了，在今年这种气氛，能够及早有着落，太幸福了，仰慕中。刚刚问了一下老托，他说现在17周了，班左里大概有5个右的同学有offer，找工的大概有40人，要加紧点了，写这些东西，希望警戒自己，以后好好努力，能够找到自己向往的工作。千万不要这么早就灰心了，生活毕竟要继续的，baidu的伤要慢慢治疗，不要这样就放弃了。

笔试概率题目

题目
有两个数组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年开学典礼上的发言

在北京大学2008年开学典礼上的发言 英语系80级校友、新东方教育科技集团董事长兼总裁俞敏洪 2008年9月21日 　　北大原来从未邀请过校友在开学典礼上讲话，2008年开学典礼，北大邀请了新东方教育科技集团董事长兼总裁俞敏洪老师讲话，这是俞老师的一种荣幸，更是新东方的一种荣誉。 各位同学、各位领导： 大家上午好！（掌声） 非常高兴许校长给我这么崇高的荣誉，谈一谈我在北大的体会。（掌声） 可以说，北大是改变了我一生的地方，是提升了我自己的地方，使我从一个农村孩子最后走向了世界的地方。毫不夸张地说，没有北大，肯定就没有我的今天。北大给我留下了一连串美好的回忆，大概也留下了一连串的痛苦。正是在美好和痛苦中间，在挫折、挣扎和进步中间，最后找到了自我，开始为自己、为家庭、为社会能做一点事情。 学生生活是非常美好的，有很多美好的回忆。我还记得我们班有一个男生，每天都在女生的宿舍楼下拉小提琴，（笑声）希望能够引起女生的注意，结果后来被女生扔了水瓶子。我还记得我自己为了吸引女生的注意，每到寒假和暑假都帮着女生扛包。（笑声、掌声）后来我发现那个女生有男朋友，（笑声）我就问她为什么还要让我扛包，她说为了让男朋友休息一下（笑声、掌声）。我也记得刚进北大的时候我不会讲普通话，全班同学第一次开班会的时候互相介绍，我站起来自我介绍了一番，结果我们的班长站起来跟我说：“俞敏洪你能不能不讲日语？”（笑声）我后来用了整整一年时间，拿着收音机在北大的树林中模仿广播台的播音，但是到今天普通话还依然讲得不好。 人的进步可能是一辈子的事情。在北大是我们生活的一个开始，而不是结束。有很多事情特别让人感动。比如说，我们很有幸见过朱光潜教授。在他最后的日子里，是我们班的同学每天轮流推着轮椅在北大里陪他一起散步。（掌声）每当我推着轮椅的时候，我心中就充满了对朱光潜教授的崇拜，一种神圣感油然而生。所以，我在大学看书最多的领域是美学。因为他写了一本《西方美学史》，是我进大学以后读的第二本书。 为什么是第二本呢？因为第一本是这样来的，我进北大以后走进宿舍，我有个同学已经在宿舍。那个同学躺在床上看一本书，叫做《第三帝国的兴亡》。所以我就问了他一句话，我说：“在大学还要读这种书吗？”他把书从眼睛上拿开，看了我一眼，没理我，继续读他的书。这一眼一直留在我心中。我知道进了北大不仅仅是来学专业的，要读大量大量的书。你才能够有资格把自己叫做北大的学生。（掌声）所以我在北大读的第一本书就是《第三帝国的兴亡》，而且读了三遍。后来我就去找这个同学，我说：“咱们聊聊《第三帝国的兴亡》”，他说：“我已经忘了。”（笑声） 　　我也记得我的导师李赋宁教授，原来是北大英语系的主任，他给我们上《新概念英语》第四册的时候，每次都把板书写得非常的完整，非常的美丽。永远都是从黑板的左上角写起，等到下课铃响起的时候，刚好写到右下角结束。（掌声）我还记得我的英国文学史的老师罗经国教授，我在北大最后一年由于心情不好，导致考试不及格。我找到罗教授说：“这门课如果我不及格就毕不了业。”，罗教授说：“我可以给你一个及格的分数，但是请你记住了，未来你一定要做出值得我给你分数的事业。”（掌声）所以，北大老师的宽容、学识、奔放、自由，让我们真正能够成为北大的学生，真正能够得到北大的精神。 当我听说许智宏校长对学生唱《隐形的翅膀》的时候，我打开视频，感动得热泪盈眶。因为我觉得北大的校长就应该是这样的。（掌声） 我记得自己在北大的时候有很多的苦闷。一是普通话不好，第二英语水平一塌糊涂。尽管我高考经过三年的努力考到了北大——因为我落榜了两次，最后一次很意外地考进了北大。我从来没有想过北大是我能够上学的地方，她是我心中一块圣地，觉得永远够不着。但是那一年，第三年考试时我的高考分数超过了北大录取分数线七分，我终于下定决心咬牙切齿填了“北京大学”四个字。我知道一定会有很多人比我分数高，我认为自己是不会被录取的。没想到北大的招生老师非常富有眼光，料到了三十年后我的今天。（掌声）但是实际上我的英语水平很差，在农村既不会听也不会说，只会背语法和单词。我们班分班的时候，五十个同学分成三个班，因为我的英语考试分数不错，就被分到了A班，但是一个月以后，我就被调到了C班。C班叫做“语音语调及听力障碍班”。（ 笑声） 我也记得自己进北大以前连《红楼梦》都没有读过，所以看到同学们一本一本书在读，我拼命地追赶。结果我在大学差不多读了八百多本书，用了五年时间（掌声）。但是依然没有赶超上我那些同学。我记得我的班长王强是一个书癖，现在他也在新东方，是新东方教育研究院的院长。他每次买书我就跟着他去，当时北大给我们每个月发二十多块钱生活费，王强有个癖好就是把生活费一分为二，一半用来买书，一半用来买饭菜票。买书的钱绝不动用来买饭票。如果他没有饭菜票了就到处借，借不到就到处偷。（笑声）后来我发现他这个习惯很好，我也把我的生活费一份为二，一半用来买书，一半用来买饭菜票，饭票吃完了我就偷他的。（笑声掌声） 毫不夸张地说，我们班的同学当时在北大，真是属于读书最多的班之一。而且我们班当时非常地活跃，光诗人就出了好几个。后来挺有名的一个诗人叫西川，真名叫刘军，就是我们班的。（掌声）我还记得我们班开风气之先，当时是北大的优秀集体，但是有一个晚上大家玩得高兴了，结果跳起了贴面舞，第二个礼拜被教育部通报批评了。那个时候跳舞是必须跳得很正规的，男女生稍微靠近一点就认为违反风纪。所以你们现在比我们当初要更加幸福一点。不光可以跳舞，而且可以手拉手地在校园里面走，我们如果当时男女生手拉手在校园里面走，一定会被扔到未名湖里，所以一般都是晚上十二点以后再在校园里面走。（笑声掌声） 我也记得我们班五十个同学，刚好是二十五个男生二十五个女生，我听到这个比例以后当时就非常的兴奋（笑声），我觉得大家就应该是一个配一个。没想到女生们都看上了那些外表英俊潇洒、风流倜傥的男生。像我这样外表不怎么样，内心充满丰富感情、未来有巨大发展潜力的，女生一般都看不上。（笑声掌声） 我记得我奋斗了整整两年希望能在成绩上赶上我的同学，但是就像刚才吕植老师说的，你尽管在中学高考可能考得很好，是第一名，但是北大精英人才太多了，你的前后左右可能都是智商极高的同学，也是各个省的状元或者说第二名。所以，在北大追赶同学是一个非常艰苦的过程，尽管我每天几乎都要比别的同学多学一两个小时，但是到了大学二年级结束的时候我的成绩依然排在班内最后几名。非常勤奋又非常郁闷，也没有女生来爱我安慰我。（笑声）这导致的结果是，我在大学三年级的时候得了一场重病，这个病叫做传染性侵润肺结核。当时我就晕了，因为当时我正在读《红楼梦》，正好读到林黛玉因为肺结核吐血而亡的那一章，（笑声）我还以为我的生命从此结束，后来北大医院的医生告诉我现在这种病能够治好，但是需要在医院里住一年。我在医院里住了一年，苦闷了一年，读了很多书，也写了六百多首诗歌，可惜一首诗歌都没有出版过。从此以后我就跟写诗结上了缘，但是我这个人有丰富的情感，但是没有优美的文笔，所以终于没有成为诗人。后来我感到非常的庆幸，因为我发现真正成为诗人的人后来都出事了。我们跟当时还不太出名的诗人海子在一起写过诗。后来他写过一首优美的诗歌，叫做《面朝大海，春暖花开》，我们每一个同学大概都能背。后来当我听说他卧轨自杀的时候，嚎啕大哭了整整一天。从此以后，我放下笔，再也不写诗了。（掌声） 记得我在北大的时候，到大学四年级毕业时，我的成绩依然排在全班最后几名。但是，当时我已经有了一个良好的心态。我知道我在聪明上比不过我的同学，但是我有一种能力，就是持续不断的努力。所以在我们班的毕业典礼上我说了这么一段话，到现在我的同学还能记得，我说：“大家都获得了优异的成绩，我是我们班的落后同学。但是我想让同学们放心，我决不放弃。你们五年干成的事情我干十年，你们十年干成的我干二十年，你们二十年干成的我干四十年”。（ 掌声）我对他们说：“如果实在不行，我会保持心情愉快、身体健康，到八十岁以后把你们送走了我再走。”（笑声掌声） 有一个故事说，能够到达金字塔顶端的只有两种动物，一是雄鹰，靠自己的天赋和翅膀飞了上去。我们这儿有很多雄鹰式的人物，很多同学学习不需要太努力就能达到高峰。很多同学后来可能很轻松地就能在北大毕业以后进入哈佛、耶鲁、牛津、剑桥这样的名牌大学继续深造。有很多同学身上充满了天赋，不需要学习就有这样的才能，比如说我刚才提到的我的班长王强，他的模仿能力就是超群的，到任何一个地方，听任何一句话，听一遍模仿出来的绝对不会两样。所以他在北大广播站当播音员当了整整四年。我每天听着他的声音，心头咬牙切齿充满仇恨。（笑声）所以，有天赋的人就像雄鹰。但是，大家也都知道，有另外一种动物，也到了金字塔的顶端。那就是蜗牛。蜗牛肯定只能是爬上去。从低下爬到上面可能要一个月、两个月，甚至一年、两年。在金字塔顶端，人们确实找到了蜗牛的痕迹。我相信蜗牛绝对不会一帆风顺地爬上去，一定会掉下来、再爬、掉下来、再爬。但是，同学们所要知道的是，蜗牛只要爬到金字塔顶端，它眼中所看到的世界，它收获的成就，跟雄鹰是一模一样的。（掌声）所以，也许我们在座的同学有的是雄鹰，有的是蜗牛。我在北大的时候，包括到今天为止，我一直认为我是一只蜗牛。但是我一直在爬，也许还没有爬到金字塔的顶端。但是只要你在爬，就足以给自己留下令生命感动的日子。（掌声） 我常常跟同学们说，如果我们的生命不为自己留下一些让自己热泪盈眶的日子，你的生命就是白过的。我们很多同学凭着优异的成绩进入了北大，但是北大绝不是你们学习的终点，而是你们生命的起点。在一岁到十八岁的岁月中间，你听老师的话、听父母的话，现在你真正开始了自己的独立生活。我们必须为自己创造一些让自己感动的日子，你才能够感动别人。我们这儿有富裕家庭来的，也有贫困家庭来的，我们生命的起点由不得你选择出生在富裕家庭还是贫困家庭，如果你生在贫困家庭，你不能说老爸给我收回去，我不想在这里待着。但是我们生命的终点是由我们自己选择的。我们所有在座的同学过去都走得很好，已经在十八岁的年龄走到了很多中国孩子的前面去，因为北大是中国的骄傲，也可以说是世界的骄傲。但是，到北大并不意味着你从此大功告成，并不意味着你未来的路也能走好，后面的五十年、六十年，甚至一百年你该怎么走，成为了每一个同学都要思考的问题。就本人而言，我觉得只要有两样东西在心中，我们就能成就自己的人生。 第一样叫做理想。我从小就有一种感觉，希望穿越地平线走向远方，我把它叫做“穿越地平线的渴望”。也正是因为这种强烈的渴望，使我有勇气不断地高考。当然，我生命中也有榜样。比如我有一个邻居，非常的有名，是我终生的榜样，他的名字叫徐霞客。当然，是五百年前的邻居。但是他确实是我的邻居，江苏江阴的，我也是江苏江阴的。因为崇拜徐霞客，直接导致我在高考的时候地理成绩考了九十七分。（掌声）也是徐霞客给我带来了穿越地平线的这种感觉，所以我也下定决心，如果徐霞客走遍了中国，我就要走遍世界。而我现在正在实现自己这一梦想。所以，只要你心中有理想，有志向，同学们，你终将走向成功。你所要做到的就是在这个过程要有艰苦奋斗、忍受挫折和失败的能力，要不断地把自己的心胸扩大，才能够把事情做得更好。 第二样东西叫良心。什么叫良心呢？就是要做好事，要做对得起自己对得起别人的事情，要有和别人分享的姿态，要有愿意为别人服务的精神。有良心的人会从你具体的生活中间做的事情体现出来，而且你所做的事情一定对你未来的生命产生影响。我来讲两个小故事，讲完我就结束我的讲话，已经占用了很长的时间。 第一个小故事。有一个企业家和我讲起他大学时候的一个故事，他们班有一个同学，家庭比较富有，每个礼拜都会带六个苹果到学校来。宿舍里的同学以为是一人一个，结果他是自己一天吃一个。尽管苹果是他的，不给你也不能抢，但是从此同学留下一个印象，就是这个孩子太自私。后来这个企业家做成功了事情，而那个吃苹果的同学还没有取得成功，就希望加入到这个企业家的队伍里来。但后来大家一商量，说不能让他加盟，原因很简单，因为在大学的时候他从来没有体现过分享精神。所以，对同学们来说在大学时代的第一个要点，你得跟同学们分享你所拥有的东西，感情、思想、财富，哪怕是一个苹果也可以分成六瓣大家一起吃。（掌声）因为你要知道，这样做你将来能得到更多，你的付出永远不会是白白付出的。 我再来讲一下我自己的故事。在北大当学生的时候，我一直比较具备为同学服务的精神。我这个人成绩一直不怎么样，但我从小就热爱劳动，我希望通过勤奋的劳动来引起老师和同学的的注意，所以我从小学一年级就一直打扫教室卫生。到了北大以后我养成了一个良好的习惯，每天为宿舍打扫卫生，这一打扫就打扫了四年。所以我们宿舍从来没排过卫生值日表。另外，我每天都拎着宿舍的水壶去给同学打水，把它当作一种体育锻炼。大家看我打水习惯了，最后还产生这样一种情况，有的时候我忘了打水，同学就说“俞敏洪怎么还不去打水”。（笑声）。但是我并不觉得打水是一件多么吃亏的事情。因为大家都是一起同学，互相帮助是理所当然的。同学们一定认为我这件事情白做了。又过了十年，到了九五年年底的时候新东方做到了一定规模，我希望找合作者，结果就跑到了美国和加拿大去寻找我的那些同学，他们在大学的时候都是我生命的榜样，包括刚才讲到的王强老师等。我为了诱惑他们回来还带了一大把美元，每天在美国非常大方地花钱，想让他们知道在中国也能赚钱。我想大概这样就能让他们回来。后来他们回来了，但是给了我一个十分意外的理由。他们说：“俞敏洪，我们回去是冲着你过去为我们打了四年水。”（掌声）他们说：“我们知道，你有这样的一种精神，所以你有饭吃肯定不会给我们粥喝，所以让我们一起回中国，共同干新东方吧。”才有了新东方的今天。（掌声） 人的一生是奋斗的一生，但是有的人一生过得很伟大，有的人一生过得很琐碎。如果我们有一个伟大的理想，有一颗善良的心，我们一定能把很多琐碎的日子堆砌起来，变成一个伟大的生命。但是如果你每天庸庸碌碌，没有理想，从此停止进步，那未来你一辈子的日子堆积起来将永远是一堆琐碎。所以，我希望所有的同学能把自己每天平凡的日子堆砌成伟大的人生。（掌声）