2015届校园招聘笔试/面试 基础知识点 总结

写在前面：

9月底收到创新工场offer，本早就该写一篇博客来总结在校招季遇到到的问题的，但近期比較懈怠直到如今才整理出这篇博客。

校招感受最深的是，提前做好准备真的非常重要。

此次校招，由于准备不足（9月份才从外地回校），多次折戟二面。面试是实力与运气的综合，你实力越强，运气成分越少。

此为个人在笔试面试中遇到的部分总结，希望能帮到仍在校招中的同学。

操作系统部分

进程间通信：

1、管道是UNIX系统IPC的最古老的形式，而且全部UNIX系统都提供此种通信机制。

可是其有局限性：

①它们是半双工的（即数据仅仅能在一个方向上流动）

②它们仅仅能在具有公共祖先的进程之间使用。（通常，一个管道由一个进程创建。然后该进程调用fork。此后父子进程之间就可应用该管道）

虽然有这两种局限性。半双工管道仍是最经常使用的IPC形式。

 

2、FIFO有时被称为命名管道。管道仅仅能由相关进程使用。可是，通过FIFO。不相关进程也能交换数据。FIFO的路径名存在于文件系统中。一般的文件I/O函数都可用于FIFO。

 

FIFO的用途：用于客户进程–server进程应用程序中

FIFO的真正优势在于：server能够是一个长期执行的进程（比如守护进程），并且与其客户能够无亲缘关系。

作为server的守护进程以某个众所周知的路径名创建一个FIFO，并打开该FIFO来读。

此后某个时刻启动的客户打开该FIFO来写，并将其请求通过该FIFO发送出去。

（客户到server）

每一个客户在启动时创建自己的FIFO。所用的路径名含有自己的进程ID。

每一个客户把自己的请求写入server的众所周知的FIFO中，该请求含有客户的进程ID以及一个请求文件路径名，server依据客户进程ID能够知道客户FIFO的路径名。

 

3、消息队列是消息的链表，存放在内核中并由消息队列标识符标识。

在某个进程往一个队列写入消息之前，并不须要另外某个进程在该队列上等待消息的到达。这跟管道和FIFO是相反的，对后两者来说，除非读出者已存在，否则先有写入者是没有意义的。

 

管道和FIFO都是随进程持续的。XSI IPC(消息队列、信号量、共享内存)都是随内核持续的。

当一个管道或FIFO的最后一次关闭发生时，仍在该管道或FIFO上的数据将被丢弃。消息队列，除非内核自举或显式删除，否则其一直存在。

 

4、信号是软件中断。它同意进程中断其它进程。

信号是异步处理事件的经典实例。

产生信号的事件对进程而言是随机出现的。进程不能简单地測试一个变量(比如errno)来判别是否出现了一个信号，而是必须告诉内核“在此信号出现时，请运行下列操作”。

一个信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件。每种信号类型都相应于某种系统事件。低层的硬件异常是由内核异常处理程序处理的，正常情况下对用户进程而言是不可见的。

信号提供了一种机制。通知用户进程发生了这些异常（由内核发送给用户进程）。假设一个进程试图除以0。那么内核就发给它一个SIGFPE信号。

 

发送信号：

内核通过更新目的进程上下文的某个状态，发送(递送)一个信号给目的进程。

发送信号能够有例如以下两个原因：

A、内核检測到一个系统事件，比方被零除错误或子进程终止。

B、一个进程调用了kill函数，显示地要求内核发送一个信号给目的进程。一个进程能够发送信号给它自己。

 

5、信号量(semaphore)是一个计数器。用于多进程对共享数据的訪问。

为了获得共享资源，进程须要运行下列操作：

A、 測试控制资源的信号量。

B、 若此信号量的值为正，则进程能够使用该资源。进程将信号量值减1，表示它使用了一个资源单位。

C、 若此信号量的值为0，则进程进入休眠状态。直至信号量值大于0。

进程被唤醒后，它返回运行第1步。

当进程不再使用此共享资源时。该信号量值增1。(返还一个资源单位) 假设有进程正在休眠等待此信号量。则唤醒它们。

 

为了正确地实现信号量，信号量值的測试及减1操作应当是原子操作。为此，信号量一般是在内核中实现的。

 

信号量、相互排斥量、条件变量之间的差异：

