数据结构
1. 图（深度广度优先遍历、单源最短路径、最小生成树）
数据结构（C++）<图的深度遍历和广度遍历> - CSDN博客 （遍历代码）
数据结构（C++）<图的邻接表表示> - CSDN博客 （定义结构代码）
深度优先遍历：深度优先遍历是一个不断探查和回溯的过程，在探查的每一 步，算法都有一个当前顶点。最初的当前顶点，也就是指定的起始顶点。每一步的探查过程中，首先对当前顶点v进行访问，并立即设置该顶点的访问标志visited[v]=true。接着在v的所有邻接顶点中找出尚未访问过的一个，并将其作为下一步探查的当前顶点。倘若当前顶点的所有邻接顶点已经被访问过，则退回上一步，将上一步所访问的顶点重新取出，当做探查的当前顶点。重复上述过程直到所有顶点已经被访问过。
广度优先遍历：广度优先遍历是一个逐层遍历的过程，在此过程中图中有多少个顶点就需要重复多少步，每一步都有一个当前顶点v,并设置当前顶点访问标志visited[v]=true。接着依次访问v的各个未访问过的邻接顶点w1，w2,…wt。再顺序访问w1,w1,…wt的所有还未访问过的邻接顶点。再从这些访问过的顶点去访问它们所有还未被访问过的邻接顶点，重复以上步骤，直到所有顶点都被访问。
2 红黑树性质 ？各种树性能对比 ？
红黑树(一)之 原理和算法详细介绍 - 如果天空不死 - 博客园
二叉查找树、平衡二叉树、红黑树、B-/B+树性能对比 - CSDN博客
二叉查找树：有N个节点，树高H为log(N+1)<= H <= log2(N+1)（都是以2为底的对数），查找的平均时间复杂度在O(logN)数量级上（最坏情况时O(N)），插入一个结点的时间复杂度O(logN)， 删除操作的时间复杂度最大不会超过O(logN)。
红黑树：
（1） 每一个结点的颜色仅仅能是红色或黑色。
（2）根结点是黑色的。
（3） 每一个叶子结点都带有两个空的黑色结点（被称为黑哨兵，就是图中黑色小圆圈），假设一个结点n的仅仅有一个左孩子，那么n的右孩子是一个黑哨兵；假设结点n仅仅有一个右孩子，那么n的左孩子是一个黑哨兵。
（4）假设一个结点是红的，则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
（5） 对于每一个结点来说，从该结点到其子孙叶结点的全部路径上包括同样数目的黑结点。
红黑树的这5个性质中，第3点是比較难理解的，但它却很有必要。我们看图1中的左边这张图，假设不使用黑哨兵，它全然满足红黑树性质，结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但假设添加黑哨兵后（如图1右图中的小黑圆点），叶结点的个数变为8个黑哨兵，根结点50到这8个叶结点路径上的黑高度就不一样了，所以它并非一棵红黑树。
不是正确的红黑树（为什么要加黑哨兵的原因）
B树存在的意义（有效减少内存和磁盘之间交换数据的频率）
如果内存和外存交换数据次数频繁，会造成了时间效率上的瓶颈，那么 B 树结构怎么就可以做到减少次数呢？
外存比如硬盘，是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是 211 或 214 个字节。在一个典型的 B 树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对 B 树 进行调整，使得 B 树的阶数 （或结点的元素）与硬盘存储的页面大小匹配。比如一棵 B 树的阶位 1001（即一个结点包含 1000 个关键字），高度为 2，它可以存储超过 10 亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。
通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获取最大数量的数据。由于 B 树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少必须访问结点和数据块的数量，从而提高了性能。可以说，B树的数据结构就是为内外存的数据交互准备的。
二叉树和哈希表查找的时间复杂度
满二叉树/完美二叉树(Perfect Binary Tree)：一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。 (注： 国内的数据结构教材大多翻译为"满二叉树")
完全二叉树(Complete Binary Tree): 完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
完满二叉树(Full Binary Tree)：所有非叶子结点的度都是2。（只要你有孩子，你就必然是有两个孩子。）
3. 静态链表和动态链表的区别
4.堆和栈的区别？堆和栈的生命周期？
（1）堆栈空间分配区别：
1.栈内存：由程序自动向操作系统申请分配以及回收，速度快，使用方便，但程序员无法控制。若分配失败，则提示栈溢出错误。注意，const局部变量也储存在栈区内，栈区向地址减小的方向增长。
堆内存：程序员向操作系统申请一块内存，当系统收到程序的申请时，会遍历一个记录空闲内存地址的链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。分配的速度较慢，地址不连续，容易碎片化。此外，由程序员申请，同时也必须由程序员负责销毁，否则则导致内存泄露。若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。
（2）什么是缓存？一级缓存和二级缓存是什么？堆栈缓存方式区别？
缓存-------- 是CPU的一部分，它存在于CPU中，CPU存取数据的速度非常的快，一秒钟能够存取、处理十亿条指令和数据（术语：CPU主频1G），而内存就慢很多，快的内存能够达到几十兆就不错了，可见两者的速度差异是多么的大。缓存是为了解决CPU速度和内存速度的速度差异问题。内存中被CPU访问最频繁的数据和指令被复制入CPU中的缓存，这样CPU就可以不经常到象“蜗牛”一样慢的内存中去取数据了，CPU只要到缓存中去取就行了，而缓存的速度要比内存快很多。
一级缓存：一级缓存可分为 一级指令缓存 和 一级数据缓存。一级指令缓存用于暂时存储并向CPU递送各类运算指令；一级数据缓存用于暂时存储并向CPU递送运算所需数据。
二级缓存：二级缓存就是一级缓存的缓冲器：一级缓存制造成本很高因此它的容量有限，二级缓存的作用就是存储那些CPU处理时需要用到、一级缓存又无法存储的数据。
1、栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放；
2、堆是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。
（3）堆栈数据结构区别：
堆（数据结构）：是一种非连续的树形储存数据结构，每个节点有一个值，整棵树是经过排序的。
栈（数据结构）：是一种连续储存的数据结构，具有先进后出的性质。
5.数据结构中各种树
6. 平衡二叉树（AVL树） 平衡二叉树（AVL树）小结 - as_ - 博客园
定义：AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（logn）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
（1）插入：向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有1.5乘logn个节点，而每次AVL旋转都耗费恒定的时间，插入处理在整体上耗费O(logn) 时间
（2）删除：从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有logn个节点被旋转，而每次AVL旋转耗费恒定的时间，删除处理在整体上耗费的时间复杂度O(logn) 时间。
（3）查找：可以像普通二叉查找树一样的进行，所以耗费O(logn)时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查找而改变。（这是与伸展树查找相对立的，它会因为查找而变更树结构。）
算法
1.有1一亿个数据，只需要找到前100个最大的数据，有什么思路？
用100个节点的大顶堆，每次从数据库中入堆，取出堆顶的数字，这样不断的入堆出堆。
2.怎样去评估存储机群的容量（用多少个机器去组成机群合适）
3. 海量数据处理的知识点，（hash表， hash统计）
海量数据处理方法： 教你如何迅速秒杀掉：99%的海量数据处理面试题 - CSDN博客
4.怎样统计一篇英文文章中出现频率最高的10个单词，用什么数据结构和算法实现？
字典树（Trie树）或者hash_map都可以
5.找出一个字符串中第一次出现的指定字符，怎么优化算法？
6.字符串与数值类型变量之间互相转换
（1）字符串转double （2）字符串转成long型 （3）字符串转整形
（1）double atof(const char *_String); （2）long atol(const char *_String); （3） int atoi(const char *_String);
将字符串转成数字通用做法：用 istringstream字符串输入流，先把string输入流，再把流输出到数字变量
将数值类型变量转换为字符串类型通用方法：利用字符串输出流ostringstream
方法str()将缓冲区的内容复制到一个string对象中，并返回
注意 ： << 或者 >>箭头的方向代表就是数据流入的方向
istringstream >> text 数据从 istringstream 流入到 text
ostringstream << text 数据从 text 流入到 ostringstream
7.设计模式六大原则
8.自己实现一个微信朋友圈的功能
朋友圈的设计及实现。 - CSDN博客
9. 非递归实现二叉树的前序、中序、后序遍历
对于前序遍历是可以进行更优化的
