找工作笔试面试那些事儿(15)---互联网公司面试的零零种种和多家经验

作者：寒小阳
时间：2013年9月。
出处：http://blog.csdn.net/han_xiaoyang/article/details/11400719。
声明：版权所有，转载请注明出处，谢谢。

前面从宏观的角度，根据师兄师姐口口相传的经验和自己的面试经历，写了点面试应该注意的点。这里针对，互联网公司，总结总结面试注意的点，里面的一部分内容出自一些优秀的大牛口中或笔下，一部分是自己的客观感受，也许会有挺多地方说的不对，望大家指出，谢谢。

1 互联网面试100分理论篇

之前看到过一个所谓的互联网面试100分理论：50分的算法和C语言、15分的项目分、15分的知识面和扯淡分、10分的开发语言细节分和5分的其他。也看过一些反驳这个说法的文章，且不说其对错吧，我把它总结了总结，结合自己的经验想法写在下面。大家往下看看想想，或许某一部分能对你有帮助。

1）50分的算法和C/C++语言题：

现在的校园招聘笔试和面试，不分公司和部门都是一窝蜂的考这两项。大部分应届生，没有履历，没有工作对口方向项目知识能力的积累，用人单位只能考察基础知识和思考分析完成程序的能力了，而最无奈的是很多时候不同的职位也就同一套题，甚至有不少想做前端的同学去忍受C指针和算法的折磨。但是假如你这两个比较好，那么你就有50%以上的机会进入心仪的互联网公司，那如果不好呢？
假如您的C语言不好，问题不大，翻出谭浩强的那个工科生必修的C教材，再熟悉熟悉。（这里我也推荐一下我的找工作笔试面试那些事儿(1)-(8)，相信也能解决不少问题） 。
假如您的算法不好，如果还有一段时间，也能补补。从去年我和同学们笔试和面试的经历看来，很多互联网公司（之前面过的像人人网、搜狗、百度、美团、大众点评网、微软等等都是）笔试面试的算法题都能找到原题或者母题。也许在很多acm大牛看来，看某典、某美和剑指offer，100题非常不屑，但对于算法基础一般般或者不怎么懂算法的人而言，还是会有很大帮助的。

最基本的下面的东西得会吧：
排序：知道各种排序的时间和复杂度，能写出快排，堆排以及计数排序的代码且知道什么时候用哪种即可。
链表：知道构建动态链表，删除节点，翻转链表，两两翻转，求环节点，求两链表交点等。
字符串：知道高效翻转，回文，如果还能完整的写出KMP查找就基本完美。有时间再了解了解字典树，后缀树什么的更好。
树：知道二叉树的三种递归遍历，非递归遍历，查找，知道两种遍历求第三种，再深一点，知道如何分层遍历，如何求两节点距离。
其它：队列、栈、哈希表的特性和应用场合。

2）15分的项目分：

据说1足够好，编程能力足够好的话，这部分基本也不会丢掉什么分。多少总归有一两个自己真实参与过的项目吧，好好讲清楚里面用到的知识技能，体现自己在遇到问题的时候分析问题和解决问题的能力就行了。

3）15分的知识面和扯淡分：

这方面确实和知识面广度深度平时积累有关系，根据面试官和应聘职位可能不同，也挺难事先准备的，有时候面试官是根据之前你的项目问些相关的知识。像PageRank，搜索引擎倒正排索引，数据库优化，web性能优化，浏览器渲染，web安全，爬虫，设计模式，软件架构，推荐系统，加密算法，服务器推等等都有可能被问到。本人也很菜，这种东西问到也不能答得太好，好在这部分15分的话，也影响不大，大部分人都在中间得分区段。

4）10分的开发语言细节分：

类似C的指针函数、函数指针，高级语言的值类型，引用类型，值传参和引用传参，托管语言的GC等等一些细节问题。来考察一个人对语言的掌握程度以及学习态度。

5）5分的其他：

主要是沟通能力，印象，有些公司会有英语有要求。

2.准备技术面试方法篇

看过这样一篇准备技术面试的文章，里面提到很多人在准备的时候，看资料都是看完问题之后直接翻答案。作者强烈建议不要这么做，并提供以下参考思路：

1尝试用自己的方法来解决这个问题。

全凭自己的方法。有些问题确实很难，不过没关系。在解决了问题之后一定要考虑下时间和空间复杂度。推敲一下是否能够通过空间换时间或者时间换空间的方法来优化算法。

2在纸上写下实现算法的代码。

此前你一直在计算机写代码，特别依赖语法高亮、代码自动填补和编译器这些东西。但是在面试的时候是没有这些东西的，为了模仿这样的情况请一定在纸上写代码。

3把你的代码原封不动的敲到计算机上。

你肯定发现自己犯了不少的错。把这些错误都列在一张表里面吧，在面试的时候你就会警惕这些错误了。

4做个模拟面试。

CareerCup提供一些模拟面试的服务，或者你可以找个朋友让他给你提一些面试的问题。虽然你的朋友不是专业面试官，但也能帮你完成代码或者算法的面试。

