一起作业 NLP 工程师电面

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]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /**
     * @param l1: the first list
     * @param l2: the second list
     * @return: the sum list of l1 and l2 
     */
    ListNode *addLists(ListNode *l1, ListNode *l2) {
        // write your code here
        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]

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param A: A sorted (increasing order) array
     * @return: A tree node
     */
    TreeNode *sortedArrayToBST(vector<int> &A) {
        // write your code here
        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]

#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