2016年10月Android岗校招笔试面试总结

之前写了两篇我在9月份的Android岗校招面试经历：2016年9月Android岗面试经历-网易/腾讯 和 2016年9月份Android岗面试经历-百度 。
后来有的朋友在下面留言，说Android岗为什么会问C++的内容呢？大家别慌，因为我的简历把我的C++编码经历提了一下，而C++这门语言，众所周知，挺难的，所以那两位面试官才会问一些C++的问题。不过我认为掌握C++还是很必要的，很多企业笔试都会或多或少考一些C++的问题。也有朋友留言，问我找到工作没。这就很尴尬了，作为一个技术弱，我并没有找到工作。现在也放弃找工作了。但是这个暑假我为校招准备了很多，<strong>今天把2016年校招中积攒的一些经验写在这里，希望可以为准备明年校招的小伙伴提供一点参考。</strong>

算法、数据结构

算法与数据结构是最重要的基础课，要花很多工夫在这上面。

• 数组、栈、队列、链表。常见操作时间复杂度。尤其对于链表，要能把常见操作的代码在白纸上写出来，各种插入、删除、反转等等。两个栈实现一个队列。还有判断链表成环(快慢指针)、判断链表交叉等题目，都是老套路了。

• 字符串。 KMP算法，通过π数组得到next数组，KMP算法与动态规划的关系。其实这一块除了笔试的选择题会考到，算法题也喜欢围绕字符串出，比如实现strcpy()之类的，多刷题会好很多。

• 二叉树。常见二叉树的性质，比如度为0的结点和度为2的结点的数量关系。如何将森林与二叉树互相转换。算法题这一块，前序遍历、中序遍历、后序遍历、层次遍历，迭代和递归版本的实现，要能够写出来。Leetcode上Tree标签下好多这样的题目。

• Binary Search Tree，常见操作的时间复杂度。最好知道如何删除一个结点、如何插入一个结点。BST退化成链表是怎么回事。相关的代码需要能够写出来。 红黑树，要知道相关的性质，代码一般不要求写出来，而且要知道红黑树在JDK中的应用。B树、B+树、B*树，要知道相关性质和应用场景，我经常在笔试题中遇到。哈夫曼树，建树过程，计算加权路径长度。

• 堆，常见操作的复杂度（放入一个元素的复杂度、堆排序的复杂度等等）。最好知道如何移除堆的一个结点，知道shiftdown()操作。知道堆逻辑上是一个完全二叉树，物理实现是一个数组。

• 图。我很少见考过，见过考结点与边的关系。从未见过考Dijkstra算法、prim算法等图算法，为了保险起见这些算法也看一看吧。不过我认为拓扑排序应该看一看，迭代实现与递归实现都看一看。

• 排序，笔试考察的重灾区。冒泡排序、插入排序、选择排序、希尔排序、快速排序、归并排序、堆排序、桶排序、基数排序。不是我危言耸听，不是我贪大求全，不要抱有侥幸心理。这9个排序，都会考，而且我全部遇到了！当初我把其他的排序弄得滚瓜烂熟，唯独认为基数排序应该不会考，结果有一家公司的笔试就考到了基数排序，而且是多选题。。。。

  • 首先，一般情况下的时间复杂度是最基本的，然后，要把最坏情况和最坏情况下的时间复杂度搞清楚。然后，搞清楚空间复杂度，这个要好记一些。
  • 要搞清楚每种排序的具体操作。冒泡是不断地把大泡泡上浮，插入排序是不断地交换（而非插入），交换到合适的位置，希尔排序是一种缩小增量排序等等。
  • 要搞清楚什么叫排序的稳定性，就是相同大小的元素在排序前后的相对位置不变。如果我们要对一组数据按照多种关键码进行排序，排序的稳定性就会有影响了。其实如果我们要记忆各种排序的稳定性，不需要死记硬背，注意到基本操作是相邻交换的都是稳定排序就可以了。
  • 要知道各种排序适用的场景。比如插入排序适用于待排数组基本有序的情况。想要取出数组的最大的N个数，适合用堆排序等等。
  • 另外，关于这些排序，我认为快速排序、归并排序、插入排序、冒泡排序，至少要能把代码写出来，至少我真实见过要写快排和merge sort。