1、相互排斥锁必须总是由给它上锁的线程解锁，信号量的释放(即挂出)和等待操作不必由同一线程(进程)运行。

2、相互排斥锁要么被锁住，要么被解开

3、信号量有一个与之关联的状态(它的计数值)，信号量释放的操作总是被记住。

但当向一个条件变量发送信号时，假设没有线程等待在该条件变量上。那么该信号将丢失。

 

【信号量的意图在于进程间同步，相互排斥锁和条件变量的意图则在于线程间同步。

可是信号量也可用于线程间。相互排斥锁和条件变量也可用于进程间。我们应该使用适合详细应用的那组原语。

】

 

6、共享存储同意两个或很多其它进程共享一给定的存储区。由于数据不须要在客户进程和server进程之间复制，所以这是最快的一种IPC。

一旦这种内存区映射到共享它的进程的地址空间。这些进程间数据的传递就不再涉及内核。

但往该共享内存区存放信息或从中取走信息的进程间须要某种形式的同步。（通常，信号量、记录锁被用来实现对共享存储訪问的同步）

 

7、套接字Socket 可用于进程间通信。

 

死锁：

产生死锁的原因主要是：

（1）由于系统资源不足。

（2）资源分配不当等。

（3）进程执行推进的顺序不合适。

 

死锁的四个必要条件：

（1） 资源独占：一个资源每次仅仅能被一个进程使用。

（2） 不可剥夺:进程已获得的资源，在末使用完之前，不能强行剥夺。

（3） 请求与保持：一个进程因请求资源而堵塞时。对已获得的资源保持不放。

（4） 循环等待:若干进程之间形成一种头尾相接的循环等待资源关系。

仅仅要系统发生死锁，这些条件必定成立，而仅仅要上述条件之中的一个不满足，就不会发生死锁。

【记忆：前两个从资源的角度讲。后两个是从进程的角度讲】

 

在系统设计、进程调度等方面注意怎样不让这四个必要条件成立。怎样确

定资源的合理分配算法，避免进程永久占领系统资源。此外。也要防止进程在处于等待状态的情况下占用资源。因此，对资源的分配要给予合理的规划。

 

进程调度算法：

1、先来先服务(First Come First Service，FCFS)调度算法

依照进程进入就绪队列的先后顺序选择能够占用处理器的进程。这是一种不可抢占方式的调度算法，长处是实现简单，缺点是后来的进程等待CPU的时间较长。它现今主要用作辅助调度法；比如结合在优先级调度算法中使用，当有两个最高优先级的进程时，则谁先来，谁就先被调度。

 

2、短运行进程优先算法(Shortest Process First。SPF)就是从就绪队列中选择一个CPU运行时间预期最短的进程，将处理器分配给它。尽管较公平，但实现难度较大，由于要准确预定下一个进程的CPU运行周期是非常困难的。

 

3、最高优先级优先(Highest Priority First，HPF)调度算法

 

4、时间片轮转(Round Robin，RR)调度算法

轮转法仅仅能用来调度分配一些能够抢占的资源。这些能够抢占的资源能够随时被剥夺。并且能够将它们再分配给别的进程。CPU是可抢占资源的一种，但打印机等资源是不可抢占的。因为作业调度是对除了CPU之外的全部系统硬件资源的分配，当中包括有不可抢占资源，所以作业调度不使用轮转法。

 

页面置换算法

1、先进先出置换算法（FIFO）

最简单的页面置换算法是先入先出（FIFO）法。

这样的算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换。即先进入内存的页，先退出内存。

理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。

建立一个FIFO队列，收容全部在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时。就把它插在队尾上。这样的算法仅仅是在按线性顺序訪问地址空间时才是理想的，否则效率不高。由于那些常被訪问的页。往往在主存中也停留得最久。结果它们因变“老”而不得不被置换出去。

FIFO的还有一个缺点是，它有一种异常现象，即在添加存储块的情况下，反而使缺页中断率添加了。当然，导致这样的异常现象的页面走向实际上是非常少见的。

 

2、近期最久未使用（LRU）算法

FIFO算法利用页面进入内存后的时间长短作为置换根据。

假设以近期的过去作为不久将来的近似。那么就能够把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当须要置换一页时，选择在近期一段时间里最久没有使用过的页面予以置换。

这样的算法就称为最久未使用算法（Least Recently Used，LRU）。

