面试需要的基础知识

何为基础知识：

数据结构和算法
编程能力
数学知识
问题分析和推理能力
编程语言
在面试过程中,面试官要么直接问语言的语法,要么让应聘者用一种编程语言写代码解决一个问题,通过写出代码来判断应聘者对他使用的语言的掌握程度.

通常语言面试有3种类型.

第一种题型是面试官直接询问应聘者对C++的概念的理解。这种类型的问题,面试官特别喜欢了解应聘者对C++关键字的理解程度.
第二种题型是面试官拿出事先准备好的代码，让应聘者分析代码的运行结果.
第三种题型就是要求应聘者写代码定义一个类型或者实现类型中的成员函数.
数据结构
数据结构一直是技术面试的终点,大多数面试题都是围绕着数组、字符串、链表、树、栈及队列这几种常见的数据结构展开.
数组和字符串是两种最基本的数据结构,它们用连续内存分别存储数字和字符.
链表和树是面试种出现频率最高的数据结构。由于操作链表和树需要操作大量的指针,应聘者再解决相关问题的时候一定要留意代码的鲁棒性,否则容易出现程序崩溃的问题
数组
数组占据一块连续的内存并按照顺序存储数据.创建数组时,我们需要首先指定数组的容量大小,然后根据大小分配内存.因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分的利用
由于数组的内存是连续的，于是可以根据下标在O(1)时间读/写任何元素,因此他的时间效率很高的.因此常可以利用数组时间效率高的特点，用数组来实现简单的哈希表:把数组的下标设为哈希表的键值(Key),而把数组种的每一个数字设为哈希表的值(value),这样每一个下标及数组中该下标对应的数字就组成了一个“键值-值”的配对.

为了解决数组空间效率不高的问题,人们又设计实现了多种动态数组,比如C++的STL种的vector.

字符串

字符串是由若干字符组成的序列.C/C++种每个字符串都以字符’\0’作为结尾,这样我们就能很方便地找到字符串地最后尾部.由于这个歌特点,每个字符串都有一个额外字符开销.

为了节省内存,C/C++把常量字符串放到单独地一个内存区域.当几个指针赋值给相同地常量字符串时,它们实际上会指向相同地内存地址

如果把字符串常量的内容复制到两个数组中去,这两个数组的初始地址将会不同.
如果把字符串常量赋给两个指针，则这两个指针将指向同一个地址.

链表

链表应该是面试时被提及最频繁的数据结构.链表的结构很简单,它由指针把若干个节点连接成链状结构.链表的创建、插入节点、删除节点等操作都只需要20行左右的代码就能实现,其代码量比较适合面试。另外,由于链表是一种动态的数据结构,其需要对指针进行操作.链表内存分配不是在创建链表时一次性完成,而是每添加一个节点分配以此内存.由于没有闲置的内存,链表的空间效率比数组高。

树

树是一种在实际编程中经常遇到的数据结构.它的逻辑很简单,除了根节点之外每个节点只有一个父结点,根节点没有父结点.父结点和子结点之间用指针链接.由于树的操作会涉及大量的指针,因此与树有关的面试题都不太容易。
树的几种遍历：

前序遍历、中序遍历、后序遍历（递归和循环两种不同的实现方法）
宽度优先遍历、深度优先遍历

二叉树是树的一种特殊的结构,在二叉树中每个节点最多只能有2个子节点。二叉树的两个特例是堆和红黑树。堆分为最大堆和最小堆.在最大堆中根节点的值最大，在最小堆中根节点的值最小.有很多需要快速找到最大值或者最小值的问题都可以用堆来解决.红黑树是把树中的节点定义为红、黑两种颜色,并通过规则确保从根节点到叶结点的最长路径的长度不超过最短路径的两倍

栈和队列

栈的特点是后进先出,即最后被压入(push)栈的元素会第一个被弹出(pop).通常栈是一个不考虑排序的数据结构,我们需要O(n)时间才能找到栈中最大或者最小元素.

队列是另外一种很重要的数据结构,和栈不同的是,队列的特点是先进先出。

算法和数据结构

递归和循环

如果我们需要重复地多次计算相同地问题,则通常可以选择用递归或者循环两种不同的方法.递归是在一个函数的内部调用这个函数自身,而循环则是通过设置计算的初始值及终止条件,在一个范围内重复运算。

递归实现的代码比循环实现的代码要简洁的多.但有时候效率比较低。而面试官往往期待比较实用的解法.

查找和排序

查找相对简单不外乎:顺序查找、二分查找、哈希表查找和二叉排序树查找。

如果面试题是要求在排序的数组中（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数,那么我们都可以尝试用二分查找算法.

回溯法

可看作蛮力法的升级版,它从解决问题每一步的所有可能选项里系统的选择出一个可行的解决方案.回溯法非常时候由多个步骤组成的问题，并且每个步骤都有多个选项.当我们在某一步选择了其中一个选项时，就进入下一步,然后又面临新的选项.我们就这样重复选择，直至达到最终的状态.用回溯法解决的问题的所有选项可以形象地用树状结构表示.

动态规划与贪婪算法

我们在应用动态规划之前要分析能否把大问题分解成小问题,分解后的每个小问题也存在最优解。如果把小问题的最优解组合起来能够得到整个问题的最优解，那么我们就可以应用动态规划来解决这个问题.

贪婪算法和动态规划不一样,当我们应用贪婪算法解决问题的时候,每一步都可以做出一个贪婪的选择,基于这个选择,我们确定能够得到最优解