很多面试官不会直接问你一个算法(平衡二叉树或者其他复杂的算法)是如何实现的，说实话这些算法面试官自己可能都忘记了。但是一般面试官需要你记住一些基本的算法，下面是一个必须知道的知识的列表：

当然这个表格并不包含一切知识点的。面试问题可能超出这个范围。这只是一个必须知道的列表。对于表格中每一项你都得理解并且知道如何实现和使用它们，以及它们的时间空间复杂度。

好好练习这些数据结构和算法的实现。在面试的时候你可能会被问到如何实现他们，或者对算法进行改进。不论什么情况，你准备的越充分越好咯。

3.算法方法技巧篇

其实这里弄这么一篇真是心里虚的很，谁都知道木有一夜两夜提高算法的秘籍（不然笔试面试还考察这个做什么），算法这玩意靠得是一点一滴的积累和思维的磨练。一些所谓的方法和技巧（大部分是《编程之美》《代码之美》《编程珠玑》《剑指offer》之类的快餐书籍里面提炼出来的），都只是给面试来只强心针喂一口大补丸，主要目的是给自己壮个胆，让自己看着自信一点。不过即使是这样，总结类的东西看看也无妨。说不定在准备过一段时间的算法，做过一些算法题之后回过头看看下面的总结，感觉还能有那么点把丝丝缕缕的算法思路串起来的赶脚~~（非常感谢整理下面方法的原作者童鞋，我看过后整理加了一些自己的东西）。

（1） 时间复杂度要求

根据面试的经验，大部分题都是对时间复杂度有所要求的，尤其是现在存储空间越来越大，存储设备越来越便宜的大环境下，对“速度“的要求却是越来越高。一般情况下就直接上时空原理咯，用空间来换时间。Hash，大数组，一些辅助性的空间，都是首选。Hash和大数组在很多情况下固然好用，不过，通常这不会是面试官想听的最终解法，他们紧接着十有八九是会说“如果只有xxxx空间呢？”。说此类方法只是为自己争取更多的时间，并且体现思考的完整性（也就是，拖延时间并装B用。。。）

例1.1：求一个char（8bit）中，二进制1的个数，越快越好。--《编程之美》

例1.2：有一个整数数组A[N]，让你不用除法，求另一个数组B[N]，其中B[i]=A[0]*A[1]...*A[N-1]/A[i]，期望复杂度是O(N)。

（2） 空间复杂度要求

一般这里指的都是在大数据分析的逻辑下，空间受限的问题。方法呢，大部分情况下就是压缩咯。bit-map(位图)是一个很好的方法，用一个bit（或几个）取代更大的int类型，最常见的位图是1bit取代1int，其实，很多时候，1bit可以取代更大的空间，这完全取决于你需要保留的信息。话说网上有一篇很有名的《十道海量数据处理面试题与十个方法大总结》，大家可以翻来看看，算是突击一下吧 -_-||

例2.1：有一个很大的文件，存放一堆7位的电话号码，号码无重复，请用最小的内存消耗，将其排序。--《编程珠玑》

例2.2：给10MB的内存，给一个4百万整数的文件，找一个不在文件中的整数。--（传说中的Google面试题）

（3） 空间复杂度延伸---基于文件处理

上面（2）中所说的空间受限的问题，其实大部分情况下都是在和文件打交道（看过《十道海量数据处理面试题与十个方法大总结》之后你更会这么发现）。基于文件的处理，基本都是寻找，或者排序，最最核心的，就是减少文件读取的次数。除了位图法，还可以考虑哨兵，典型的案例就是外排中，增加单个文件大小的方法。

例3.1：给定一个包含4300000000个32位整数的顺序文件，找到一个至少出现两次的整数。--（传说中的微软面试题，我曾经遇到过类似的）

例3.2：有一个文件，有很多很多的整数（也许有100亿），寻找其中最大的K个。--《编程之美》

（4）分治法

关于分治，我的经验是，你在面试的时候最好经常问问自己，这道题能不能用分治解决。动态规划这东西，大部分人都掌握不了，而且在面试的时候比较沉重，不好描述，不好书写，而分治却刚刚好，美丽，快捷，易书写，是面试官杀人越货的首选武器。分治的用法实在是太多了，几乎是无所不在，二分，快排，种群计数，各个唯美无比。。。

例4.1：给你一个长度为N的整数数组，请找出最大的子数组和。--《编程之美》

例4.2：求一个int（32bit）中，二进制1的个数。--《代码之美》（注，不是编程之美是另一本书，有一章叫做种群计数，这是一种很酷的分治）

（5）排序和查找

面试过程中，排序出现的频度实在是高的无法统计了，很重要的一点，排序的东西才能用二分，二分速度快啊！。二分是如此好用，以至于我们总是想着排序。查找和排序总是紧密联系的，当然，仅仅是为了查找，做一次排序，你需要衡量一下代价。。。

例5.1：有一个论坛，有ID发帖数目超过总数的一半，给你论坛所有帖子的ID列表，请你找到这个水王。--《编程之美》

例5.2：给一组一维的空间[1,6][2,4]...，请求是否有区间重叠。--《编程之美》