• 查找。对于一个有序的序列，如何进行二分查找。迭代实现和递归实现，都要能很快地能在白纸上写出来。关于hash，这一部分，要明确地知道各种冲突解决策略，知道探查函数。鹅厂有一道笔试大题就是关于hash的，当时这道题给定原始数据和填充因子，要求设计出hash函数并计算相关的查找长度。

• 贪心算法、动态规划。写在文章里只是几个字，实际上需要大量的刷题练习。比如今年网易的笔试题，一道贪心、一道dp，都不是easy题，需要一点思考。所以，还是需要大量地刷题。

• 大数据处理。似乎鹅厂考的比较多。推荐一个不错的博客：十道海量数据处理面试题与十个方法大总结

操作系统、网络、数据库

• 进程和线程区别。死锁的必要条件。进程调度算法。缺页调度算法。这些问题都比较偏书本一些，被考到的不多。其实可以跟Linux结合起来问，比如Linux中进程的状态，Linux中进程和线程的关系，Linux下IPC的几种方式等等。

• HTTP的请求报头和响应报头格式。HTTP响应的常见状态码。

• HTTPS的作用，使用的端口。连接的建立过程。

• POST提交数据的四种方式。urlencoded、表单、xml、json。

• TCP协议，流量控制机制、拥塞的处理。TCP连接的建立与释放过程，为什么需要3次握手，2次握手为什么不行？客户端和服务端会经历什么状态，这些状态代表什么意思。释放过程中TIME-WAIT状态的意义是什么？

• ICMP报文的类型与作用，ping和traceroute的原理。

• 数据库也会考到，但面试基本不问，主要是在笔试题中出现。我在今年校招笔试种遇到过的题目有：对第二范式、第三范式、BC范式的考察，对3种并发错误（读脏数据、不可重复读、幻象）的考察，对事务的四个特性ACID的考察，对count(*)、count(1)的区别的考察，对主键外键约束的考察，对用户权限分配的SQL语句语法的考察等。

Java基础与Java并发

推荐看这3本书：Effective Java、深入理解Java虚拟机、Java并发编程实战。如果只是为了面试准备，不必一页一页地看，根据自己的需要快速补充一下欠缺知识点。

• String、StringBuilder、StringBuffer的作用和区别，最好看过它们的源码，明白效率差异的原因，StringBuffer为什么是线程安全的，可以引申来的问题很多，要多多思考。还有普通的字符串拼接，如

String str="str"+"ing";

实际上发生了什么，这个拼接的效率如何呢。
以下代码的执行结果如果呢：

String a1="abc";
String a2="abc";
System.out.println(a1==a2);

上述代码换成Integer、Double也是一样吗？

• Object类的几个方法。hash()这个函数的作用是啥，equal()和==的区别是什么？equal()的函数重写的时候为什么要重写hash()函数呢，clone()方法能用来干什么呢？

• Java的常见容器类。ArrayList、Vector、HashMap、LinkedHashMap、TreeMap、TreeSet等等，要知道内部实现。尤其是HashMap，几乎被考烂了。

• 一个Java文件中构造块和静态块的执行顺序，什么时候会执行呢？会执行几次？

• 一个Java类的类加载过程。加载、验证、准备、解析、初始化，当然不是把这几个词背下来就行了，要把其中的过程理解清楚。

• Java的gc算法，Mark&Sweep算法、复制算法、标记-整理算法。了解CMS收集器。了解Android中什么时候会触发gc。gc对性能的影响。

• Java运行时的数据区：方法区、堆、虚拟机栈、程序计数器、本地方法栈。了解每个区的作用，是否是线程隔离的。

