《第7次东南大学面试算法讲座》由会员分享，可在线阅读，更多相关《第7次东南大学面试算法讲座（100页珍藏版）》请在金锄头文库上搜索。
1、东南大学东南大学面试面试 & & 算法讲座算法讲座July东南大学自动化研会2014-7-16, 晚6:309:00本次讲座大纲笔试面试考什么解决笔试面试题的常用算法常用算法的时间复杂度包括各类排序算法O(N)时间复杂度内能解决的问题包括KMP，最长回文子串Manacher算法如何学习算法相互串联以Trie树、后缀树，贪心、动态规划为例简单入手，追本溯源二叉树、红黑树、2-3-4树、B树为例海量数据处理面试题十种解决之道2笔试面试考什么3笔试偏基础语言基础int hope;int* hope;double(*p) 3;void (*func) ();操作系统线程与进程的区别产生死锁的条件如何规
2、避死锁C+内存分配堆、栈、自由存储区、全局/静态存储区，常量存储区网络协议TCP建立连接的三次握手数据库概率论与数理统计推荐数理统计学简史4基础不够 补基础语言 C ：C 和指针征服C 指针C+：C+ PrimerSTL 源码剖析Effective C+深度探索C+ 对象模型5面试偏算法数据结构上的增删改查查找、遍历、排序算法分治、递归、回溯贪心、动态规划海量数据处理6基于各个数据结构上的增删改查字符串字符串库函数的编写，例如atoi 等字符串查找、翻转、匹配数组查找（如二分查找、杨氏矩阵查找）链表翻转、遍历、查找、删除、合并Hash表查找树遍历（前序、中序、后序）set、map高级树的查找（
3、红黑树、B树、R树）图遍历查找（DFS、BFS）最短路径算法7知道了考什么，怎么破8笔试面试常用算法穷举（递归回溯）“万能的”求n个数的全排列 & 8皇后（N皇后问题）分治分而治之，然后归并递归回溯DFS空间换时间hashtable巧用数据结构堆能排序，考虑排序前后两个指针往中间扫若已经排好序，想想有无必要二分不能排序贪心最小生成树 Prim, Krusal最短路 dijkstra动态规划如 01背包问题，每一步都在决策细节处理注意边界条件9各类算法的时间复杂度10O(1) 到 O(nlogn)O(1)基本运算， ，%，寻址Hash表的期望复杂度O(logn)二分查找O(n1/2)枚举约数O(
4、n)线性查找建立堆O(nlogn)归并排序快速排序的期望复杂度基于比较排序的算法下界11O(n2) 到 O(nn)O(n2)集合里枚举所有二元组、朴素最近点对O(n3) 集合里枚举三元组、Floyd最短路、普通矩阵乘法O(2n) 枚举全部的子集O（2nn)TSP的动态规划算法O(n!)枚举全排列O(nn)枚举1.n的n维数组的全部元素总结O(1) O(logn) O(n1/2) O(n) O(nlogn) O(n2) O(n3) O(2n) O（2nn) O(n!) defabc）X：abc，Y：def；X-XT，得：abc-cba；Y-YT，得：def-fedXTYT，得到：cbafed-d
5、efabc，即(XTYT)T=YX16寻找最小的k个数输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。17最大子数组最大和题目描述输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。i)一维：输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。暴力循环O（N）遍历 1 -2 3 10 -4 7 2 -5 b ： 0 1 -1 3 13
6、 9 16 18 13 sum： 0 1 1 3 13 13 16 18 1818ii) 二维iii)子数组” 并不只是一个二维数组或矩形，而是联通的元素(上下或左右相邻即视为联通)iv)如果是个轮胎呢？19寻找和为定值的两个数输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。解答：百试不厌：暴力穷举如果无序，先排序，排完序后，i j前后两个指针往中间扫20快速排序算法的一个实现一前一后两指针同往后扫j
7、 指针从第一个元素扫到倒数第二个，遇到比主元小，(i+1)与 j 所指元素互换PARTITION(A, p, r)1 x Ar2 i p - 13 for j p to r - 14 do if Aj x5 then i i + 16 exchange Ai Aj7 exchange Ai + 1 Ar8 return i + 1QUICKSORT(A, p, r)1 if p r2 then q PARTITION(A, p, r) /关键3 QUICKSORT(A, p, q - 1)4 QUICKSORT(A, q + 1, r)21快速排序实现之步骤一int partition(int
8、 data,int lo,int hi) int key=datahi; /以最后一个元素，datahi为主元 int i=lo-1; for(int j=lo;jhi;j+) /注，j从p指向的是r-1，不是r。 if(dataj=key) i=i+1; swap(&datai,&dataj); swap(&datai+1,&datahi); /不能改为swap(&datai+1,&key) return i+1;22快速排序实现之步骤二void QuickSort(int data, int lo, int hi) if (lo i，那么Pi = Min(P2 * id - i, mx -
9、 i)令j = 2 * id - i，也就是说j是i关于id的对称点。当 mx - i Pj ，以Sj为中心的回文子串被包含在以Sid为中心的回文子串中，因 i 和 j 对称，以Si为中心的回文子串必然被包含在以Sid为中心的回文子串中，所以Pi = Pj。当 Pj = mx - i ，以Sj为中心的回文子串不一定被完全包含于以Sid为中心的回文子串中，但是基于对称性可知，图中两个绿框所包围的部分是相同的，也就是说以Si为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 Pi = mx - i。38代码线性时间解决最长回文(Manacher)void Manacher() int i,
10、mx = 0; int id; for(i=1; i i ) pi = MIN( p2*id-i, mx-i ); else/mx mx ) mx = pi + i; id = i; 39如何学习算法？40算法学习方法论基础很重要学习什么，心中有大纲算法解决什么问题，解决策略是什么广搜一层一层往外遍历，寻找最短路径策略：队列最小生成树最小代价连接所有点策略：贪心（Prim：贪心+权重队列）Dijkstra寻找单源最短路径策略：贪心+非负权重队列Floyd多结点对的最短路径策略：动态规划方法论对比联系从简单入手，追本溯源41要则一：把相关算法串联起来，相互比对比如trie树、后缀树贪心、动态规划
11、要则二：从简单入手，追本溯源二叉树、红黑树、2-3-4树、B树42Trie 树每个节点是一个字母从根到某节点的路径作为一个单词每个节点维护一个boolean值优化：压缩节点时间复杂度：查找O(len)空间复杂度： 跟公共前缀有关4344存储前缀，统计后缀Trie树 + TOP Khashmap+堆，hashmap+堆统计出如10个近似的热词44没这么简单（讨论） 搜索引擎的智能提示注意只能解决前缀的问题如何存储？分布？有无slave & master?P2P?如何更新？ 尽量透明？中文怎么处理？ 化成拼音？用途：最长前缀匹配！45后缀树 1/4以字符串S=XMADAMYX为例，它的长度为8，所
12、以S1.8, S2.8, . , S8.8都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀（对于后缀Si.n，我们说这项后缀起始于i）：S1.8, XMADAMYX， 也就是字符串本身，起始位置为1 S2.8, MADAMYX，起始位置为2 S3.8, ADAMYX，起始位置为3 S4.8, DAMYX，起始位置为4 S5.8, AMYX，起始位置为5 S6.8, MYX，起始位置为6 S7.8, YX，起始位置为7 S8.8, X，起始位置为8 空字串，记为$46后缀树 2/4把上面的后缀加入Trie后，我们得到右边的结构：47后缀树 3/4把这种没有分叉的路径压缩到一条
13、边并在叶节点上标注上每项后缀的起始位置48后缀树 4/4在待处理的子串后加一个空字串例如我们处理XMADAMYX前，先把XMADAMYX变为 XMADAMYX$，于是就得到suffix tree-后缀树了49贪心算法特点容易想到 证明可能困难应用广泛应用 MST (prim, Krusal)DijkstraHuffmanLRU缓存替换机制 （其实最好的机制是换掉最远不使用）其他问题的启发式给出近似解50Prim算法1462531030204525 554050153512162162316234边(1,2)(2,6)(3,6)(6,4)(3,5)成本1025152035策略：使得迄今所选择的边
14、的集合A构成一棵树；则将要计入到A中的下一条边(u,v)，应是E中一条当前不在A中且使得A(u,v)也是一棵树的最小成本边。146253102025153551Kruskal算法策略：图G的所有边按成本非降次序排列，下一条生成树T中的边是尚未加入树的边中具有最小成本、且和T中现有的边不会构成环路的边。1462531030204525 5540501535126345126345162345162345162345边(1,2)(3,6)(4,6)(2,6)(3,5)成本101520253514625352动态规划53两个简单的例子最短路径：A - B经过x1，x2，x3故枚举所有可能从A到B要经
15、过的路径选择一条最优如何求最优比较如何比较？写DP方程，min之类的如何写？练.如何练？.比如二维数组最小路径和一个二维矩阵M*N矩阵matrix中，找出一条路径，只能向右或向下，求路径经过元素之和最小当前位置(i, j)上一个位置只可能是(i-1， j) 或 (i, j-1)故：pathij = min(pathij-1, pathi-1j) + matrixij54寻找和为定值的多个数输入两个整数 n 和 m，从数列1，2，3.n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。list1.push_front(n); /典型的01背包问题find_factor(sum
16、-n, n-1); /放n，n-1个数填满sum-n list1.pop_front(); find_factor(sum, n-1); /不放n，n-1个数填满sum动态规划适用条件最优子结构独立重叠子问题55交替字符串输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序例如当s1 = “aabcc”，s2 = “dbbca”，s3 = “aadbbcbcac”时，则输出true，但如果s3=“accabdbbca”，则输出false。解法令dpij代表s30.i+j-1是否由s10.i-1和s20.j-1的字符
17、组成如果s1当前字符（即s1i-1）等于s3当前字符（即s3i+j-1），而且dpi-1j为真，那么可以取s1当前字符而忽略s2的情况，dpij返回真；如果s2当前字符等于s3当前字符，并且dpij-1为真，那么可以取s2而忽略s1的情况，dpij返回真，其它情况，dpij返回假56格子取数问题题目有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。57贪心陷阱不顾全局，只看局部，让第一次和第二次的路径都是最优58追
18、本溯源红黑树为何要有RB-Tree完全平衡完全二叉树高度平衡AVL树先理解二叉树的插入、删除后理解红黑树的插入修复、删除修复B树先学习2-3-4树，理解结点饱和分裂，结点稀缺合并为何？因为2-3-4 树在计算机科学中是阶为 4 的B树意味着什么？意味着2-3-4树中每个结点的关键字数目是：1-3个（ceil(m / 2)-1）= n = m-1m为阶数，即孩子树，等于459二叉树到完全二叉树树的深度越小，搜索时间logn（n即为树的深度）60AVL树高度平衡树AVL树中任何节点的两个子树的高度最大差别为一61红黑树的5个性质1.每个结点要么是红的，要么是黑的。 2.根结点是黑的。 3.每个叶结
19、点（叶结点即指树尾端NIL指针或NULL结点）是黑的。 4.如果一个结点是红的，那么它的俩个儿子都是黑的。 5.对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 62二叉树的插入插入一个节点63红黑树的插入插入一个元素后，需要修复，修复有两种手段重新着色旋转操作：左旋与右旋64红黑树的插入修复代码3种插入修复情况65插入一个元素而后修复的几种情况 1/3插入修复情况 预处理插入的是根结点原树是空树，此情况只会违反性质2对策：直接把此结点涂为黑色。插入修复情况插入的结点的父结点是黑色。此不会违反性质2和性质4，红黑树没有被破坏。对策：什么也不做。66插入一个元素而
20、后修复的几种情况 2/3插入修复情况1：当前结点的父结点是红色，且叔叔结点（祖父结点的另一个子结点）是红色对策：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法 （此情况3将引发后续的一连锁反应：情况2 和 情况3） 情况情况1 1变成了情况变成了情况22插入修复情况2：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋（还没完，在情况3中继续）67插入一个元素而后修复的几种情况 3/3 接情况接情况22插入修复情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是
21、其父节点的左子解法：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋 （从情况1到情况3，终于调整完成）68从2-3-4树开始谈起692-3-4树的查找702-3-4树的插入 1/3712-3-4树的插入 2/3722-3-4树的插入 3/3关键字数要超过4时就要开始分裂4阶的B树的关键字数满足：大于等于1，小于等于3732-3-4树一次完整的插入示例 1/2不断插入多个元素的过程742-3-4树一次完整的插入示例 1/2接上，继续插入元素N、B、X75看过了红黑树的插入看过了2-3-4树分裂接下来，看另外一种新树它与红黑树最大的区别在于，它的结点可以有许多子女，从几个到几千个76B树出
22、现缘由二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下 77一棵B树的示例查找文件29一直往下，3次磁盘IO操作和3次内存查找78B树的插入示例 1/5一棵5阶（即树中任一结点至多含有4个关键字，5棵子树）B树根结点至少得有2个孩子5阶，2- 4 个key，3-5 个childrenB树除根结点之外的结点（包括叶子结点）的关键字的个数n必须满足：（ceil(m / 2)-1）= n = m-1 2 = 关键字数 = 4m为孩子数，即子树的数目，等于579B树的插入示例 2/5插入以下字符字母到一棵空的B 树中非根结点关键字数小了（小于2个）就合并大了（超过4个）
23、就分裂）：C N G A H E K Q M F W L T Z D P R X Y S首先，结点空间足够，4个字母插入相同的结点中：当咱们试着插入H时，结点发现空间不够，以致将其分裂成2个结点，移动中间元素G上移到新的根结点中，在实现过程中，咱们把A和C留在当前结点中，而H和N放置新的其右邻居结点中：80B树的插入示例 3/5C N G A H E K Q M F W L T Z D P R X Y S当咱们插入E,K,Q时，不需要任何分裂操作：插入M需要一次分裂，注意M恰好是中间关键字元素，以致向上移到父节点中：81B树的插入示例 4/5C N G A H E K Q M F W L T
24、Z D P R X Y S插入F,W,L,T不需要任何分裂操作：插入Z时，最右的叶子结点空间满了，需要进行分裂操作，中间元素T上移到父节点中，注意通过上移中间元素，树最终还是保持平衡，分裂结果的结点存在2个关键字元素：82B树的插入示例 5/5C N G A H E K Q M F W L T Z D P R X Y S插入D时，导致最左边的叶子结点被分裂，D恰好也是中间元素，上移到父节点中，然后字母P,R,X,Y陆续插入不需要任何分裂操作（别忘了，任一结点最多可有4个关键字）：最后，当插入S时，含有N,P,Q,R的结点需要分裂，把中间元素Q上移到父节点中，但是问题来了，因为Q上移导致父结点
25、“D G M T” 也满了，所以也要进行分裂，将父节点中的中间元素M上移到新形成的根结点中，从而致使树的高度增加一层。83B+ 树一棵m阶的B+树和m阶的B树的异同点在于：有n棵子树的结点中含有n-1 个关键字所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(而B 树的非终节点也包含需要查找的有效信息)84B* 树B*-tree是B+-tree的变体在B+树的基础上，所有的叶子结点中包含了
26、全部关键字的信息，及指向含有这些关键字记录的指针)；B*树中非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）85B树、B+树、B*树的区别B树，B+树，B*树总结如下：B树：有序数组+平衡多叉树；B+树：有序数组链表+平衡多叉树；B*树：一棵丰满的B+树。86总结：1.理解了2-3-4树，便理解了B树2.理解了B树，便理解了B+树3.理解了B+树，便理解了B*树4.当然，还有一种树：空间划分树 - R树87R 树的查找假设我要查询广州市天河区天河城附近一公里的所有餐厅地址怎么办？打开地图（也就是整个R树）
27、，先选择国内还是国外（也就是根结点）；然后选择华南地区（对应第一层结点），选择广州市（对应第二层结点），再选择天河区（对应第三层结点），最后选择天河城所在的那个区域（对应叶子结点，存放有最小矩形），遍历所有在此区域内的结点，看是否满足我们的要求即可。88总结有了二叉树，为何要有AVL平衡树？有了AVL树，为何要有红黑树？有了红黑树，为何要有B树？有了B树，为何要有R树？89海量数据处理90十个密匙哈希分治simhash算法外排序MapReduce多层划分BitmapBloom FilterTrie树数据库倒排索引9192万丈高楼平地起Reb-Black treeset/map （map同时拥有
28、key和value，set的key就是value）multiset/multimap（允许重复键值）hashtablehashmap/hashset/hash_multiset/hash_multimap （允许重复键值）备注：C+ 11标准命名了基于hash函数实现的unordered_set/ unordered_map / unordered_multiset / unordered_multimap相当于hash_set、hash_ma，和hash_multiset、hash_multimap。9293分而治之/hash映射 + hash统计 + 堆/快速/归并排序海量日志数据，提取出
29、某日访问百度次数最多的那个IP分而治之/hash映射，比如模1000，把整个大文件映射为1000个小文件hash_map(ip，value)来进行频率统计（hash_map对那1000个文件中的所有IP进行频率统计，然后依次找出1000个文件中频率最大的那个IP）再在这1000个最大的IP中，找出那个频率最大的IP93类似问题变形hash函数映射 + hashmap统计 + 堆排有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。假设已有10w个敏感词，现给你50个单词，查询这50个单词中是否有敏感词。单机5G内存，磁盘200T的数据，分别为
30、字符串，然后给定一个字符串，判断这200T数据里面有没有这个字符串，怎么做？如果查询次数会非常的多, 怎么预处理？ 94simHash的具体算法分词给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN/博客/结构/之/法/算法/之/道/的/作者/July”，然后为每个特征向量赋予权值：CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。hash通过hash函数计算各个特征向量的hash值，hash值为二进制数01组成
31、的n-bit签名。比如“CSDN”的hash值Hash(CSDN)为100101，“博客”的hash值Hash(博客)为“101011”。就这样，字符串就变成了一系列数字。加权W = Hash * weight。W(CSDN)=100101*4=4-4-44-44，W(博客)=101011*5=5 -5 5 - 5 5 5。合并将上述各个特征的加权结果累加，变成一个序列串。如：“4+5,-4+-5,-4+5,4+-5,-4+5,4+5”，得到“9,-9,1,-1,1”。降维对于n位签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simha
32、sh的海明距离来判断它们的相似度。例如把上面计算出来的“9,-9,1,-1,1,9”降维，得到 “101011”，从而形成它们的simhash签名。959697算法之上，继续深入！数学微积分：微积分概念发展史概率论与数理统计：数理统计学简史 数学史：数学恩仇录数学与知识的探求古今数学思想素数之恋矩阵分析与应用，清华张贤达著；凸优化，作者: Stephen Boyd / Lieven Vandenberghe，原著名: Convex Optimization；搜索 & 推荐自然语言处理数据挖掘 & 机器学习SVM支持向量机导论支持向量机通俗导论（理解SVM的三层境界）98参考资料与继续阅读北京算法班的两个PPT周六班讲师邹博PPT周日班讲师曹博PPT算法导论第十二章 二叉搜索树第十三章 红黑树编程艺术githubhttps:/ you，any question？contact me微博： 研究者研究者JulyJuly100
