I took an interview with 17zuoye today. This article records the process and content of the interview.
今天参加了一起作业的 NLP 工程师面试，本文记录了面试的内容。
这家公司之前没听说过，得到这个面试机会的因为我在拉勾上投了一堆NLP/ML的职位，结果这家公司的HR很快找到我说可以安排面试，她的态度给我的感觉挺好，然后我就想那就试试吧。
这家公司是用 NLP/AI 做中小学教育的，感觉还是挺有前景的。
这次面试很直接，面试官一上来简单聊了两句，然后直接做题。
第一题：
输入为两个list，数据结构如下面 ListNode 所示，输出为两链表对应位的和，例如：
l1: 3->4->2, l2: 3->6->4, output: 6->0->7
- 每个节点只有一个非负整数
- 超过10的向下一个节点进位
- l1, l2可能不一样长, 对应节点没有的视为0
- 下面给出基本测试用例，面试者需自行设计测试用例，保证代码无bug
TestCase：
- l1: 1->1->1 l2: 2->2->2, output: 3->3->3
- l1: 1->2->3 l2: 4->5, output: 5->7->3
- l1: 1 l2: 9->9, output: 0->0->1
链表各位求和，LintCode167 原题，思路就是先加公共部分，再把相对长的链表未加的部分加到结果链表中，直接秒了。
[C++ Code]
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
70
71
72
73
74
75
76
77
78
79
80
81
|
class Solution {
public:
ListNode *addLists(ListNode *l1, ListNode *l2) {
ListNode *result = NULL, *iter = NULL, *i = l1, *j = l2;
int val1 = 0, val2 = 0, carry = 0, sum = 0;
if (i == NULL && j == NULL) {
return NULL;
}
else if (i == NULL) {
return j;
}
else if (j == NULL) {
return i;
}
else {
while (i != NULL && j != NULL) {
val1 = i->val;
val2 = j->val;
sum = (val1 + val2 + carry) % 10;
carry = (val1 + val2 + carry) / 10;
ListNode *node = new ListNode(sum);
if (result == NULL) {
result = node;
}
if (iter != NULL) {
iter->next = node;
}
iter = node;
i = i->next;
j = j->next;
}
while (i != NULL) {
sum = (i->val + carry) % 10;
carry = (i->val + carry) / 10;
ListNode *node = new ListNode(sum);
iter->next = node;
iter = node;
i = i->next;
}
while (j != NULL) {
sum = (j->val + carry) % 10;
carry = (j->val + carry) / 10;
ListNode *node = new ListNode(sum);
iter->next = node;
iter = node;
j = j->next;
}
if (carry) {
ListNode *node = new ListNode(carry);
iter->next = node;
}
return result;
}
}
};
|
第二题：
有序数组转为平衡二叉查找树 (Convert sorted array to AVL Tree)，LeetCode 108 原题，思路就是二分法，将有序数组中每次处于中间的元素作为二叉树根结点，递归地构造整棵树。
这么做的依据是平衡二叉树的一个性质：若为平衡二叉树，则中序遍历结果为一非递减序列。
[C++ Code]
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
|
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &A) {
TreeNode *root = NULL;
if (A.empty())
return NULL;
int size = A.size();
int low = 0, high = size - 1;
root = createTree(A, low, high);
return root;
}
TreeNode *createTree(vector<int> &A, int low, int high) {
TreeNode *root;
if (low > high)
return NULL;
int mid = (low + high) / 2;
root = new TreeNode(A[mid]);
root->left = createTree(A, low, mid - 1);
root->right = createTree(A, mid + 1, high);
return root;
}
};
|
还问了一些数据结构和算法方面的问题，比如有一堆字符串，如何判断一个新字符串是否出现在这堆字符串中，就可以用二叉查找树 (BST) 来做。
面试的两题都做出来，感觉面试官还是挺满意的。
2017-08-08 更新
AI/NLP 部门的老大今天又面了我一轮，聊了下我大学时候做的 Entity Linking 的项目，然后做了一道题。
他看了我博客上今日头条的面试，然后说我们就做这个题吧。。。
不过题目的要求稍有改动：一个字符串中只有大括号(“{}”)、中括号(“[]”)、小括号(“()”)，判断该字符串中的括号是否匹配。
e.g. str = “{()[]()}” 合法；str = “[(])” 不合法。
后经朴哥提醒，这也是一道原题 LeetCode 20 有效的括号序列。
[C++ Code]
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
| #include <iostream>
#include <string>
#include <stack>
using namespace std;
bool isLeft(char c) {
if (c == '{' || c == '[' || c == '(')
return true;
else
return false;
}
bool isMatch(char left, char right) {
if (right == '}') {
if (left == '{')
return true;
else
return false;
}
if (right == ']') {
if (left == '[')
return true;
else
return false;
}
if (right == ')') {
if (left == '(')
return true;
else
return false;
}
}
bool isValidParentheses(string &str) {
int size = str.length();
if (size == 0) return true;
stack<char> cache;
for (int i=0; i<size; i++) {
if (isLeft(str[i])) {
cache.push(str[i]);
}
else {
if (cache.empty() || !isMatch(cache.top(), str[i])) {
return false;
}
cache.pop();
}
}
if (!cache.empty()) {
return false;
}
return true;
}
|
限时编程测试结束后，又问了一些ML相关的知识。
第一个问题是 逻辑回归 和 线性回归 有什么区别？我没答上来，虽说这是一道很基础的问题了，看来是时候好好恶补 ML 的知识了。
第二个问题是如果在一段话中有一个单词出现了拼写错误，如何推荐替代它的正确单词？
这是一个开放问题了，和面试官讨论下来，我说了三种方法：
- 字符串相似度 (编辑距离) Trie树
- 计算候选单词的上下文相似度
- 设计一些启发式规则来计算候选单词的分数
今天面的感觉还行吧，不过一个 ML 里的基本问题没答上来确实很扣分了。
2017-08-10 更新
技术面试通过啦！
感谢一起科技！
也感谢我自己！
2017-10-03 更新
现在是国庆节，这几天北京的天气还是不错的！
突然想到上次面试时候没答上来的那道题：逻辑回归 和 线性回归 有什么区别？
就找了点资料研究了一下，以下是答案。
TODO