笔试是面试过程中的重头戏，甚至是决定了面试通过与否的重要一环，我们需要通过不断的练习和方法论总结来提高我们的代码能力。以下是我总结的一些方法论思路，希望能与大家共勉，有不足之处还请大家指出。以下，enjoy:
面试需要的基础知识:
一.数据结构:
大多数面试题都是围绕着数组，字符串，链表，树，栈及队列这几种常见的数据结构展开。
数组和字符串是两种最基本的数据结构，他们用连续内存分别存储数字和字符。
链表和树是面试中出现频率最高的数据结构。
栈是一个与递归紧密相关的数据结构，同样队列也与广度优先遍历算法紧密相关，深刻理解这两种数据结构能帮助我们解决很多算法问题。
(1)数组
数组可以说是最简单的一种数据结构，他占据一块连续的内存并按照顺序存储数据。创建数组时，我们需要首先指定数组的容量大小，然后根据大小分配内存。即使我们只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分的利用。(可动态分配内存来解决上述问题)
由于数组中的内存是连续的，于是可以根据数组下标O(1)时间读/写任何元素，因此它的时间效率是很高的。我们可以根据数组时间效率高的优点，用数组来实现简单的哈希表:把数组的下标设为哈希表的键值(Key)，而把数组中的每个数字设为哈希表的值(Value)，这样每一个下标及数组中该下标对应的数字就组成了一个"键值-值"的配对。有了这样的哈希表，我们就可以在O(1)时间内实现查找，从而快速、高效地解决很多问题。
为了解决数组空间效率不高的问题，人们又设计实现了多种动态数组，比如C++的STL中的vector。为了避免浪费，我们先为数组开辟较小的空间，然后往数组中添加数据。当数据的数目超过数组的容量时，我们再重新分配一块更大的空间(STL的vector每次扩容时，新的容量都是前一次的两倍)，把之前的数据复制到新的数组中，再把之前的内存释放，这样就能减少内存的浪费。
在C/C++中，数组和指针是既相互关联又有区别的两个概念。当我们声明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素。我们可以用一个指针来访问数组。
(2)字符串
字符串是由若干字符组成的序列。C/C++中每个字符串都以字符’\0’作为结尾，这样我们就能很方便地找到字符串的最后尾部。但由于这个特点，每个字符串都有一个额外的字符开销，稍不留神就会造成字符串越界。
(3)链表
链表应该是面试时被提及最频繁的数据结构。链表的结构很简单，由指针把若干个节点连接成链状结构。链表的创建、插入节点、删除节点等操作都只需要20行左右的代码就能完成，其代码量比较适合面试。并且链表是一种动态的数据结构，其需要对指针进行操作，因此我们需要比较好的基础才能写出完整的代码。加上链表很灵活，在实际的工程中也很有应用价值。
在创建链表时，我们无须知到链表的长度。当插入一个节点时，我们只需要为新节点分配内存，然后调整指针的指向来确保新节点被链接到链表中。内存分配不是在创建链表时一次性完成的，而是每添加一个节点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。
(4)树
树是一种在实际工程中经常与到的一个数据结构。其逻辑:除根节点之外每个节点只有一个父节点，根节点没有父节点;除叶节点之外所有节点都有一个或多个子节点，叶节点没有子节点。父节点和子节点之间用指针链接。
二叉树:是树的一种特殊结构，在二叉树中每个节点最多只能有两个子节点。
树的遍历模式:
- 前序遍历:先访问根节点，再访问左子节点，最后访问右子节点。
- 中序遍历:先访问左子节点，再访问根节点，最后访问右子节点。
- 后序遍历:先访问左子节点，再访问右子节点，最后访问根节点。
- 宽度优先遍历:先访问树的第一层节点，再访问树的第二层节点，一直到最下面一层节点。
二叉搜索树:左子节点总是小于或者等于根节点，而右子节点总是大于或者等于根节点。我么可以平均在O(logn)的时间内根据数值在二叉搜索树中找到一个结点。
堆:分为最大堆和最小堆。在最大堆中根节点的值最大，在最小堆中根节点的值最小。有很多需要快速找到最大值或者最小值的问题都可以用堆来解决。
红黑树:红黑树是把树中的节点定义为红、黑两中颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。在C++的STL中，set、multiset、map、multimap等数据结构都是基于红黑树实现的。
(5)栈和队列
栈是一个非常常见的数据结构，它在计算机领域被广泛应用，比如操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。栈的特点是先进后出，即最后被压入(push)栈的元素会第一个被弹出(pop)。
通常栈是一个不考虑排序的数据结构，我们需要O(n)时间才能找到栈中的最大值或最小值。
队列的特点是先进先出，即第一个进入队列的元素将会第一个出来。
二.算法和数据操作
和数据结构一样，考查算法的面试题也备受面试官的青睐。很多算法都可以用递归和循环两种不同的方式实现。通常基于递归的实现方法代码会比较简洁，但性能不如基于循环的实现方法。 在面试的时候，我们可以根据题目的特点，甚至可以和面试官讨论选择合适的方法编程。
通常排序和查找是面试时考查算法的重点。在准备面试的时候，我们应该重点掌握二分查找、归并排序和快速排序，做到能随时正确、完整地写出它们的代码。
如果面试题要求在二维数组(可能具体表现为迷宫或者棋盘等)上搜索路径，那么我们可以尝试用回溯法。通常回溯法很适合用递归的代码实现。只有当面试官限定不可以用递归实现的时候，我们再考虑用栈来模拟递归的过程。
如果面试题是求某个问题的最优解，并且该问题可以分为多个子问题，那么我们可以尝试用动态规划。在用自上而下的递归思路去分析动态规划问题的时候，我们会发现子问题之间存在重叠的更小的子问题。为了避免重复计算，我们可以用自下而上的循环代码来实现，也就是把子问题的最优解先算出来并用数组(一般是以为数组或是二维数组)保存下来，接下来基于子问题的解计算大问题的解。
如果我们告诉面试官动态规划的思路之后，面试官还在提醒说在分解子问题的时候是不是存在某个特殊的选择，如果采用这个特殊的选择将一定能得到最优解。那么，通常面试官这样的提示意味着该面试题可能适用于贪婪算法。当然，面试官也会要求我们证明贪婪选择的确最终能够得到最优解。
位运算可以看成一类特殊的算法，它是把数字表示成二进制之后对0和1的操作。由于位运算的对象为二进制数字，所以不是很直观，但掌握它也不难，因为总共只有与、或、异或、左移和右移5种运算。
(1)递归和循环
如果我们需要重复地多次计算相同的问题，则通常可以选择用递归或者循环两种不同的方法。递归是在一个函数的内部调用这个函数自身。而循环则是通过设置计算的初始值及终止条件，在一个范围内重复计算。
通常递归的代码比较简洁。在面试的时候，如果面试官没有特别的要求，则我们可以尽量多采用递归的方法编程。
递归虽然有简洁的优点，但它同时也有显著的缺点。递归由于是函数调用自身，而函数调用是有时间和空间消耗的:每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解上述的例子中递归实现的效率不如循环。
另外，递归中可能很多计算都是重复的，从而对性能带来很大的负面影响。
所以当我们应用动态规划解决问题的时候通常是用递归的思路分析问题，但由于递归分解的子问题中存在大量的重复，因此我们总是用自下而上的循环来实现代码。
除了效率之外，递归还有可能引起更严重的问题:调用栈溢出。在前面的分析中提到需要为每一次函数调用在内存栈中分配空间，而每个进程的栈的容量是有限的。当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。
高质量的代码:
1.我们要有对代码的容错能力处理能力，代码不能只是针对一种假象的‘正常值’进行处理，要考虑异常状况，也要考虑资源的回收等问题。
2.要避免功能错误，这时最基本的要求，我们还要特别注意边界情况。
3.在写代码或者和面试官交谈时，如果发现出错的地方要快速反应，进行改正。
我们可以从规范性，完整性和鲁棒性三个方面提高代码的质量。
一.代码的规范性:
如果我们代码写的不够规范，影响面试官阅读代码的兴致，那么面试官就会默默的减去几分。
规范的代码:
- 清晰的书写
- 清晰的布局
- 合理的命名
通常编程面试的代码量都不会超过50行，书写不用花多少时间，关键是在写代码之前形成清晰的思路并能把思路用编程语言清楚的书写出来。
我们还要格外注意布局问题。当循环判断较多，逻辑较为复杂的时候，缩进的层次可能会比较多。如果布局不够清晰，缩进也不能体现代码的逻辑，那么面试官对这样的代码将会头昏脑涨。
我们在写代码的时候，用完整的英文单词组合命名变量和函数，让面试官一眼就能读懂我们代码的意图。
二.代码的完整性:
面试过程中，我们要周全地考虑问题。我们要对自己写的代码进行检查，看看是否完成了基本功能，输入边界是否能得到正确的输出，是否对各种不合规范的非法输入做出了合理的错误处理。
完整的代码可以从三方面来进行测试:
- 功能测试:保证我们的代码能完成基本功能。
- 边界测试:我们的代码经常会有循环或者递归，那么结束循环或者递归的边界值是否正确?
- 负面测试:当输入不符合要求的时候要做出合理的错误处理。
在软件开发的过程中，永远不变的就是需求一直在改变，我们要向面试官展示自己对程序可扩展性和可维护性的理解。
主要的处理错误的方法有以下三种:
- 函数用返回值来告知调用者是否出错:这个方法最大的问题是使用不便，因为函数不能直接把计算结果通过返回值赋值给其他变量，同时也不能把这个函数计算的结果直接作为参数传递给其他变量。
- 当错误发生时设置一个全局变量:这个方法的问题是调用者很容易忘记检查全局变量，从而在调用出错的时候忘记进行相应的错误处理，从而留下安全隐患。
- 异常:这个方法的问题是抛出异常的时候，程序的执行会打乱正常的顺序，对程序的性能有很大影响。
三.代码的鲁棒性:
Robust是指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。
容错性是鲁棒性的一个重要体现，不鲁棒的程序在发生异常事件时会出现不可预见的行为，或者干脆整个程序崩溃。所以在面试中我们也要特别重视代码的鲁棒性。
提高代码鲁棒性的有效途径是进行防御性编程。 防御性编程是一种编程习惯，是指在预见什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。举个例子:当我们试图打开文件时发现文件不存在，可以提示用户检查文件名和路径。
在面试的时候，最简单也最实用的防御性编程就是在函数入口添加代码以验证用户输入是否符合要求，当然有时候还要在代码中进行添加。
解决面试题的思路:
1.编代码前讲自己的思路，在做事之前明白自己要做的事情究竟是什么，以及该怎么做。
2.解释清楚问题本身和问题解决方案是关键。
3.在与面试官的对话中分析思路，发现方案中的错误和漏洞并加以改正。
画图，举例和分解能够帮助我们解决复杂的问题。下面详细解释:
一.画图:
图形能使抽象的问题形象化。当面试题涉及链表，二维数组，二叉树等数据结构时，如果在纸面上画出几张草图，则题目中隐藏的规律就有可能变得很直观。
对于复杂的问题，我门光用语言未必能够说的清楚。这时候可以画出几幅图形，一边看着图形一边讲解面试官就能更加轻松地理解我们的思路。这对我们是有益的，因为面试官会觉得我们具有很好的沟通交流能力。