By

Contents
  1. 1. 面试概况
  2. 2. 面试内容

面试概况

面试时间：2016/03/10 15：00-16：15

面试形式：电话面试

面试岗位：自然语言处理工程师

面试持续时间较长，部分题目记不起来了。

面试内容

（1）做一下自我介绍

【经过前几轮面试的洗礼，这次专门准备了一下，效果不错。】

我是。。。

13年9月-15年4月期间。。。【科研项目1】。。。

15年4月-今。。。【科研项目2】。。。

除了科研项目。。。【工程项目】。。。

除了上边提到的三个周期比较长，规模比较大的项目之外。。。【小项目】。。。

此外，本科期间。。。【ACM】。。。

（2）针对【科研项目2】进行了一系列提问

Q：项目中用到的模型是自己开发实现？还是调用第三方库？

A：调用第三方库。

Q：使用的这些模型，哪个模型效果最好？

A：SVM

Q：为什么不尝试用K-means之类的方法？

A：K-means是聚类，项目中做的是分类

Q：为什么不直接使用这种方法，一个类别下边有很多特征词，然后计算每个文本和这些词之间的距离，进行分类？

A：这个方法太简单了吧。（不知道说啥）

Q：既然做分类，那么需要分类的数据是什么？类别都有哪些？

A：balabala。。。

Q：项目中用到的伪标注数据是指什么？

A：balabala。。。

（3）在线编程（注意：下边的代码是错误重重的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
题目：
给定一个二维数组input和一个字符串target；
input是rows行，cols列的二维数组，二维数组中每个元素为一个字符；
target是一个长度为len的字符串；
例如
char[][] input = 
{
    {'a', 'b', 'c'},
    {'t', 'e', 'f'},
    {'e', 'o', 's'}
};
char[] target = 'abe'

问题：
在二维数组中是否存在一条路径能够和target相匹配。
在上边的例子中，字符串'abe','beo','cfeb'等就符合条件，而字符串'abt','atoe'就不符合条件。

约束条件：
（1）二维数组中的每个字符只能使用一次
（2）从一个点跳向另一个点是，只能走上下左右四个方向
*/
bool search(char[][] input, int rows, int cols, char[] target, int len, int idx) {
    int i, j;
    bool flag = false;
    for (i = 0; i < rows && !flag; i++) {
        for (j = 0; j < cols && !flag; j++) {
            if (input[i][j] == target[0]) {
                flag |= search_recursive(input, i, j , rows, cols, target, 0);
            }
        }
    }
    return flag;
}

bool search_recursive(char[][] input, int row, int col, int rows, int cols, char[] target, int len, int idx) {
    bool ret = false;
    //terminate
    if (idx == len) {
        return true;
    }
    //try right
    // idx = 0
    if (col + 1 < cols && input[row][col + 1] == target[idx + 1]) {
        ret |= search_recursive(input, row, col + 1, rows, cols, target, len, idx + 1);
    }
    if (true == ret) {
        return ret;
    }
    //try down
    if (row + 1 < rows && input[row + 1][col] == target[idx + 1]) {
        ret |= search_recursive(input, row + 1, col, rows, cols, target, len, idx + 1);
    }
    if (true == ret) {
        return ret;
    }
    //try left
    if (col - 1 >= 0 && input[row][col - 1] == target[idx + 1]) {
        ret |= search_recursive(input, row, col - 1, rows, cols, target, len, idx + 1);
    }
    if (true == ret) {
        return ret;
    }
    //try up
    if (row - 1 >= 0 && input[row - 1][col] == target[idx + 1]) {
        ret |= search_recursive(input, row - 1, col, rows, cols, target, len, idx + 1 );
    }
    return ret;
}

分析+编码，大概用了20分钟左右，思路如下：

<1>这是一个图的搜索问题，可以用深度优先搜索；

<2>因为每一步跳越都是类似的，所以可以用递归方法来做；

于是我就在search中找到第一个符合标准的点，找到之后利用research_recursive进行递归查找；

编码完成，开始提问：

Q：你忘了每个字符只能用一次？

A：好像是忘记了，这会导致在两个点之间来回跳跃。我可以用一个大小为len*2的二维数组作为辅助空间tmp来记录搜索路径，对于第i步来讲，tmp[i][0]和tmp[i][1]就是坐标x和y。在搜索的时候，如果这个点之前已经访问过了，那么就回溯。

Q：假设现在要搜索的字符串为“*”，你跟我讲一下tmp的操作过程。

A：。。。tmp数组可以看作一个栈，balabala，入栈，出栈。。。

Q：那就是说每次都要线性扫描一次？

A：哦（恍然大悟），可以用一个辅助二维数组，大小与input相同，专门用来记录是否被访问过，例如初始化为0表示未访问，如果访问过就设置为1，这样每次只需要根据坐标就可以在O(1)时间内完成判断。

Q：你的代码还有一个问题，如果target长度为1，那么你的代码会怎样运行？

A：（看了一下代码）对哦，好像忘记这个特殊情况了，这可能会导致在递归函数中出现数组下标越界的问题，可以在search中进行一个判断用来避免这个问题，此外，在递归search函数中的4个if语句中也需要加一个这样的判断。

Q：这个问题就到这里吧。你熟悉设计模式吗？

A：以前本科时候上过这门课，但是之后就再没专门学习过。

Q：用C++或Java实现一个单例模式。

A：我试试。。。（过了一会儿）。。。不会

Q：那你知道单例模式吗？

A：知道。。。balabala。。。

（4）介绍一个自己比较熟悉的模型

介绍的HMM。

三个组成（隐马链，状态序列，观测序列）。

模型参数含义（A，B，π）。

改进之处。

参数训练方法（极大似然估计）。

viterbi预测算法。

（5）应聘者提问

Q：你手上有其他offer吗？

A：。。。

Q：你有什么问题要问我的吗？

A：团队规模？

Q：。。。

A：工作内容？

Q：。。。

A：新人培训？

Q：。。。

Contents
  1. 1. 面试概况
  2. 2. 面试内容