菜鸟笔记
提升您的技术认知

腾讯TEG一面记录

阅读 : 53

本人的第一次面试。 本来投的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. 数据库. 这个大坑慢慢补