腾讯后台开发 数据结构和算法

数据结构

• 查找的常用数据结构？

  • 线性表、静态查找表、动态查找表、二叉搜索树、平衡二叉树(AVL树)、红黑树、B树、B+树、哈希表

• hash冲突的几种解决办法

  • 开放地址法，比如线性探查(从冲突位置开始线性扫)、平方探查(不停+)、双哈希函数(H(k,i) = (h1(k) +i*h2(k) ) mod m)探查等
  • 链地址法，发生冲突后直接在相同位置搞个链表
  • 再哈希法，搞很多个哈希函数，第一个挂了换第二个，以此类推
  • 建立公共溢出区，把哈希表分为公共表和溢出表，如果发生了溢出，溢出的数据全部放在溢出区。

• 链表和数组的区别（内存上的分布、增删查的时间复杂度）

  • 从内存上看，链表元素不一定相连，内存一定相连
  • 增删：链表O(1)，数组O(n)
  • 查：链表O(n)，数组O(1)

• 树的先根、中根、后根遍历（延伸出来波兰序列和逆波兰序列）

  • 先序中序后序就不用多说了8。
  • 波兰序列就是前缀表达式，逆波兰序列就是后缀表达式
  • 比如A+B_(C-D)-E_F，前缀表达式为- + A * B - C D * E F，后缀表达式为A B C D - * + E F * -
  • 求解前缀表达式是从后往前扫，后者方向相反，都是用栈处理

• 有N个节点的满二叉树的高度。1+logN

• AVL树

  • 任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是#card=math&code=O%28log%7Bn%7D%29)。
  • 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
  • LL、RR、LR、RL要区分
  • wiki

• BST树，二叉查找树

  • 满足以下性质

    • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
    • 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值
    • 任意节点的左、右子树也分别为二叉查找树
  • 搜索、插入、删除的复杂度等于树高，期望#card=math&code=O%28log%7Bn%7D%29)，退化到线性表后最坏#card=math&code=O%28n%29)。
  • 删除要注意四种情况：无左右子树、有左子树、有右子树、有左右子树

• 平衡树

  • 跟AVL树相比，少了最大高度差的限制而已，其他一样

• 红黑树

  • 查找插入删除都是#card=math&code=O%28log%7Bn%7D%29)

  • 红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

    • 节点是红色或黑色。
    • 根是黑色。
    • 所有叶子都是黑色（叶子是NIL节点，NIL结点经常可以充当正常结点使用以使得算法的表达更加容易。）。
    • 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
    • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
  • 这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
  • 要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个相邻的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

  • 插入分5种情况，都是先按照二叉搜索树的方法先插入，且把颜色定为红色，再分情况调整：

    • 插入位置是树的根，这种情况下直接把插入节点换成黑色就行
    • 插入位置的父节点是黑色，无事发生
    • 插入位置的父节点是红色且叔父节点也是红色，这种情况下把父节点和叔父节点变成黑色，把祖父节点变成红色，再根据祖父节点是否为根节点来判定祖父节点的颜色
    • 插入位置的父节点是红色且叔父节点为黑色/不存在，且祖父节点、父亲节点与当前节点形成LL/RR关系，这时候需要进行右旋/左旋，并交换父节点和祖父节点的颜色
    • 插入位置的父节点是红色且叔父节点为黑色/不存在，且祖父节点、父亲节点与当前节点形成LR/RL关系，这时候需要先进行一次左旋/右旋，使得三者关系变为LL/RR，再按上面的方法进行处理
  • 删除分6种情况。如果需要删除的节点有两个儿子，对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们要么找到它左子树中的最大元素、要么找到它右子树中的最小元素，并把它的值转移到要删除的节点中。接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值（没有复制颜色），不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。
  • 剩下部分看这里，讲得贼好

• 为什么在 STL 的实现中，用的是红黑树，而不是其他树。

  • 如果插入一个节点，引发了旋转，那么RBT和AVL都是最多只需要2次旋转操作，即两者都是O(1)
  • 但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。
  • AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
  • map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。