LRU算法是与每一个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。LRU算法是常常採用的页面置换算法。并被觉得是相当好的，可是存在怎样实现它的问题。LRU算法须要实际硬件的支持。

其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
   

a.计数器。最简单的情况是使每一个页表项相应一个使用时间字段，并给CPU添加一个逻辑时钟或计数器。

每次存储訪问。该时钟都加1。

每当訪问一个页面时，时钟寄存器的内容就被拷贝到相应页表项的使用时间字段中。这样我们就能够始终保留着每一个页面最后訪问的“时间”。

在置换页面时。选择该时间值最小的页面。这样做，不仅要查页表，并且当页表改变时（因CPU调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。
   

b.栈。用一个栈保留页号。每当訪问一个页面时，就把它从栈中取出放在栈顶上。这样一来。栈顶总是放有眼下使用最多的页，而栈底放着眼下最少使用的页。由于要从栈的中间移走一项。所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上须要修改6个指针。

每次修改都要有开销。但须要置换哪个页面却可直接得到，用不着查找，由于尾指针指向栈底，当中有被置换页。

 

3、近期未使用算法（Not Recently Used。NUR）

因实现LRU算法必须有大量硬件支持。还须要一定的软件开销。

所以实际实现的都是一种简单有效的LRU近似算法。

一种LRU近似算法是近期未使用算法（Not Recently Used，NUR）。

它在存储分块表的每一表项中添加一个引用位，操作系统定期地将它们置为0。

当某一页被訪问时，由硬件将该位置1。过一段时间后，通过检查这些位能够确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，由于在近期一段时间里它未被訪问过。

 

4、工作集算法（working set）

在单纯的分页系统里。刚启动进程时。在内存中并没有页面。在CPU试图取第一条指令时就会产生一次缺页中断。使操作系统装入含有第一条指令的页面。其它由訪问全局数据和堆栈引起的缺页中断一般会紧接着发生。

一段时间以后，进程须要的大部分页面都已经在内存了。进程開始在较少缺页中断的情况下执行。这个策略称为请求调页（demand paging），由于页面是在须要时被调入的，而不是预先装入。

一个进程当前正在使用的页面的集合称为它的工作集（working set）。

假设整个工作集都被装入到了内存中，那么进程在执行到下一执行阶段之前，不会产生非常多缺页中断。若内存太小而无法容纳下整个工作集，那么进程的执行过程中会产生大量的缺页中断，导致执行速度也会变得非常缓慢。

不少分页系统都会设法跟踪进程的工作集，以确保在让进程执行曾经，它的工作集就已在内存中了。该方法称为工作集模型（working set model）。其目的在于大大降低缺页中断率。在让进程执行前预先装入其工作集页面也称为预先调页（prepaging）。请注意工作集是随着时间变化的。

人们非常早就发现大多数程序都不是均匀地訪问它们的地址空间的。而訪问往往是集中于一小部分页面。在任一时刻t，都存在一个集合，它包括全部近期k次内存訪问所訪问过的页面。这个集合w(k, t)就是工作集。

为了实现工作集模型，操作系统必须跟踪哪些页面在工作集中。

通过这些信息能够直接推导出一个合理的页面置换算法：当发生缺页中断时。淘汰一个不在工作集中的页面。

（至于系统怎样确定工作集，及算法较复杂，这里不做介绍）

 

5）第二次机会算法

第二次机会算法的基本思想是与FIFO同样的，可是有所改进，避免把常常使用的页面置换出去。

当选择置换页面时。检查它的訪问位。假设是0。就淘汰这页。假设訪问位是1，就给它第二次机会。并选择下一个FIFO页面。

当一个页面得到第二次机会时，它的訪问位就清为0，它的到达时间就置为当前时间。

假设该页在此期间被訪问过。则訪问位置1。

这样给了第二次机会的页面将不被淘汰，直至全部其它页面被淘汰过（或者也给了第二次机会）。因此。假设一个页面常常使用。它的訪问位总保持为1，它就从来不会被淘汰出去。

第二次机会算法可视为一个环形队列。用一个指针指示哪一页是以下要淘汰的。

当须要一个存储块时。指针就前进，直至找到訪问位是0的页。随着指针的前进，把訪问位就清为0。

在最坏的情况下，全部的訪问位都是1，指针要通过整个队列一周，每一个页都给第二次机会。这时就退化成FIFO算法了。

 