• volatile关键字的作用。synchronized关键字的作用。内存可见性的意思。

• 同步容器与并发容器的作用。它们之间的性能差异。

• ThreadLocal的作用与实现原理。

• 线程池的使用。如何实现一个线程池？（某大厂笔试题）

• 单例模式的几种实现（双重检查加锁、内部类）。考虑一下并发与重排序对单例模式的影响。

Android知识

推荐看Android开发艺术探索、Android源码设计模式，其实能把这两本书吃透就已经不错了。

• Activity的生命周期。不仅仅是把各个回调地顺序记下来，而且要知道每个回调的意义。onStart()调用的时候界面会不会显示出来？onPause()为什么不宜执行耗时操作？从活动A跳转到一个使用非透明主题的活动B，执行回调的顺序是什么？

• Activity的四种启动模式。要了解任务栈的概念。会用dumpsys activity查看任务栈的情况。

• Service的两种启动方式。两种启动方式对生命周期的影响。常见的Service保活方式。Service能否执行耗时活动。IntentService的作用。onStartCommand()返回值的意义等等。

• Fragment的生命周期。生命周期比较复杂，要背下来，而且要跟Activity放在一起比较。如何保存Fragment的状态。

• BroadcastReceiver的两种注册方式。系统广播与自定义广播。广播接收器中能否执行耗时任务。

• Handler的作用。Handler、Looper、消息队列之间的关系。

• AsyncTask的内部实现。AsyncTask的使用的注意事项及其缺点。

• View的触摸事件分发机制。一个事件序列是如何被拦截并被消费的。

• View的绘制过程。最好自己自定义一个控件，感受一下绘制流程。

• 一个apk的打包过程和安装过程。

• 实现一个图片加载框架要注意到的点。

• 常见设计模式。（单例模式、Builder模式、观察者模式、工厂模式、责任链模式、外观模式、订阅者模式、装饰者模式、适配器模式）其中有些是要求能够写出代码的。

C/C++/编程基础

这一块是基础知识，即便是Android岗也会考一些。推荐看深入理解计算机系统、C++ Primer 5th。这一块笔试没有考太深，暂时想起来的就这些了。

• 对于C，我们至少要知道基本关键字、基本语法，尤其要知道数组、指针的关系。
• 经常考一个结构体的size是多大，我们需要知道内存对齐的一些知识。还需要知道联合体是什么玩意。考一个类的size是多大，我们需要知道虚函数表指针这个东西。
• 会考到大小端的字节序问题，我们要知道x86架构上和网络上的字节顺序，哪边大头哪边小头。
• 经常遇到考const的转换，问会不会报错。(鹅厂的笔试题)
• C++经常问到虚函数，最好知道虚函数的实现机制。
• 一个源程序从编译到执行的基本过程：预处理、编译、汇编、链接、加载执行。
• 一个int型的整数在内存中如何表示，尤其它是负数的时候？跟大小端结合起来问更爽。
• 经常见过考这样类型的题：

char *str="abc";
cout<<sizeof(str)<<endl;

• 太多可以考的知识点，暂时就写这么多。

说一下我的建议

现在回想起来，两个方面最重要：写算法题、项目实战经验。上面写得那些知识点，很多都可以通过突击补一补，在牛客网上刷一刷，那些容易补、容易“扯淡”的都不是大问题。

算法题最少提前3-6个月开始刷，最好能刷完Leetcode上的题目，不管什么难度的题都刷一刷。刷完一题可以总结一下经验，把套路总结出来，而且有些经典的题目要反复刷，提高熟练度，每一题的时间尽可能控制住，想一想，如果你平时刷一道题都需要半个小时，那笔试面试的时候怎么办？所以每道题尽可能20分钟以内搞定。刷Leetcode可以根据标签来刷题，这样不至于像没头苍蝇一样。

至于项目经验，其实就是要平时多写代码，多做出一些个人的作品来，最后可以在github上传一些自己的项目，应当会有加分。