千呼万唤，数模成绩出来了，校赛二等奖，达到了赛前的预期，还算是不错的结果。之后就是准备自己的简历，开始找实习。

在网上闲逛了一天，看了各种各样的教程，重点推荐《简历制作——step by step》，了解基本原则，然后开始动手。简历的排版有多种方式，最基本的是word版，拉拉表格，搞搞字体即可；花哨一点的可以用ps，indesign，只是有些牛刀杀鸡罢了；我不想弄的那么花哨，因此我选择用[tex]\LaTeX[/tex]排版我的简历。正式动手之前，我扫了一下《LaTeX2e中文用户手册》，进一步熟悉了定制[tex]\LaTeX[/tex]的方法，并找到了以下资料作为参考：

• moderncv：一个漂亮的latex "documentclass"。
• jerry's resume：我觉得这个简历太长了……足足有四五页……
• pluskid's resume：非常简洁清爽的简历

我呢，就仿照着pluskid简历的风格，自己制作了一份，pdf和tex源文件可以在这里下载。然后就去88上找相应的信息，稀里糊涂的投了几家，包括百度、阿里、intel等。百度和阿里的效率很高，邮箱发过去简历，不到二十分钟就有了回音，百度更是在当天中午就打来了电话，问我第二天有没有时间，直接电话面试一下。我说好的。于是在6月13号下午一点，我找工作的处女面就这样献给了百度。

首先是客套的自我介绍，原来面试官是浙大02级的学长，怪不得对我这么“照顾”（至少在投简历时我不期望我的资本能够赢得这次面试的机会）。然后就是正经八百的面试。第一道题目是，给你十个瓶子，每个瓶子里装有白色的粉末，其中有一个瓶子中的白粉放入水中30分钟后可以变成蓝色（姑且把这粉末想像成硫酸铜）。现在给你无限制的水，问，在四十分钟内，最少能用几个瓶子，可以将这瓶特殊的粉末鉴别出来。我的直觉是这个问题与小学生的“天平挑苹果“的智力题类似——比如给你3个苹果，两个重量一样，另外一个比较重，用天平一次就能挑出来。我想到的大体思想还是先确定一个大概的范围，比如确定这个“硫酸铜“在前面五个瓶子中，然后在进一步缩小范围。但是此题的难点在于，所给的时间40分钟只够一次实验的时间，多出来的十分钟倒是没什么用，迷惑人用的。进一步想是不是该采用两个集合求交的方法来鉴别呢。此时时间大概过了三分钟，我的大脑依然在飞速的思索。最后我给出的答案是，将十个瓶子分为四组，分别是{1,2,3}、{3,4,5}、{6,7,8}、{8,9,10}，每组三个瓶子都取出粉末放到编号为I, II, III, IV的瓶子里面。如果I, II同时变蓝，那么这个粉末就在第3瓶，如果III, IV同时变蓝，那么就是第8瓶，剩下的情况我们可以肯定这瓶粉末肯定在两个瓶子之中。不过结果不算完美，而我也只能得出这样的结果了。其实这道题目正确的答案是数的二进制表示法。我们将十个瓶子的编号{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}进行二进制编码，这样只需要四位二进制数即可，然后找四个瓶子装上水，对于白粉末，如果其二进制编码的某位上为1，我们就在相应的瓶子里放入该瓶的粉末（这话太绕了……），举个例子来说，瓶子3的四位二进制编码为0011，我们就在第I, II个瓶子中放入瓶子3中的粉末。所有的十个瓶子都这样做，最后，I, II, III, IV的颜色序列（蓝表示1，不变色表示0）就可以指示出“硫酸铜“所在瓶子的二进制编码！

第二道题目是一道概率题。概率是我的弱项，高中就学不好，大学更是一点都没有接触。题目大意是给你一个字符串（可能有几亿个字符），给定一个特殊的字符'a'，再给定一个可以产生0和1的随机数发生器，然后让你写一个函数，等概率地返回'a'的一个索引（就是'a'在字符串中的位置，比如字符串为aaba，那么a的索引为{0, 1, 3}，等概率地返回0、1或者3）。我说这简单啊，首先用[tex]O(n)[/tex]时间做一个扫描，将'a'的索引位置存储在另外一个数组中，假设为b[length_of_all_a]，然后用随机数发生器产生一串0、1，转换成十进制，再做x = '0101000...01' mod length_of_all_a的运算，然后返回b[x]就行了。说完了我就知道肯定有问题，这么简单通俗的方法就是一个没有学过计算机的人也能想得出来。果不其然，面试官开始刨根问底了。先是问了我时间和空间复杂度是多少，我说都是[tex]O(n)[/tex]，他说复杂度太高，我说要做扫描线性时间复杂度是必须的；然后他说有没有办法减少空间复杂度，毕竟最坏情况是[tex]O(n)[/tex]，比如这个超长的字符串全部都是'a'，那么存储索引需要的空间就是[tex]O(n)[/tex]的。我一时语塞，要了五分钟考虑时间。最后想出的方法是类似于二分的方法，首先肯定的是在空间复杂度小于[tex]O(n)[/tex]的要求下，我们不可能存储'a'的所有索引了。于是我想的方案就是看随机数发生器，如果是0，我们就去字符串的左半部分查找，否则就去右半部分查找，依次递归，当递归下去的字符串长度小于某个数值的时候，我们就用线性查找的方法，看看这个小串中有没有'a'存在，存在的话，返回索引值，否则向上回溯一层，去另一半查找。总之是很晕的一个山寨方法，而面试官竟然还能听懂，然后他问我怎么样证明这个就是等概率的呢。我说了几个“应该……“，都是凭感觉。再然后他给了我一个串“aaba“，照我的方法，前面个两个'a'被返回的概率有25%，最后一个'a'却有50%，这下我彻底无语了，只能承认自己没辙了。

第三个问题是关于c++的。问我c和c++的static关键字都有什么作用。我就balabalay的说了一通变量的作用域，c++中static class member和static class member functions的东西，可是面试官总是不满意，不停地问“还有吗……“，然后给个提示，我就继续balabala一痛，直到问地我再也无法balabala的时候才放手。

最后好像让我谈了谈自己做的项目，我就把四月份实验室做的哪个项目鼓吹了一通，然后谈了谈acm比赛，我说我只是了解，选拔赛被虐的很惨，对于进入校队基本不抱希望——暑假有时间实习（希望你给我个offer）。临结束的时候又问了一句“你对异步编程“有没有了解，我愣了，说不了解，只听说AJAX是异步Javascript和XML的意思。然后他问我还有没有什么问题，我就傻傻的问“我想知道这次面试中你对我的评价“。评价结果是“思维比较活跃，基础还算不错，但是接触的东西不够广泛“，大概如此。

整个面试过程约一个小时，头脑风暴，增加了自己的信心，也意识到了自己的差距。革命尚未成功，同志仍需努力，暑假，一定要好好把握。

• Relative Posts