【注意：FIFO与LRU算法是笔试中常见的，务必要搞清楚】

 

僵尸进程

Unix/Linux系统中僵尸进程是怎样产生的？有什么危害？怎样避免？

     一个进程在调用exit命令结束自己的生命的时候。事实上它并没有真正的被销毁，而是留下一个称为僵尸进程（Zombie）的数据结构（系统调用exit，它的作用是使进程退出。但也只限于将一个正常的进程变成一个僵尸进程。并不能将其全然销毁）。


    在Linux进程的状态中，僵尸进程是非常特殊的一种。它已经放弃了差点儿全部内存空间，没有不论什么可运行代码，也不能被调度，只在进程列表中保留一个位置，记载该进程的退出状态等信息供其它进程收集，除此之外。僵尸进程不再占有不论什么内存空间。它须要它的父进程来为它收尸，假设他的父进程没安装SIGCHLD信号处理函数调用wait或waitpid()等待子进程结束。又没有显式忽略该信号。那么它就一直保持僵尸状态。假设这时父进程结束了。那么init进程自己主动会接手这个子进程，为它收尸。它还是能被清除的。可是假设假设父进程是一个循环，不会结束。那么子进程就会一直保持僵尸状态。这就是为什么系统中有时会有非常多的僵尸进程。

避免zombie的方法： 
      

1)在SVR4中。假设调用signal或sigset将SIGCHLD的配置设置为忽略,则不会产生僵死子进程。另外,使用SVR4版的sigaction,则可设置SA_NOCLDWAIT标志以避免子进程              僵死。 
      Linux中也可使用这个，在一个程序的開始调用这个函数 signal(SIGCHLD,SIG_IGN);  
        

2)调用fork两次。
       

3)用waitpid等待子进程返回. 

 

 

select与epoll的差别：（多次被问到）

select和epoll这两个机制都是多路I/O机制的解决方式，select为POSIX标准中的，而epoll为Linux所特有的。

差别（epoll相对select长处）主要有三：

1.select的句柄数目受限，select最多同一时候监听1024个fd。

而epoll没有。它的限制是最大的打开文件句柄数目。

2.epoll的最大优点是不会随着FD的数目增长而减少效率。在selec中採用轮询处理。当中的数据结构类似一个数组的数据结构，而epoll是维护一个队列。直接看队列是不是空就能够了。epoll仅仅会对”活跃”的socket进行操作—这是由于在内核实现中epoll是依据每一个fd上面的callback函数实现的。那么，仅仅有”活跃”的socket才会主动的去调用 callback函数（把这个句柄增加队列），其它idle状态句柄则不会，在这点上。epoll实现了一个”伪”AIO。可是假设绝大部分的I/O都是“活跃的”，每一个I/Oport使用率非常高的话，epoll效率不一定比select高（可能是要维护队列复杂）。

3.使用mmap加速内核与用户空间的消息传递。不管是select,poll还是epoll都须要内核把FD消息通知给用户空间，怎样避免不必要的内存拷贝就非常重要，在这点上，epoll是通过内核于用户空间mmap同一块内存实现的。 

 

进程和线程的差别：

1）一个程序至少有一个进程。一个进程至少有一个线程。

2）进程在运行过程中拥有独立的内存单元。而多个线程共享进程所拥有的内存。

3）进程可以独立运行，但线程不可以独立运行，必须依存在进程中，由使用该进程的应用程序提供多个线程运行控制。

怎样实现多线程编程？

线程的同步能够使用临界区、相互排斥量和信号量等方式实现。

多线程的优点：1.多任务2.提高运行效率。处理能力。   缺点：那就是，遇到一些独占性的资源时的调度问题。

 

数据结构部分

 

二叉树的遍历：

已知先序中序，求后序 （笔试必考）

链表逆序 （要会写出代码）

 

用两个栈实现队列 （此题在多家公司的笔试中遇到，要求写出代码）

  

哈希表的冲突

 

trie树、B树、B+树、红黑树、后缀树 （这些高级的数据结构要搞明确，要能清楚地向面试官讲清，这些初高级的数据结构一定要了然于胸，能清楚地讲出来 是加分项）

外部归并的败者树

海量数据处理相关：

比方Top n问题的多种解决方式一定要熟知。

（多次被问到）

（非常多互联网公司会在面试中问到）

 

数据库

各种数据库设计的范式的内容。 （百度笔试有考）