• B树

  • 概括来说是一个一般化的多叉查找树。一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。
  • 对于外存储器的信息读取最大的时间消耗在于寻找磁盘页面。那么一个基本的想法就是能不能减少这种读取的次数，在一个磁盘页面上，多存储一些索引信息。B树的基本逻辑就是这个思路，它要改二叉为多叉，每个节点存储更多的指针信息，以降低I/O操作数。

  • 一棵最小度为t的B树是满足如下四个条件的平衡多叉树：

    • 每个节点最多包含个关键字，除根节点外的每个节点至少有个关键字()，根节点至少有一个关键字
    • 每个节点中的关键字按不下降方式排列
    • 每个节点的关键字对其子树的范围分割。被指向的节点里的关键字范围在指针相邻的关键字之间。
    • 所有叶子节点具有相同的深度，即树的高度h。
  • 对于一个包含n个关键字，最小度数t的B树，高度h满足
  • 很明显，访问节点（即读取磁盘）的次数与树的高度呈正比，而B树与红黑树和普通的二叉查找树相比，虽然高度都是对数数量级，但是显然B树中log函数的底可以比2更大，因此，和二叉树相比，极大地减少了磁盘读取的次数。
  • 需要注意的是：指针，关键字，以及关键字所代表的文件地址这三样东西合起来构成了B树的一个节点，这个节点存储在一个磁盘块上
  • 因为B树节点中的关键字都是排序好的，所以，在节点中的信息被读入内存之后，可以采用二分查找这种快速的查找方式，更进一步减少了读入内存之后的计算时间，由此更能说明对于外存数据结构来说，I/O次数是其查找信息中最大的时间消耗，而我们要做的所有努力就是尽量在搜索过程中减少I/O操作的次数。
  • 插入过程就不用多说了8，反正我是会的，满了就先把中间关键字提上去再插入就ok了

  • 删除原理如下：

    • 基本原则是不能破坏关键字个数的限制
    • 如果在当前节点中，找到了要删的关键字，且当前节点为内部节点。那么，如果有比较丰满的前驱或后继，借一个上来，再把要删的关键字降下去，在子树中递归删除；如果没有比较丰满的前驱或后继，则令前驱与后继合并，把要删的关键字降下去，递归删除
    • 如果在当前节点中，还未找到要删的关键字，且当前节点为内部节点。那么去找下一步应该扫描的孩子，并判断这个孩子是否丰满，如果丰满，继续扫描；如果不丰满，则看其有无丰满的兄弟，有的话，从父亲那里接一个，父亲再找其最丰满的兄弟借一个；如果没有丰满的兄弟，则合并，再令父亲下降，以保证B树的结构。

• B+树

  • B+树是B树的一种变形，它更适合实际应用中操作系统的文件索引和数据库索引。这里使用阶数来定义B+树，而不像之前的B树中，使用的是最小度t来定义
  • 除根节点外的内部节点，每个节点最多有m个关键字，最少有ceil(m/2)个关键字。其中每个关键字对应一个子树（也就是最多有m棵子树，最少有ceil(m/2)棵子树
  • 根节点要么没有子树，要么至少有2棵子树

  • 所有的叶子节点包含了全部的关键字以及这些关键字指向文件的指针，并且：

    • 所有叶子节点中的关键字按大小顺序排列
    • 相邻的叶子节点顺序链接（相当于是构成了一个顺序链表）
    • 所有叶子节点在同一层
  • 所有分支节点的关键字都是对应子树中关键字的最大值

  • 与B树相比，不同点主要在于：

    • 内部节点中，关键字的个数与其子树的个数相同，不像B树中，子树的个数总比关键字个数多1个
    • 所有指向文件的关键字及其指针都在叶子节点中，不像B树，有的指向文件的关键字是在内部节点中。换句话说，B+树中，内部节点仅仅起到索引的作用
    • 在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支

  • B+树比B树更有优势，主要在于：

    • B+树的磁盘读写代价更低。B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。
    • B+树的查询效率更加稳定。由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
    • B+树更有利于对数据库的扫描。B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性能。

• 跳表

  • 跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。
  • 跳跃列表允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。
  • 跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速通道”，这里在第i层中的元素按某个固定的概率p出现在第i+1层中。
  • 在查找目标元素时，从顶层列表、头元素起步。算法沿着每层链表搜索，直至找到一个大于或等于目标的元素，或者到达当前层列表末尾。如果该元素等于目标元素，则表明该元素已被找到；如果该元素大于目标元素或已到达链表末尾，则退回到当前层的上一个元素，然后转入下一层进行搜索。

• 两个栈实现一个队列

  • 入队时，将元素压入stack1。
  • 出队时，把元素压入stack2，再出队；然后再把元素压回stack1

