百度网络维护面试经历

在经历了半个多月的漫长等待、翘首以盼的期待以后，今天终于有幸再次去百度大厦总部二面。此乃谓真应了百度的那句名言：众里寻他千百度，蓦然回首，那人却在灯火阑珊处——为了信念，执著追求、永不言弃！ 这次面试官是一位GG，很帅气，干练，自信中散发着内在的睿智——三张纸、两个人、一支笔，没带笔记本——这便是今天面试的主题。 在深刻分析和总结了一面失利的教训后，为了防止一面因听不清题目而要求面试官JJ重述题目的失误，再因这次面试官是一位GG，因此可以和GG坐得尽量靠近些，这样一来便于一次性清晰、准确、完整的理解题目的确切信息，另一方面也方便和面试官进行面对面充分的交流，避免在同一个地方跌倒两次——重蹈一面的覆辙。不过这次面试，我的这些担心看来似乎都是多余的：GG说话声音适量，很有底气，题意、需求、提问也都很清晰、简洁、明了，而且GG在提问的时候还特意重点强调了题意的重要信息，因此这次面试没有因听不清题目而要求面试官重述问题的情况，而且我在理解了GG表述的意思后也尽量迅捷作出反馈。总体上，这次面试感觉比较轻松，交流也很充分，GG待人很好，气氛也很Happy OK 介绍了这些面试的“前传”以后，下面就让我们直入今天面试的主题 第一道，给出两个集合A和B，其中集合A={name}，集合B={age、sex、scholarship、address、...}，要求：问题1、根据集合A中的name查询出集合B中对应的属性信息；问题2、根据集合B中的属性信息（单个属性，如age<20等），查询出集合A中对应的name 第二道，给出一个文件，里面包含两个字段{url、size}，即url为网址，size为对应网址访问的次数，要求：问题1、利用Linux Shell命令或自己设计算法，查询出url字符串中包含“baidu”子字符串对应的size字段值；问题2、根据问题1的查询结果，对其按照size由大到小的排列。（说明：url数据量很大，100亿级以上） 第三道，测试一部手机（手机是普通手机，除了系统软件外，可能已经安装了某些应用软件） 第四道，根据我简历上的项目经历，选出了其中的一个“Gloss搜索推荐系统”项目，让我介绍其架构以及我负责的工作 第五道，询问了是否比较熟悉的编程语言（C/C /C#）、VS2008以及对Linux Shell、Python认识等，主要是聊天交流方式，感觉很轻松 最后，是自由提问环节啦，问我有些什么问题，我主要提问了三个问题：框计算与云计算有哪些区别以及框计算目前的进展如何、百度面对团购网和移动互联网等新兴市场将有哪些战略方面的调整以及质量测试部门的工作和后期面试将要准备或学习些什么（这三个问题依次涉及到：1、框计算，关注百度的发展战略和核心技术创新；2、百度在面对不断变革和创新的互联网市场，将如何定位和战略调整；3、涉及到个人如果有幸三面或最终被录用，我将可能需要提前学习和准备哪些方面的知识储备） 对于第一道的问题1：因为最近我一直都负责处理实验室的海量文本数据（500G以上的log文本数据）进行数据挖掘分析，因此我直接给出了我正在用到的文本处理方法。 方法1、直接利用HashTable的{key、value}来做映射，即利用key记录集合A中的name属性，利用value记录集合B中的属性向量，然后直接key来查询value值 方法2、使用C 的容器类map进行一对多的映射（其实应该是multimap，当时忘了一对一与一对多的关系，在此更正一下） 方法3、自定义映射关系，大体思路是index vector模式，vector可以利用struct结构体做，index主要对name建立索引，提高查询效率这题的的核心解决思想，其实就是如何建立起一对多的映射关系，以及如何高效的进行查询匹配 对于第一道的问题2：一时我没有非常完整、高效的解决方案，但是我给面试官GG讲了我思考的大体思路： 第一种方案，集合A和集合B，逐行读取并按属性字段判断，如age<20则打印出name，否则直接读取下一行。但GG指出这样做的缺点是需要遍历整个文件，效率较低 第二种方案，于是提高效率，我借鉴了倒排索引的思想，提出把关键字段建立索引，进行“全文”搜索（其实就是集合A中的name），但是GG提出建立索引会占用额外存储空间，不是最优的方案 第三种方案，为了不占用额外存储空间，我再想借鉴数据库的Group Order方法，对集合B关键字段先分组然后排序，这样既不占用额外存储空间，也比方案一提高了效率，但GG说这不是最优方案，并给我提示说其实很简单，没我想的这么复杂，让我继续想想。。。 于是我继续想了一小会儿，在头脑中快速搜索我曾经还遇到过哪些能够既不占额外存储空间，又能提高效率的方法或借鉴思想。火花一冒，对呀，最近炒得很热的框计算、云计算，它们的设计思想或许可以一用，于是我接着想分布存储计算，对，利用分布式的思想来提高效率。可GG说似乎不行，这仍然不是解决问题2的最佳解决方案。不过还好的是，GG没有在这个问题上继续损杀我的脑细胞和自信心，而是循于转入下一道题目（GG不死抠面试者最薄弱的环节，而是适时直接转入下一环节，GG提问的技巧和哲学，给了面试者足够的自信和勇气，赞） 好啦，出于对我所崇拜的技术型创新公司——百度面试题目知识产权的保护以及对面试官GG（超牛级人物）劳动成果的尊重，我不再详细介绍本次面试的具体细节 O(∩_∩)O哈哈~，谨以上述第一道题的大体思考过程和分析解决问题的方法，以飨各位支持我、鼓励我的博友们 ^_^ 不过做事为了有始有终，不半途而废，下面我还是简单描述一下第2-5题我能想到的解决方法和细节，也希望大家能帮我提出更好更优化的方法 第二道，利用Linux Shell查询文件中的子字符串，需要用grep命令进行内容查询；分离显示文件的url和size两字段，似乎需要用到awk命令（没用过，不太熟悉），二者通过管道|传值。不过当时我没用Shell命令（不敢在GG高手面前Show，否则出了问题可不太好ban滴 呵呵 面试回来后，我在man sort查看详细参数后，利用Shell的解法请见：百度面试及总结4 ）于是我采用了自己设计算法解决的，分解成三步（1、字符匹配：字节流逐行读取，进行子字符串匹配KMP算法，查出所有包含“baidu”的url；2、打印满足1对应的size结果；3、根据2的结果，先把字段size字段值的字符型转换成整型，然后再用排序算法进行排序）当时说了三种排序算法：二分法、快排、堆排序 这里面还有一个小