简单SQL语句的书写 

 

计算机网络

依据子网掩码求网络号

TCP的三次握手、TCP连接的client和server端的状态  （这些是在面试中最频繁遇到的）

TCP的四次挥手 

 

TCP：面向连接、传输可靠(保证数据正确性,保证数据顺序)、用于传输大量数据(流模式)、速度慢，建立连接须要开销较多(时间。系统资源)。

UDP：面向非连接、传输不可靠、用于传输少量数据(数据包模式)、速度快。

TCP的流量控制过程 （这个略复杂。仅仅有美团面的时候问到了）

 

算法

主定理 （笔试中可能会遇到）

 

二分查找 （要能写出健壮完整的代码）

 

Dijkstra最短路径、Floyd最短路径、A*算法 （路径搜索算法有公司会问到）

 

动态规划举例具体解释、贪心举例 （绝大多数公司不考察深入的算法）

最长递增子序列

 

排序的稳定性：

 

高速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法。而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

首先，排序算法的稳定性大家应该都知道。通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序同样。在简单形式化一下，假设Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。

其次。说一下稳定性的优点。排序算法假设是稳定的，那么从一个键上排序，然后再从还有一个键上排序。第一个键排序的结果能够为第二个键排序所用。基数排序就是这样。先按低位排序。逐次按高位排序，低位同样的元素其顺序再高位也同样时是不会改变的。

回到主题，如今分析一下常见的排序算法的稳定性，每一个都给出简单的理由。

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比較是相邻的两个元素比較，交换也发生在这两个元素之间。所以，假设两个元素相等，我想你是不会再无聊地把他们俩交换一下的；假设两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以同样元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

(2)选择排序

选择排序是给每一个位置选择当前元素最小的。比方给第一个位置选择最小的。在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，由于仅仅剩下它一个最大的元素了。那么。在一趟选择，假设当前元素比一个元素小，而该小的元素又出如今一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

比較拗口。举个样例，序列5 8 5 2 9。我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

(3)插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚開始这个有序的小序列仅仅有1个元素。就是第一个元素。比較是从有序序列的末尾開始，也就是想要插入的元素和已经有序的最大者開始比起。假设比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。假设碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序。所以插入排序是稳定的。

(4)高速排序

高速排序有两个方向，左边的i下标一直往右走。当a[i] <= a[center_index]，当中center_index是中枢元素的数组下标。一般取为数组第0个元素。

而右边的j下标一直往左走，当a[j] > a[center_index]。假设i和j都走不动了，i <=j, 交换a[i]和a[j],反复上面的过程，直到i>j。

交换a[j]和a[center_index]。完毕一趟高速排序。在中枢元素和a[j]交换的时候，非常有可能把前面的元素的稳定性打乱，比方序列为 5 3 3 4 3 8 9 10 11，如今中枢元素5和3(第5个元素，下标从1開始计)交换就会把元素3的稳定性打乱，所以高速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

(5)归并排序