（6）减小问题规模

很多时候，题目看上去很吓人，仔细分析一下，就可以刨去其中大部分的无关内容，获得真正的出题意图，这一点很重要。另外有些时候，题目会在空间上做出一些限制，这个时候，你可以考虑动态的对数据规模进行缩减，比如用减法或除法抵消，用异或抵消，等等。。。

例6.1：给一个整数N，求它的阶乘N!，有几个0结尾。--《编程之美》

例6.2：盒子里有三种颜色的球，红黄蓝，可以用任意两个不同颜色的球，换两个另外颜色的球，比如1红+1黄=2蓝。现在盒子里面有171个红球，172个黄球，173个蓝球，问，能不能经过若干次交换，最终变成同一颜色的球。--TopLanguage

例6.3：有一组数，除了一个数只有1个，其他都是两两成对的，请找出那一个不成对的数。另，如果不成对的数有两个，该如何是好。

（7）常量法

一个典型的速餐方法。比如说其中比较有名的一个例子是，一组数，在某些情况下，它们的和一定，通过这个常量，进行反推，可快速搞定一些问题。。。（但是这个地方，提个小小的醒，和是定值，但是和可能很大，超出我们可以定义的数据范围，肿么办呢？恩，考虑考虑异或什么的吧）

例7.1：有一副扑克牌（你可以用任意方式来表示），被抽去一张，请快速找出这抽去的一张是什么？--- 传说中的微软面试题

（8）编码

编码还真是个好东西，可以将复杂的问题抽象化。比如，对一个序列进行编码，可以直接映射到数组脚标上，大大提高访问速度。。。

例8.1：有1000瓶超级名贵的葡萄酒，其中有1瓶有毒。这种毒药很厉害，哪怕被稀释了1000000倍还是可以毒死人的。但这个毒药一定时间后才会毒发，时长是1个月。为了不浪费这些葡萄酒，有1000个壮士决定花5周的时间将毒酒找出，他们只希望最多有10个人牺牲，你需要如何安排才能实现。--TopLanguage

（9）关于数据结构

大部分面试时候，用到的数据结构都比较简单，大概数组堆栈链表就可以搞定了，顶多来个二叉树，因为简单变化多，面试官好把握。其他数据结果，同样也很重要。AVL，B树那样的可能比较复杂，但是偶尔真的会被问到，还是留心关注关注比较好。。。

例9.1：给你一个单链表的头指针，在不使用大量附加数据或修改原有数据的前提下，检查一个单链表是否有环。--- 传说中的微软面试题

例9.2：给你两个链表，如何判断其是否相交，如果相交，如何找到两个链表的第一个交点。--《编程之美》

例9.3：只给你一个指向链表中某元素的指针，请删除该元素。--《编程之美》

例9.4：写堆排序的算法eg6.5：判断一棵二叉树T中，是否包含另一颗二叉树P的结构。--微软面试题，活生生

（10）概率题

刚开始面试的时候一直不理解为什么概率题会被采纳为面试题，一直觉得这不就是数学吗，和编程算法关联不大啊。后来发现概率是一种很多情形下违背直觉的东西，容易让人陷入迷茫，而面试官会希望见到能犀利分析问题而不迷失的你。说来尴尬，曾经在面试某社交互联网公司的时候，被一道简单的概率题绕进去了，调戏的脸面全无，至今想起，仍然是汗流满面。所以，为了人身安全，复习一下概率的基本知识吧。。。

例10.1：有一个长度为N的链表，N未知。希望你只遍历一次链表，就从链表中等概率的挑出K个数。--TopLanguage

（11）进一步优化

时常有一些同学觉得自己的算法能完成所给的任务，而且程序也都写对了，但是面试莫名其妙地就挂掉了。其实，大部分情况下，可能是面试官觉得你的程序能用，但是还不够优秀。面试官会希望你优化一下。优化的方法有很多，就基本的思路就是，考虑一下到底哪里出现了浪费。常见的浪费有两种，一种是回归到时间和空间的问题，你用了比较沉重的运算，比如除法、取模等，你可能需要为计算来加速。另外有时候，你为了得到所需的结果附加计算了很多不需要的东西，这样的算法太粗线条，比如只需要符号，你却计算了总数等等。。。

例11.1：求两个数的最大公约数。--《编程之美》eg5.2：有一个整数数组A[N]，求其中连续N-1个数的最大乘积。--《编程之美》

例11.2：估计一下快速排序的比较次数。--《代码之美》

（12）总结

上面这些所谓的总结的小东西，大牛们看看一笑而过就好了。总的来说，面试过程中出到的算法，并不为了考察算法本身，大部分情况下，面试官看重的是分析问题解决问题的能力，还有交流沟通能力，以及在面试官提示下能迅速找到突破口，扭转错误方向的能力，而不是最终的题结果本身。很多人举例子说，算法在面试中的地位，好比是托福在出国中的地位一样，必须但不是最重要的，它只是考量的各个方面的一部分，不一定就决定生死。所以，有就让它更好点，没有就稍微补充点，足矣。