腾讯TEG一面凉经

本人的第一次面试。

本来投的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++后端，怎么会被这种部门捞啊，好凉啊。。。

更新

刚才看一下，竟然过了，是初试的要求低一些的原因吗？

还有，求问分布式的知识怎么补？

复试保佑我啊！