合肥百度一面回来，攒RP，写面试经过，期待二面。

jinwp2007

昨晚12点，刚睡着，接到了百度一面通知，当时糊里糊涂的没听清就挂了，等自己清醒过来，发现不对。自己不知道在什么地方面试……晕，努力回忆，还是想不起来，只好发个短信去问，刚发完短信，电话就打进来的，然后和她解释，她很不耐烦，说你是哪个学生，当时我想这下给她惹毛了，就歇菜了。 不过她还是和我说了。（**大酒店***，***）当时在想怎么还搞个*分，不过没多想。 下午到了酒店，一看根本就没看到前台接待的，连个标语都没有，到是看了几个学生在大厅，然后上楼，一看门是关的，不好意思敲门，下来问宾馆前台，说，有这么回事，说是时间到了自己上去。看了下面几个哥们，听了一下，他们在讨论问题，感觉百度挺难的，他们说，网页搜索部门--核心技术研发是最难进的。我不知道我面的是什么，最后才知道我面的就是这个。有点晕 上楼，到了***门口，看到了传说中的牛人--科大本科生，一问，他说他也是同一时间，我想这下坏了，一面二，我不擅长这个，像这种情况我一般只有听的份。这样就听天由命吧。 那扇门终于打开了，出来了一位，然后问下一个是谁，然后我们俩都说是，面试GG说我看一下，然后出来对我说，我是下一个的，牛人是我后面的，我一想，那不就说明我有可能面积1小时，来了就安心面吧。 进去了然后我就开始寒喧了一下，面试GG叫我坐，我怕这种沉默，我就先主动开口说话了，我来自我介绍一下吧，然后balabala给我准备的自我绍了一下，中间还忘词了，小尴尬一下，然后面试GG笑笑说，我们开始吧。 第一个问题： 堆和栈的区别？ 这个很熟，balabala，不过感觉总结的时候，条理不太清晰，期间说到new和malloc，面试GG等我说完，叫我说一下new和malloc之间的区别。我答：new 是运算符，malloc是函数,balabala……然后他又接着问，什么时候用栈，什么时候用堆，晕，没想过这个问题，我说知道要分配多大空间的时候用栈，不知的情况用堆，感觉心跳加快，出冷汗，太细了，再问下去我不知道他还会问什么。不过还好，他说这个问题就到这。 第二个问题：两个排序的数组，怎么求交集。 这个会，我说两个数组同时遍历，相等的时候输出，小的下标++，他说恩，那你说说这个时间复杂度多少，这个我知道O（M+N），他接着问，现在这两个数组大小相差很大，应该怎么去改进算法，我想了一下，说用二分。他说恩这个可以，他又问，这样的时间复杂度是多少， 我答：O（Mlog2N), 他接着问，在什么情况下，这种优化才有明显效果，现在假如我第一个数组的大小为10万个int ，那第二个多大才会有效果。晕，他给我一支笔，说你想想，我晕，那就算吧，第一种O(M+N)， 第二种是O（Mlog2N)算了一下，当N>16M的时候才有效果，Mlog2(100K) = M*(10+log2(100))=17M,17M<M+N,N>16M,期间还犯了个低级错误，把log2(100K) = log2 (1000)*log2(100),算了大概是60多，那哥们很差异，我才想到就改成上面的，他又问了，在实际中，我们这种算法在N》90M的时候才会有效果，问我为什么？我又晕，我说是不是因为第一种方法有可能在很早就结束了，他说我们做很多测试，这个是平均时间复杂度，我无语了，接着想，我说是不是因为二分查找出现太多找不到情况，说出口我就知道错了，二分查找最坏的情况就是log2N+1，他说不是，沉默了一会，我估计我一时半会想不出来，我就说：这个问题我估计短时间想不出来，那哥们给提示了，问我二维数组的二种遍历方式，按行和按列怎么实现，我说这个数据结构书上有讲，二维数组有两种存储方式，一种是按行，一种是按列，他说有按列存储的吗？怎么个存储方法，当时我没敢说，我说数据结构书上是这样说的。他没接着问这个，就问我按行遍历快，还是按列遍历快，我说按行，他说为什么，我说数组是顺序存储的，按列要计算地址，CPU寻址是需要时间的，这时我想到我上面题目的原因了。原来二分查找寻址的时候有开销。他又接着问，第一个数组和第二数组倍娄相差不是很大的时候怎么优化，假如说N=10M，我晕，真绝，我说应该给大的分块，他又问怎么个分块法，我先给我知道的东西说了一下，在数据结构中，分块查找一般是按照数组大小的开平方来决定的，不过对于我们这个问题，应该考虑到实际情况，想了一会，我说应该按它们之间倍数来分块，他说恩，那我们这个问题就到这。我晕， 第三个问题：智力题：100个球，我和你来拿，每人只能拿1-5之间的数目的球，你先拿，谁最后先拿完，谁就赢。歇菜了，当时头一大，没有思路，我还是说我想想，想了30秒，我说出自己的方案，我说最后让他给我剩5个以内的球，我就能赢，所以在95球让他最后拿完，于是说，我先拿5个，剩下的，他拿1个我就拿他的对5的补，结果应该有可能会赢，面试GG分析了一下不行，叫我再想，受不了，想了2-3分钟，期间也说了一二个想法，都给他否决了，然后我说，能不能给点提示，他说，你想赢，最后一个回合，你要给他留几个球，我想，说6个，我顿时感觉自己智障，只想自己一下给最后拿完，没想到给人下套，于是我告诉他我的答案，第一次我拿4个，然后你拿多少，我就拿你的个数对6的补，（每次都给你下套，赵大叔应该来拐他几回）。他说：恩OK，这个问题就到这。 第四个问题：一个int数组，问怎么找到这个数组中重复超过一半的数？ 这个暑假在崇新通信做过，我说可以用STL吗，他说可以，我说那很简单，给出一个map<int,int>对里面的数组遍历一次，然后遍历一次map,只要map的second大于数组的一半，输出他的first域。他说你这个复杂度多少，我晕又是这个，我说O（2N），他说你这样的话，要用2M的空间开销，你能不能降低开销，我晕了，我想我能不能对数组排序，他说可以，我说那也很好做，我先排序，然后来统计一下里面重复的个数，这样就能做到，他说这是可行的，你要知道当N很大的时候，你的排序要多少时间复杂度，我说最少也是O(Nlog2N)，他说，所以这方法不可行，还有没有其它方法，我晕，左思右想，找不到合适的，又用期待眼光看着他，说能不能给点提示（实在脸皮厚），不过可惜的是，他没看我一眼，对着电脑说你想这样的数在数组里面是个什么数，我说是众数，他说这是肯定的，他说应该也是中位数，我说当N很大M也不小，你这样假设不太对，那哥们没说什么，我猛然想到，一次不行，多几次应该差不多，我说了我的想法，我用几次二分，多找几回，如果，出现的数多，就拿这个数来做，哥们笑笑说，这个问题就到这。 下面就对着我简历问我的项目，第一个项目，这个我在行，我就和他balabala，吹，这个昨天在联发科技吹过一次，今天特熟，思路也还好，然后和google street, city8比较了一下，说我们这个怎么怎么好，哥们听得很认真，然后又发难了： 你在这个项目中做了哪些工作？ 这个我昨天也吹了，今天吹得更卖力。期间还问了不少小问题，我是吹得天花乱坠……呵呵，吹6B看来还是很重要的，哥们最后说，我没有什么要问的了，你有什么想问我的， 我问了几个问题： 1、baidu和google在搜索英文文献的时候，baidu的搜索不如google。这方面的原因是什么？ 2、baidu有没有想做一个类似于google street的东西，（因为我项目就是在google street上有改进，想套近乎的）。 3、在交通查询方面，百度可不可以做一个，像火车时刻查询系统，这样比较方便，当然除了火车的，还有汽车的，飞机都可以做。 4、老一套，问如果我幸能进贵公司，我应该做什么方面的工作？ 5、你们写程序用什么IDE（这个回答，说我们不用IDE，然后他balabala.晕，太强……） 面试GG都做了回答，最后说那今天就到这，起身，问了最后一个问题，有点唐突：我能知道您贵姓吗，他说姓*。握手，告别， 开门的时候，我想问问我有没有二面机会当然不能直说，婉转的表达意思，结果他打了一套太极拳，等于白问，就再握手，走人。 下楼感觉今天发挥还好，题目有点难，现在还没有二面的消息，估计黄了。唉，大公司就是不一样。