当然了，长远来看，我们都会死掉，所以我会把事情搞简单，说一些你绝对应该复习一下的关键概念。

大部分数组和字符串是可互换的，事实上，你遇到的大部分字符串处理的问题，都可以在理解数组的基础上得到解决。记住这一点之后，你应该懂得如何遍历数组，知道如何访问、转换和调换其中的每一个元素，而且要懂得如何对它们进行各种不同的集合运算。和其他算法相比，二分法检索（Binary search）可能会更多地成为面试问题的核心内容（如果你曾经碰到过有分类数组的问题，那么二分法检索有可能应该是你答案的一部分），你绝对必须知道如何使用它。

和数组密切相关的，是排序算法。你不大可能会被要求重复使用一个排序算法，但很可能你至少知道排序是如何在O(nlogn)的时间里完成的就行。不过你应该大概知道归并排序（merge sort）或者快速排序（quicksort）和基数排序（radix sort）的执行细节。

动态数组/可增数组 动态数组可以按需重新调整自己的大小，同时依然提供分时平摊的持续时间访问。一种典型的做法是，当在一个全排列数组中增加一个元素的时候，会形成一个新的、更大的数组，而旧数组中的元素也会被复制到新数组里。你应该在面试时做到完成一个动态数组。

如果你拿到一个非数组类问题，但你在答题中需要用到像数组结构这样的数组，不妨少给自己惹麻烦，直接用动态数组吧。

哈希映射/哈希表/词典/哈希集合 哈希表（Hash tables）是编程时的瑞士军刀，很多不同类型的问题（检查存在、计算频率、排序，等等）都能用哈希表来完美解决。它几乎肯定会出现在你的面试中，而你应该理解它的原理（哈希功能的角色、冲突如何解决、什么时候要调整大小、为什么）以及如何运用它们。

链表问题在C和C++的面试中最常见，因为它们是弄清楚应聘者是否理解指针的一种简单的办法。不过这个点太初级、太基础了，所以不管用哪种语言，你都应该知道该如何从零做起应用它们。而且由于大部分链表问题不过是与人所周知的遍历还有删除和插入相关的问题的变体，所以链表问题准备起来很容易，你没有理由拿不到这部分分数。

许多链表问题中都会用到一个小技巧，那就是慢速/快速指针技术。它的简单版含义如下：使用两个指针迭代生成一个列表，其中一个指针在另一个指针的前面。快速模式下的指针可能会是一个位于前面的固定数值（它有助于确定列表有无循环，或者找到列表中的第k个元素），或者也可能会跳过慢速指针经过的多个结点（打个比方，如果快速指针的速度是慢速指针的两倍，那么当它到达列表末尾时，慢速指针将会位于列表的中间）。

请注意，当面试官谈到链表时，他们常常指的是单链表，但你无论如何都应该问清楚。

栈和队列一般会是你用来解题的数据结构的一部分。你应该知道如何用链表和数组两种方式来实现它们。

加练两道题：利用两个队列实现一个栈，以及利用两个栈来实现一个队列。

你可能不会每天都见到树和图，但你很可能会在面试时遇到它们，所以你要彻底地看一下这些数据结构。

树最一般的定义，是和其他结点没有或者有一个以上关系的结点的集合，但在实践中，当面试官说“树”的时候，他们指的是一种叫二叉树的东西。二叉树是一种树的类型，它的每个结点都至多有两个子树，一般被称为左子树和右子树。

你不应该把二叉树和二叉搜索树混淆起来，后者是一种特殊的二叉树，它的左子树结点上的值都比父结点小，而右子树结点上的值都比父结点大或者相等。二叉搜索树的优点是，如果树的结构相对平衡（向面试官问清楚这个问题），那么查找、插入和删除就可以在O(log n)的时间里完成。二叉搜索树的其他重要属性，就是你跟着所有的左子树走，就能得到这个树上最小的元素，而跟着所有的右子树走，就能得到这个树上最大的元素。

请注意，是有办法让树一直保持平衡的，最常用的办法就是红黑树和AVL树。我不会去弄清楚它具体实现的细节，只要知道有这些数据结构就行。

不过你绝对必须知道遍历树（tree traversal）算法：广度优先搜索（breadth-first-search）、深度优先搜索（depth-first-search），以及中序遍历、后序遍历和前序遍历之间的差别。

以下是在Java实现中序遍历的例子，它可以打印出一个树的所有值（前序遍历和后序遍历几乎和这个一样）：

字典树（trie，读“tree”）常常被用在字符串问题里，它是一个n元树，除了根结点以外的每个结点都代表一个字符或者部分或完整的单词，而且沿着树的每一条路径都代表一个单词。实际上它真的没有听起来那么复杂，只要读一下维基百科上的页面、了解该如何构建一个字典树以及如何查询其中的数值就行。请注意，你可以通过前序遍历输出字典树中的所有键。作为一个练习，你可以想一想自己会如何利用字典树实现自动完成功能。

最后是堆（heaps），它也被称为优先队列，是你应该了解的最后一种数据结构。它们通常都是满足堆属性的二叉树：每个结点的子树的值都比结点本身的值小，或者与它相等。所以根结点的值总是最大的，也就是说你总能找到最大值，但代价就是寻找其他任何一个值所需的时间都是O(n)。插入和删除所需的时间依然是O(logn)。

和树一样，图也是由带子集的结点组成的，但和树不一样的地方在于，这些结点可以有多个父结点，所以可能会形成自环（loop）或者圈（cycle）。除了链接——也被称作边（edges）——之外，两个结点之间可能地有比指针更多的信息，而且可能会有值和权重。边有方向的图被称为有向图，而只有双向指针的图被称为无向图。边上有权重的图被称为加权图。

有三种方法来表示图，但你只要搞清楚邻接矩阵（adjacency matrices）和邻接表（adjacency lists）就行了。你应该了解它们计算的复杂程度、它们需要折衷的地方，以及如何在现实的代码中实现它们。用哪种方法取决于你有的图的类型，比如连接完整的简单图可能用邻接矩阵来实现更好，而稀疏一些的图则可能用邻接表来表示更好。

请注意，如果你是在实现加权图，很可能需要定义一个Edge类。

图论是一个非常宽泛的话题，所以很难知道一个人应该为一场面试去熟悉多少种图论算法，所以我只是列出了我认为可以覆盖90%图论问题的内容：你绝对必须知道该如何遍历一个图（深度优先或者广度优先），以及如何做拓扑排序（topological sorting），你应该知道如何实现迪杰斯特拉（Dijkstra）的最短路径算法（这里有一个制作精巧的视频解释了这一算法），同时也要知道如何实现普里姆（Prim’s）算法。最后，如果你还知道如何实现A搜索算法（Asearchalgorithm），那就更好了。

使用以上数据结构，你就可能解决绝大多数问题了，但也请尽管在这个部分下留言，为其他读者推荐其他数据结构。

要想处理位元，你必须先得知道在二进制补码（two’s complement）标记内部，数字是如何表示的——二进制补码和无格式二进制标记是一样的，只是负数要“进行位元翻转之后再加1”。比如要想得到数字-1，你要从用8位二进制整数表示是00000001的1开始。对每一个位元进行翻转之后的结果是11111110，再加上1就是11111111，也就成了二进制补码中的-1。

左移位运算符“<<”会把位元移向左边，用0来补上移走之后的空位。