• 两个队列实现一个栈

  • 入栈时，把元素压入某个非空队列，都空则随便选
  • 出栈时，把非指定元素压入另一个空队列，直到找到最后一个元素，出栈

• 一颗二叉搜索树，找出树中的第k大节点

  • 中序遍历就完事了，如果是倒数第k大，就把左右儿子访问顺序换一下。

• 画图描述双链表的增删查

  • 注意首尾情况

• 实现一个函数, 判断机器的字节序是大顶端还是小顶端.

  • 用一个union实现

  • ```c union Node{ int num; char ch; }

int main(){ union Node p; p.num=0x1234568; if (p.ch==0x78) 小顶端 else 大顶端 // 还有另一种做法，连union都不用 int num=0x12345678; char *ch=# // 然后跟上面一样 } ```

• 给你一个链表，要你排序，拿出来再插入，至少需要O(n^2)

• 非递归完成二叉树的先序遍历（先序用栈、中序用栈、后序用两个栈）

• 堆

  • 从数组创建堆，时间复杂度O(nlogn)
  • 堆排序，O(nlogn)
  • 添加/删除节点，O(logn)

算法

• 排序一定要掌握：堆排、基排、快排、冒泡（时间复杂度、空间复杂度、应用场景、哪些是稳定性排序）

  • | 名称 | 平均情况 | 最好情况 | 最坏情况 | | —- | —- | —- | —- | | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | | 基数排序 | O(n) | O(n) | O(n) | | 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | | 希尔排序 | #card=math&code=O%28n%5Clog%5E2%7Bn%7D%29) | O(n) | #card=math&code=O%28n%5Clog%5E2%7Bn%7D%29) | | 插入排序 | O(n^2) | O(n) | O(n^2) | | 选择排序 | O(n^2) | O(n^2) | O(n^2) | | 冒泡排序 | O(n^2) | O(n) | O(n^2) | | 双向冒泡(鸡尾酒) | O(n^2) | O(n) | O(n^2) | | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) |

• 稳定的排序：插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序

• 不稳定的排序：选择排序、希尔排序、快速排序、堆排序是不稳定的

• 辅助空间比较：

  • 二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1)

• 特殊点：

  • 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。
  • 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
  • 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
  • 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
  • 当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。
  • 当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

• 外排序和内排序

  • 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序
  • 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序
    • 一句话说清楚快排，快排为什么会有最坏情况？如何避免最坏情况？还能不能再优化？

• 对于每次选择的区间，选择一个轴值，用该轴值把区间内其他元素分为两个区间并递归处理

• 最坏情况是轴值不能切割元素，一个区间为n-1个元素，另一个区间0个元素，就会退化到n方
• 最好做法是随机选择轴值，或者选头中尾三个元素的中位数
  • 图的深度优先搜索（延伸出回溯法）和广度优先搜索（延伸出分支界限法）链表翻转

• 编辑距离

  • 编辑距离，又称Levenshtein距离（莱文斯坦距离也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
  • 求两个字符串的编辑距离，做法是dp
  • leetcode
  • 字符串相似度公式：1-%7D#card=math&code=%5Cfrac%7B%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%7D%7Bmax%28s1%E9%95%BF%E5%BA%A6%2Cs2%E9%95%BF%E5%BA%A6%29%7D)

• 左旋or右旋数组——要求至少给出两种做法

  • reverse三次是最妙的

• 如何判断一个图是否连通？

  • 并查集。dfs判断节点个数。并查集看是否所有节点的根节点是否能够相同（不用吧，你dfs都能走完了还需要并查集？）

• 要从一亿个数中找出排序后第一到第一百的数

  • 堆排序最爽，先找100个树建堆，然后剩下的数据疯狂插入

• 如何求二叉树的最大深度？（先序遍历求高度）

• 求无序数组第k大。魔改快排即可

• 给你一个数x，在无序数组里找一个与这个数x最接近的数并返回

• 算法题：最长不重复字串。尺取就行

• 算法题问了三个，判断一个数是不是2的幂，两个单链表有公共节点，找出第一个。（top k用了4种方法寻找，同时计算了每种方法的时间复杂度。判断2的幂也用了四种（不断模2；列出了所有2的幂指数后二分搜索；减一与本身取&；统计二进制中1的个数）。两个链表公共节点用的计算长度后遍历对比，不详细说了，其实还想到另一种首尾相连找链表环头结点的方法。）

