本人的第一次面试。 本来投的csig，一直没被捞就被释放了，然后今天被teg约面试。
主要问题如下：
1. 自我介绍 名字，学校，平常就看书、运动、写写博客。喜欢算法和数据结构（挖坑开始）。
2. 先问个简单算法吧，讲下kmp的原理 我讲了下next数组，然后他问复杂度，一个主串多个模式串呢？
3. 我自己挖坑提到ac自动机，问了具体实现和复杂度 由于我基本忘了，赶紧说我是队里的数学选手，字符串题都是队友做
4. 讲一下各种最短路算法以及它们的差异 我把处理负权图说成了dikstra，晕（实际是bellman-ford）
5. 数据结构方面：rmq问题 我讲了st表和线段树
6. 然后又开始问线段树，原理及构建
我说每个区间都是一个节点，每个节点存自己对应的区间的统计信息
void build(int o, int l, int r) { int m = l (r-l) / 2; if(l == r) minv[o] = a[l]; else { build(2*o, l, m); build(2*o 1, m 1, r); minv[o] = min(minv[2*o], minv[2*o 1]); } }
7. 数据库: - innodb的索引结构：b 树 - b树与b 树的区别：节点不存储信息、范围查询、时间稳定 - 幻影读：不清楚 - 事务级隔离：不清楚 - 主从一致性：不清楚 - nosql：不清楚 - cass？？：反正是一个没听过的名词缩写
、8. 操作系统： - 进程、线程和协程的区别：协程不太了解，只知道是一种比线程更轻量的方式 - 进程间的通信方式：管道、信号量、信号、共享内存和套接字
9. 又问了一个算法题：有n整数，其中有一个数出现次数超过n/2，如何找到他。 - 先讲了用map统计一下， - 后来想到可以将互异的元素两两划掉去，口糊了一个递归算法，o(n)
10. 最后，你有什么想问的问题吗？ - 你是什么部门的？teg的一个部门，主要是分布式数据库开发 - 你们希望实习生拥有哪些技能和素质？实习生的话主要看数据结构、操作系统等计算机基础，校招的话会看项目
总结一下： 1. 这次根本没提项目，之前面csig的腾讯电脑管家，就一直怼项目，各部门差异有点大。 2. 估计对方也是个acmer，问了很多算法竞赛的知识，字符串算法对一个数学选手极不友好（就不应该把一个没获奖的竞赛经历写上去） 3. 对方是分布式数据库开发的，问了好多数据库方面的知识，分布式这一块我都没准备，之前数据库课程也没学好，结果一问三不知，尴尬 4. 我投的c 后端，怎么会被这种部门捞啊，好凉啊。。。
补题：
1. kmp和ac自动机
kmp复杂度为o(n m),
void getfail(char* p, int* f) { int m = strlen(p); f[0] = 0; f[1] = 0; //递推边界的初值 for (int i = 1; i < m; i ) { int j = f[i]; while (j && p[i] != p[j]) j = f[j]; //往回走 f[i 1] = (p[i] == p[j] ? j 1 : 0); } } void find(char* t, char* p, int * f) { int n = strlen(t), m = strlen(p); getfail(p, f); int j = 0; //当前结点编号 for (int i = 0; i < n; i ) { while (j && p[j] != t[i]) j = f[j]; //顺着失配边走，知道可以匹配 if (p[j] == t[i]) j ; if (j == m) { printf("%d\n", i - m 1); //找到了一个 j = f[j]; } } }
view code
2. 多个模式串匹配使用ac自动机，组成一个大的状态转移图，而不是每个模式串构造一个转移图。
ac自动机是在trie树的每个节点加一条fail边，指向当前位置匹配失败时需要跳转到的位置
- trie的插入、删除复杂度都是o(字符串的长度)，因此构建状态转移图是o(模式串长度之和)
- ac自动机在查找所有匹配的位置时，时间复杂度为 o(|s| m)， |s| 是文本串的长度，m是模板串总的匹配数目
3.
- dijkstra不能用于负权图，s集合和t集合，t集合dis[v]最小的就是点v最终的最短距离，如果存在负边就不一定，所以dijkstra不能用于负权图，复杂度o(vlogv)
- bellman-ford可以处理负权图，当n-1次之后还能进行松弛操作，说明存在负权，复杂度o(ve)
- spfa只将发生松弛操作的节点入队，因为松弛操作必定发生在前导节点成功松弛的节点上。spfa在随机的稀疏图上表现出色，并且极其适合带有负边权的图。然而spfa在最坏情况的时间复杂度与bellman-ford算法相同
- disjkstra适合稠密图
4. 协程
5. 数据库. 这个大坑慢慢补