归并排序是把序列递归地分成短序列，递归出口是短序列仅仅有1个元素(觉得直接有序)或者2个序列(1次比較和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列所有排好序。

能够发现，在1个或2个元素时，1个元素不会交换，2个元素假设大小相等也没有人有益交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中。稳定是是否受到破坏？没有。合并过程中我们能够保证假设两个当前元素相等时。我们把处在前面的序列的元素保存在结果序列的前面。这样就保证了稳定性。

所以，归并排序也是稳定的排序算法。

(6)基数排序

基数排序是依照低位先排序。然后收集；再依照高位排序，然后再收集；依次类推。直到最高位。有时候有些属性是有优先级顺序的。先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级同样的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

(7)希尔排序(shell)

希尔排序是依照不同步长对元素进行插入排序，当刚開始元素非常无序的时候，步长最大，所以插入排序的元素个数非常少。速度非常快。当元素基本有序了。步长非常小。插入排序对于有序的序列效率非常高。所以，希尔排序的时间复杂度会比o(n^2)好一些。因为多次插入排序。我们知道一次插入排序是稳定的。不会改变同样元素的相对顺序，但在不同的插入排序过程中，同样的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

(8)堆排序

我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。

在一个长为n 的序列。堆排序的过程是从第n/2開始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了。而第n/2-1个父节点把后面一个同样的元素没有交换。那么这2个同样的元素之间的稳定性就被破坏了。

所以。堆排序不是稳定的排序算法。

综上，得出结论: 选择排序、高速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

 

语言相关

C++ 构造函数、析构函数、拷贝构造函数（要能正确写出源码。參考《高质量程序设计指南——C++/C》中 末尾的測试）

C++的虚继承、虚函数、覆盖、隐藏  

C++的内存回收、智能指针

看看《effective c++》会对面试有所帮助，楼主对C++这方面长时间没用，之前又没有准备复习，以致面试官问上面非常基础的问题都答得不好，错失良机。

 

设计模式

工厂方法（要能写出演示样例代码）

抽象工厂

单例模式 （写出演示样例代码）

组合模式

装饰者模式

观察者模式

（以上是我面试遇到的，对于常见的设计模式要知道其内容、适用情景、与相关的模式的异同及类图要很熟悉）

纸上写代码 （非常重要）

遇到非常多大公司在面试环节都要求在纸上写代码（笔试也有非常多写代码的），这些题目一般都是简单的，考察面试者写代码的健壮性，考虑问题的周全，及代码的规范。

一下是我遇到的纸上写代码的题目。

写memcpy （注意考虑内存重叠问题）

写trim函数 （注意就地移动字符串 以免内存泄露）

写strcpy函数

写strstr函数

写二分查找 （注意细节，注意边界）

输入先序和中序，返回一颗二叉树

用两个栈实现队列的操作

（以上都是常见的，出现频率较高的。面试之前一定要准备好）

写在后面

校招之前的准备真的非常重要。楼主如今肠子都悔青了。

写一下楼主的校招经历：（楼主投的是后台开发）

第一家。阿里，坑爹的在线笔试，全是选择题，不少是智力逻辑题、概率题还有专业题。时间非常紧张。答的一塌糊涂。直接给跪了（讨厌在线笔试啊，之后每次在线測试都挂了T-T）。之后，联发科过笔试，进面试。由于不想搞嵌入式，仅仅想拿联发科来练手，面试说话比較嚣张，被pass了。

然后是腾讯，进入二面，自我感觉良好，然后莫名其妙的被挂了（后来想想可能是一面面的不太好，问我C++非常基础的东西我都忘了）

百度笔试挂了，至今想不通为什么挂（难道是我字迹潦草？）。

美团进二面，美团笔试全是编程题，面试问的也相当多，楼主数据库是软肋，面试一问到这方面就给跪。

搜狗进二面，搜狗笔试题出的非常不错。有些深度，一面的面试官非常nice，和我聊了一个多小时，二面的面试官略严肃。考了我一个多小时。最后是跪在了C++和纸上写代码还有搜索相关的问题上。（提前有所准备真的非常重要）

中间还有酷派、用友，皆进面试。这两家公司的笔试题出的非常不好，面试官感觉也略水。更重要的是楼主本就没打算去这两家公司，可能是面试的时候讲话略嚣张，人家认为我性格有缺陷…..（当时是内心着急，想找个保底的安心，事实上如今看来大可不必，后面来得大公司有非常多，要找准目标，不能什么公司都去，这样仅仅会浪费时间和精力）

还有小米和去哪儿网。这两家都是出了三个编程题。我笔试就挂了。（挂笔试。丢人啊）（注意，在笔试的时候写代码写个差点儿相同即可了。不要过分注重健壮性和细节，改卷的哪能看这么细致呢，这两家的笔试我就跪在这上面了，太注重对输入检查，考虑细节多，结果一个小时根本时间不够用）

9月底，创新工场笔试过。一面过。双选会。展程游戏面试后给offer。

拿到offer后就没赶场了。

这将近一个月的各种面各种挂，身心俱疲，食不下咽，真的非常辛苦。

十一过后，纠结要不要再继续面其它公司，之后又面了人人。给了offer，但又纠结去不去。

最后还是决定去搞手机游戏。然后三方办妥之后。直接回家歇息了，太累了。

总得来说，给大家的建议是：早点确定方向，搞清楚找个方向须要什么相关的知识。早做准备。（我是到写简历才发现自己仅仅能搞后台开发）

还有，简历上要突出重点，把擅长的方向写上面，并在自我介绍的时候说出来，引导面试官问你擅长的部分。

关于看书，《剑指offer》比較实用，有些笔试 面试题是此书上的，《编程之美》上面的题不多。