google宣讲会和笔试经历.doc

google宣讲会和笔试经历笔试第一次宣讲和笔试的机会给了Google，谁叫它开始的早呢？上次百度就因为错过了投简历的时间而放弃了。其实将来自己去哪儿我觉得在水平一定的情况下更多的还是靠运气，不过这种锻炼的机会还是越多越好，当然这个锻炼是花时间的。9月底就投了Google的简历，昨天收到了邀请函。今天18:10到达宣讲会场，人真是多啊，队伍从会场门口排了将近100来米，而且后来才发现其实另外一个方向还有一队。18:15左右开始进场，直到18:40我离门口还有10来米，可见人有多少了。不过正在这时，前面一阵骚乱，我看到前面的队伍都散了，有些人拥到了一块，然后散开，我听到一个人说“会场坐满了，去别的教室”，然后也挤到前面看到每个人要根据自己的号去不同的考场，我于是就离开去我要去的3100。而这时我看到我后面的队伍至少还有100多米。差10分7点到了教室，坐在那儿等，知道今天的宣讲是听不了了，只能等笔试了。我又不知道几点笔试，走也走不了，身上什么东西都没带，所以只好趴在那儿睡觉。有了这次的经验，以后笔试一定得带本什么书。直到19:45左右，有三个看上去比我还年轻的小姑娘进了教室，身上都穿着统一的Google的T-shirt。8点左右，我们被请出教室，然后依次核对了身份再进入教室坐下，直到8:45才正式开始考试，这中间人陆陆续续的来到，我大概看了一眼，共有大约90-100人，按照这个数计算一共六个考场，怎么也得有600来人。Google在北京只有两个学校开宣讲会北大和清华，所以这么算来，人还是相当多的。环顾四周，我发现像我这种谁都不认识的人还是少数，好多人都是几个、十几个人一起来笔试，坐在那里聊天。发了卷子看了一下，第一页是个人信息，后面有六页考题，选择题三页，大题三道，每道一页。时间对我来说基本还可以，正好答完，中间有时间慢慢思考。总的来说，我觉得Google的考题出的还是不错的，我在5号那天看了一上午的google和百度的之前的笔试题目，发现好多都不会，尤其是百度的题目出的挺bt，竟是些极其具体的题，比如某个linux的命令，或者用shell编的一个程序的输出。如果没用过linux的人来说肯定是100%不会，用过的可能都会，而用与不用其实只是是否是一个熟练工种的区别。而这次google的题目我觉得都还不错，选择题除了前两个是考概念（IP协议和内存）之外，其它的题目都是考察基本的数据结构或者算法分析的能力题，这些题目不会涉及到某个具体的知识点或概念，而是纯粹考察学生的智力，所以这种题目做的比较有乐趣。三道大题是这样的：本帖隐藏的内容需要回复才可以浏览第一题：给定一个a，一个b和一个N，让计算机按照从小到大的顺序输出前N个能够被a或被b整除的数。并给出测试的例子说明你编写的程序是正确。这道题，我考完以后才觉得可能我把第二问理解错了，原意可能是说让自己举一个例子，然后说明我的程序能够输出正确的解。而我当时理解成为了，要求自己设计一个完备的测试例，来验证程序在任何可能的输入下是否正确。题目本身不难，就是中间有一句我忘了C语言分配内存的语句是不是Q=(int*)malloc(sizeof(int)*N)这么写了。第二题：任给一个字符串，里面包含大写和小写字母。编写一个程序使得将小写字母全部放到字符串的前面，顺序可以打乱。要求尽可能使用空间和时间效率好的算法。我的思路是：定义两个指针pH和pL，pH从左向右扫描字符串，pL从右向左扫描，如果pH指的是大写字母则停下，pL指的是小写字母则停下，然后pH和pL指的字符交换，然后pH继续右移，pL继续左移，直到pL=pH。我不知道这个题目的标准答案是什么，但是我觉得我这个应该就是最好的算法了。具体的coding应该没什么，就是尽可能多的写注释，以保证阅卷人能看得懂。第三题：给定一个无向无封闭环的图T，将它转换成一个树，使得树的深度尽可能的少，编写一个程序返回所有的可能的树的根节点的集合。给出这个程序的算法并分析程序的时间和空间复杂度。这道题我觉得按理说作为最后一道题应该挺难的，但是我编出来的算法却很简单，所以我不知道是不是我想的不对还是我的算法复杂度不好。总之我的思路就是，将图中度为1的节点以及和它们相连的边删掉，然后看图的定点集合是否为空，如果不是则重复这个操作，直到删除度为1的节点之后，图为空，那么这时候最后删除的这批节点就是题目中要求的所有可能的树的根节点集合。然后分析了一下时间和空间复杂度。就交卷了。出来以后，感觉挺轻松的，虽然不知道自己考的怎么样，但是至少我的第一次笔试还是没有我想象的那么痛苦的，或许是Google的题目出的比较好，有水平，所以心情倒是很愉快。能不能进面试其实也不重要（能进当然更好），至少经验值是赚到了，以后就不怕了。回来的路上下起了小雨，幸好我从考场出来的及时，没有淋的太厉害，回来也才22:30，正好洗个澡。这会儿已经过12点了，睡觉。明天继续好好工作。10月5日看到了google发来的宣讲会邀请函和笔试通知，上面说7号6点半在清华就业指导中心大厅举办宣讲会。昨天下午跟同学一块打车过去。去的还比较早，到那已经开始排队，好在队伍并不长。不得不说，google这次的宣讲和笔试组织的很不好。大概等了30分钟，组织者才开始让人进。这个就业指导大厅很小，最多也就坐200人。到后来，好多人都站着，还有很多人在门口不让进。宣讲会本来是8点就该结束，结果拖到了8点半。然后再换地方笔试，9点开始笔试，10点半结束。考完出来，发现竟然下雨了，也没带伞。等回到寝室，都11点多了。还第一次见到宿舍楼下那么多人等电梯。说实话，我一直都很向往google这个公司，它的企业文化和工作环境我都很喜欢。可是这个公司太牛了，只适合大牛，对我来说，只能憧憬，太遥远了。回到正题把，google的笔试题分两种，一种是选择题，一种是程序设计和算法题。选择题考的都很基础，考了很多os和数据结构的东西。因为很早之前就开始看书了，所以除了图的题我不会，其他都还比较有把握。程序设计题考得都比较基础。都是用c来写的，我不是很会c，幸好第二题可以用喜欢的语言写，我就用了java。两道程序题都要求用时间和空间复杂度小的算法。我一直都搞不明白时间和空间复杂度，再说了，我能写出算法来，完成题目，就已经很不错了，所以我的算法是比较笨拙的那种，在此就不用再议了。最后一道算法题是考图的，图我都没看过，光凭印象，乱写一通。总的来说，这次google的笔试题考得都很基础，我觉得题目出得很不错，不愧是it界一流的公司。题的难度也不大，对于算法很牛的研究生来说，这套题应该是小菜一碟把。昨天晚上回去就觉得累得不行，尤其是心。在google笔试之前我一直都雄心勃勃的想