• 图中的最短路径问题怎么求、迪杰斯特拉算法和弗洛伊德算法的区别有哪些？

• 10亿个数存在文件中，只能在一台机器上进行全排序

• 说一下贪心和动态规划的区别。

  • 动态规划和贪心算法都是一种递推算法，均由局部最优解来推导全局最优解
  • 贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留。
  • 贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。
  • dp中，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
  • 动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解

• 说说不经过第三个变量，怎么将两个变量交换。a^=b, b^=a, a^=b;

• 给你一个超大的url集合，要对url进行去重，而内存空间有限，你会如何设计。

• 求二叉树中某个值为5的结点到根的路径。

• 字符串倒转。

• 升序链表的合并。

• 双向链表删除一个节点(注意头尾)

• 存储10亿个INT型的QQ号，但给的内存只有1GB。（明显，一个int型占用4个字节，10亿个QQ号就需要4GB的存储空间，直接存储内存不足。）解决方法是利用哈希存储，使用位图（每个QQ号只用一位进行存储，这样一个int型32位就能存储32个QQ号了）

• 在1亿个数中找出前1000个大的数（用int存储），只分配4KB的存储空间。解决这种问题（找出前n个最大或者最小的数），一般使用堆排。前n个最大的数使用最小堆，前n个最小的数使用最大堆 - 找出第k大的数，利用快排（快排的思想就是每次找到一个数在整个序列中的具体位置）

• 大整数乘法，使用分治思想

• 字符串匹配（判断回文串、找出最长回文子串、找出最长回文子序列、判断字符串A是否为字符串B的字序列）

• KMP算法（找出字符串A在字符串B的位置，不存在返回-1）

• 有一个页面能同时展示两个广告，现在有五个广告，设计算法使五个广告展示概率为1:2:3:4:5（搞出一堆数，按比例放，然后轮询展示）

• 加密算法有哪些、AES中向量的作用、md5的长度

• 两个大文件存url，找相同url

• 编程：实现 double pow(double a, int n)，要求考虑double和int的所有取值范围，若有溢出抛出异常。

• 实现 long avg(long *arr, int n)求平均数，要求考虑所有可能的取值范围。结果因为忘记了负数除法和取余的规则，写了半天没写完整就结束了

• 10g文件，只有2g内存，怎么查找文件中指定的字符串出现位置。MapReduce分割文件处理。
  他说可以用cat | grep 管道处理。

• 一个矩阵，从左上角到右下角，每个位置有一个权值。可以上下左右走，到达右下角的路径权值最小怎么走。
  先说了一下dfs递归实现。面试官说要优化。说了一下用迪杰斯特拉的思路，说可以。

• 四辆小车，每辆车加满油可以走一公里，问怎么能让一辆小车走最远。说了好几种方案，面试官引导我优化了一下，但是还是不满意，最后他说跳过。

• 十亿个数的集合和10w个数的集合，如何求它们的交集。（对小数组做hash，然后遍历大数组即可。我完全想错方向了。）

• 一个机器上有一个超大的文件，里面有4G个32位int型整数，而机器的内存只有512MB，我需要获得它的中位数，请问应该怎么办？

• 两个链表找第一个公共节点。

  • 遍历两个链表，计算长度差，然后让长的链表先走长度差步，然后让两个指针一起以相同速度往前走，每次判断两个节点是否相等
  • 维护两个栈，把第一个链表的节点全部压入栈A，把第二个链表的节点全部压入栈B，然后不断从A、B栈中弹出元素，直到弹出的元素不相同，那么上一个弹出的元素就是两个链表中第一个相同的元素。

• 找数组中多于一半的元素

  • 设置一个计数器count记录出现最多的元素的次数，和一个变量major记录当前出现最多的元素。然后遍历数组，如果count=0，则把major置为当前元素，如果遇到的数和major相同，则count+1，不同则count-1。扫描完成后，最后的major就是数组中出现次数最多的元素，再次扫描数组，计算major出现的次数
  • 线性选择算法：其实就是用快速排序的中间过程，partition结合二分，每次随机选择一个数，把比他小的排在左边，比他大的排在右边，直到选中数字的下标最终被排在n/2的位置，就说明左边都比他小了，右边都比他大了。这个数字就是中位数，然后再扫一次数组，看看这个数字出现次数是否超过n/2。

• 算出两个日期之间相隔的天数

• 说一下电梯算法

• n个整数的平均数