本文记录我大三寒假找NLP算法实习岗位的面试(被暴打)经历，整个期末考试周上午考试下午面试，连着面了五六天，每次两小时左右，一通下来被虐得很厉害，算是知道自己到底有多辣鸡了，大多数面试官人都很好，少数emmm。。。写下此篇给找ai/nlp方向实习工作的同学当作复习参考。

先说下结果，拿到的offer：扇贝自然语言处理工程师，百度NLP部百度翻译算法工程师。

挂掉的公司：赛舵智能，字节跳动

扇贝最早给我发了offer，刚好两天后就放假了，所以直接去了南京，租好房子就上班了，百度的offer在我上班一周后才发给我，不得已只能错过。

赛舵智能

2019.12.23，周日下午两点第一个面的公司是上海赛舵智能科技有限公司，今年7月融了一千万成立的，之前本来说是CEO来面我，然后CEO出差鸽了我一次，最后换了一个技术leader来面我。

一面

python基础

问了python在定义函数时的 *和**的作用

没答出来，fluent python看过给忘了，回去搜了才知道*会把接收到的参数形成一个元组，而**则会把接收到的参数存入一个字典
python常见的数据结构

list， set， dict，tuple，name_tuple，organized_dict
多线程，协程

爬虫学过，全忘了
面向对象的初始化方法？

我说有双下划线init,len,getattr,str
问我class里怎么定义私有变量，公有变量？

我又跪了，平常都是在init里传入后就self.变量名=值，乱说了个在init里用self.定义的就是私有，在外边定义的就是共有。其实真实答案应该是单下划线开头的变量是semi-private变量，可以通过实例._attrname访问，双下划线开头的是super-private，无法访问，不过可以通过实例._类名__attrname访问，semi-private被存储在__dict__里，而super-private不在。

数据结构算法

学过哪些排序？

我说了冒泡，选择，归并，快排
问了我冒泡复杂度

$O(n^{2})$，开始说成了$O(\frac{n^{2}}{2})$
快排原理，快排比冒泡的优势在哪?

大概说出来了
学过哪些搜索算法？

我说深度优先搜索、二分搜索，就让我选一个讲讲，我讲了二分搜索，其实我对dfs也不算太熟悉
问我学过b树和b+树，红黑树

全不会，后来看了下b+树

面到这面试官说我python基础比较薄弱，感觉凉了一大半

NLP基础

自然语言处理要解决的问题有哪些？

我说了有好多，balabala，但我主要做的是分类，发现问题主要出在词的多义、歧义性上。
问我怎么解决词的多义性

我说了动态词向量，就被追着问什么是动态词向量，还好我没继续吹ELMO，毕竟我都没看过论文，就瞎扯了用多层双向LSTM抽取特征，还顺便和静态词向量对比了下。
怎么判断两个词向量的相似性？

我说余弦相似度，还有用奇异值分解，降维到二维或者三维再看两个词在空间中的位置关系。
人工智能中语音信号处理是用来做什么的？

我说先把语音转成文本，再用NLP去处理抽取人的指令，再送到后台

小结：不要夸口说自己不太懂，只了解名称和大概的东西，一说多了就会被追着问，比如我多嘴说了动态词向量。电话面了20分钟，感觉简历上的都没被问到，就是考察了各个基础知识，我面试前复习的都是nlp的，结果啥都没问到，还好花了一上午看了下排序又自己写了一遍，不然绝对都聊不下去了。HR说帮我问问能不能进复试，然后一晚上都没回话，应该是挂了吧，哎，第一次找实习的面试以失败告终。基础太差！

CEO面

如何搭建一个垃圾邮件分类器，假如邮件内容的语言是从未见过的语种
如果邮件分类器的效果很差，能获得的数据量也不多，如何有效提高准确率
每行读取数据，读入非常大的数据量，如何把重复的行去掉，要求占内存小且速度快(面试官提醒我在unix系统下有一些命令可以做到，可惜我并不会)

其他的都忘了，问的我基本都没答上来，之后hr委婉地告诉我挂了。

扇贝

面试官先问我是怎么学的ai，我说都是自学的。问我做的NLP项目是学校有的，还是我自己找的，当然是我自己找老师搞的了，然后让我说说我做的文本细粒度情感分类的工作，我就把复现论文的算法和过程大概说了说，面试官说我搞的这个和他现在在做的工作还挺像的。

算法题

然后就给了邮件发了两道算法题，让我一个半小时内发解答回去，一道简单一道难。

第一题：

Given a list of intervals, remove all intervals that are covered by another interval in the list. Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.
After doing so, return the number of remaining intervals.

Example 1:
1
2
3
>Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

我看着就觉得像leetcode上之前写过的No.56合并区间就去搜了搜，发现真是原题，题号No.1272，不过是会员可见。之前合并区间用了按区间的左边界排序，这次也用到了，还用到了左边界相等情况下的右边界降序排列，这样如果两个相邻的区间，左边界相等，那么左边的那个区间一定包含了右边的区间，我改造了下快排写了个函数sortlist，然后再判断边界条件是否覆盖，就解决了。

class Solution:
  def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
      # 将list按照左边界升序排，若左边界相同，按右边界降序排
      intervals = self.sortlist(intervals)
      i = 0
      while(i + 1 < len(intervals)):
          l = intervals[i]
          r = intervals[i+1]
          # 如果左右区间相等，pop
          if l[0] == l[1]:
              intervals.pop(i)
              continue

          # 如果左边界相同，则l的右边界必大于等于r的右边界，pop r
          if l[0] == r[0]:
              intervals.pop(i+1)
              continue
          # 如果l的右边界小于r的右边界，不覆盖
          if l[1] < r[1]:
              i += 1
              continue

          else:
              intervals.pop(i+1)
              continue
      return len(intervals)

  def sortlist(self, intervals):
      n = len(intervals)
      if n <= 1:
          return intervals
      else:
          part = intervals.pop(0)
          partl, partr = part[0], part[1]
          left = []
          right = []
          for l in intervals:
              if l[0] > partl:
                  right.append(l)
              elif l[0] == partl:
                  if l[1] < partr:
                      right.append(l)
                  else:
                      left.append(l)
              else:
                  left.append(l)
          return self.sortlist(left) + [part] + self.sortlist(right)

第二题：

给定一个整型的方形矩阵，定义一种路径为从上往下每行取一个元素但相邻两个元素不得取自同一列。
路径的和定义为路径上所有元素的总和。
求所有这样的路径的和当中的最小者。
例如：
arr = [[1,2,3],[4,5,6],[7,8,9]]
所有可能的路径是：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
最小的和是13（ [1,5,7] ）

我还剩30分钟写的这道题，没写出来面试官就给我打电话让我交题了，上一题因为太紧张，浪费了大量时间，mmp，我想着可以用递归，
遍历第一行所有数字：选完第一行的数字后添加到列表path [1]，记录所选数字所在的列col，开始递归剩余的行，选第一行中所有非col列的数字，与上一层path合并，得到 [1, 5], [1, 6]，再重复到最后一行得到 [1, 5, 7], [1, 5, 9], [1, 6, 7], [1,6 8]。然后开始遍历2。
时间复杂度O(n^2)，空间复杂度好像到了阶乘级别？面试官看完我写的第一题说我写得还不错，然后问我第二题的思路，我就说了，他说耗时太久了，然后跟我说用动态规划，主要我算法基础这一块还是很欠缺。。
解答先欠着，复习期末要紧。。。

1 2	class Solution: def minFallingPathSum(self, arr: List[List[int]]) -> int:

两天后如愿拿到了offer：自然语言处理算法工程师实习

百度NLP部翻译组

一面

问简历项目，重点是在seq2seq，attention那一块，被问得千疮百孔，毕竟我生成任务做的不多，写过一个简陋的英语翻译成越南语的练习。

算法题：

file1: 一个中文的文本文件，已分词，词语之间用空格隔开，有10万行
file2: 一个中文的文本文件，已分词，词语中间用空格隔开，有100行
例如，file1的第一行：
我来自中国，我是龙的传人。
词频的定义：
假设词语A后可能出现B、C、D三个词
三个词出现的频次分别是3，5，2。那么，此时
p(B|A)=0.3、P(C|A)=0.5、P(D|A)=0.2
句子概率的定义：
现在有一个句子是ABCD，那么，我们定义句子概率为
P(ABCD)=P(B|A)*P(C|BA)*P(D|ABC)=P(B|A)*P(C|B)*P(D|C)
要求如下：根据file1统计词频，然后计算file2每个句子的概率并输出。

面试官让我先想想思路，然后我就说用字典的嵌套，比如

# 第一个字典的key是出现的第一个词，它的value是一个{他后面出现的词:出现次数}的字典
dict{
  'a' : dict{'b':10, 'c':4} 
  'b' : dict{'c':7, 'd':4}
}

面试官说嵌套字典内存消耗太大，然后给我指点把里面的字典变成list，也就是：

dict{
  'a' : [ ['b', 10], ['c', 4] ]
  'b' : [ ['c', 7], ['d', 4] ]
}

还可以这样

dict{
  'a' : [ 14, ['b', 10], ['c', 4] ] # 就是在list开头保存着总数，之后每次算概率不用再求和了
  'b' : [ 11, ['c', 7], ['d', 4] ]
}

最后我在面试官的指点下写了出来，是上述第二种模式，代码如下

import sys


file1 = open(sys.argv[1], 'r', encoding='utf8')
file2 = open(sys.argv[2], 'r', encoding='utf8')
# create dict
DICT = {}  # key: A value:[["B", 1], ["C", 4]]
for l in file1.readlines():
    sentence = l.split(" ")
    for i in range(len(sentence) - 1):
        if sentence[i] not in DICT:
            DICT[sentence[i]] = []
            DICT[sentence[i]].append([sentence[i + 1], 1])
            continue
        for j in range(len(DICT[sentence[i]])):

            if sentence[i + 1] == DICT[sentence[i]][j][0]:
                DICT[sentence[i]][j][1] += 1
                continue
            DICT[sentence[i]].append([sentence[i + 1], 1])

# calu prob
    for l in file2.readlines():
        sentence = l.split(" ")
        p = 1
        for i in range(len(sentence) - 1):
            if sentence[i] not in DICT:
                DICT[sentence[i]] = []
                DICT[sentence[i]].append([sentence[i + 1], 1])
                continue
            sum_num = 0
            for j in range(len(DICT[sentence[i]])):
                if sentence[i + 1] == DICT[sentence[i]][j][0]:
                    appear_num = DICT[sentence[i]][j][1]
                sum_num += DICT[sentence[i]][j][1]
            p *= appear_num / sum_num
        print("sentence's prob = ", p)

还问了点其他的，记不太清了，我就记得还问了我逻辑斯蒂回归，我也答出来了。

面完后跟我说，一会儿通知我是否二面，两分钟后得到通知，十分钟后二面。

二面

又问了我seq2seq，attention，面试官要求比上一个高，直接和我说感觉我不太熟悉这方面，然后要直接考察我代码工程能力。

题目很简单，有序数组被旋转，例如[1,2,3,4,5] -> [4,5,1,2,3]，找出旋转的位置index

这就是leetcode 153原题寻找旋转排序数组中的最小值，因为旋转的位置必定是最小值，我当时看到是我做过的原题很兴奋，开始尝试回想写过的代码，然而我失算了，我不但没回想起来，还把自己逻辑搞的一团糟，边界条件判断完全失去理智，导致我写的很辣鸡，面试官指出好几处我写的错误。最后面试就结束了，我复制了我写的代码到ide上跑，发现漏洞百出。下面是我找到的之前看的人家的解答

# [1,2,3,4,5] -> [4,5,1,2,3]
class Solution:
    def findMin(nums):
        if len(nums) == 1:
            return nums[0]
        left = 0
        right = len(nums) - 1

        if nums[right] > nums[0]:
            return nums[0]

        while right >= left:
            mid = (left + right) >> 1

            if nums[mid] > nums[mid + 1]:
                return mid + 1

            if nums[mid - 1] > nums[mid]:
                return mid

            if nums[mid] > nums[0]:
                left = mid + 1

            else:
                right = mid - 1

过了一周也没收到通知，我以为挂了，二面发挥的很不好，这么简单的一道题居然没写出来，所以教训是看到做过的题最好也当成没见过来好好从头分析，不然不但没回想起来，还可能把逻辑搞乱了，彻底写不出来，平常刷题时分析问题的思路一定要有。面试官都会问你有没有思路，如果思路对了，即使代码写不出完整的问题也不是很大，如果思路都一团混乱基本就凉了。之前有看过同样面百度过了一个月才收到offer的，我以为不会发生在我身上，谁知道真的就发生了，而这时我已经在扇贝上班一个多星期了，刚上手了一个项目正做得起劲，所以就婉拒了，实在很可惜，如果早点发offer我肯定会去百度的。

字节跳动

面的岗位是aml机器学习平台算法实习生

一面

先问了自我介绍，简历项目介绍，然后主要考察了编程算法计算机基础，算是除了赛舵CEO那一面里最难的了。

算法题

如何判断一个单链表是否有环。

我用set()记录每个节点的id，然后如果发生当前节点的id出现在set里了，即是有环。

问时间、空间复杂度？

面试官说有更好的办法，让我回去再看看
如何找到环的开头节点？

线性扫描，我判断当前节点的next是否在set里，如果是，那么当前节点就是环的开头

面试官说这样也行吧，说我这道题没思路的话确实也想不出来更好的办法

后来网上搜了可以用两个速度不一样的指针，如果快指针从后面追上了慢指针就说明有环，如果快指针到了null还没追上就是无环。
学过什么排序算法？

我说快排，归并，然后让我写了下快排。

问时间、空间复杂度？

能不能优化快排，把空间复杂度降下来？

让我原地做快排，我之前写过可因为递归的方法写起来很方便就没写过原地快排了，憋了半天没写出完整的，最后时间到了。回头我复习了下，应该是这么写

def quick_sort_in_place(array, lo, hi):
    if lo >= hi:
        return
    left = lo
    right = hi
    pivot = array[lo]
    while left < right:
        while left < right and array[right] > pivot:
            right -= 1
        array[left] = array[right]
        while left < right and array[left] < pivot:
            left += 1
        array[right] = array[left]
    array[left] = pivot

    quick_sort_in_place(array, lo, left-1)
    quick_sort_in_place(array, left+1, hi)

学没学过计算机网络，了解tcp，http协议吗？

这个我真不会
python的值传递和引用传递？

答出来了，然后他指出我上面写的原地快排就是只传递了值，没法改变原本的list，这时候我才发现。。还得加上左边界和右边界的索引。

时间差不多一个小时了，最后问我有什么想问的，我感觉我基本没了，就问了问我投的这个岗位主要做什么，然后结束了。

二面

没想到还有二面，面试官很和蔼，打开视频的时候还说：“哎，你真人比照片帅很多嘛！”，hhhh就喜欢听这种实话，对西电似乎印象很好，跟我说这边有很多我的学长，然后就开始正题了。

算法题：

给一个head，翻转单链表

我用了三个指针，p1 p2 p3，开始把head的next指向None，然后把p2的next指向p1，然后把三个指针右移，p3是为了防止p2的next指向p1后找不到原本的next了，如果将p2指向p1后当前的p3为None，那就大功告成，可以直接跳出循环了。

class Node:
    def __init__(self, item):
        self.item = item
        self.next = None

def reverselist(head):
    if head is None or head.next is None:
        return head

    p1 = head
    p2 = p1.next
    p3 = p2.next
    head.next = None
    while p2:
        p2.next = p1
        p1 = p2
        p2 = p3
        if p3 is None:
            break
        p3 = p3.next
    return p1

后来在网上看到一个用递归的解法如下：

def revervelist(head):
  if head == None or head.next == None:
    return head
  
  newhead = reverselist(head.next)
  t1 = head.next
  t1.next = head
  head.next = None

  return newhead

接着问了很多东西，只能写些我还记得的：

L1和L2正则化，为什么能减少过拟合？

我说能惩罚参数，让参数变小或置零，降低模型复杂度，阻止模型完全拟合训练集，他又问为什么参数变小了就能减小过拟合，我没答出来
layernorm有什么用？

答：均值归零，方差归一，加快训练速度
self-attention运算过程

写过，答出来了
手写lstm

写出来了
loss.backward()是怎么把梯度反向传播回去的

答：根据计算图的边进行链式求导。又接着问我每一步运算它通过什么机制，怎么就知道该跟谁求导，我没答出来
当用pytorch生成一个tensor时底层如何分配空间

不会。。。
pytorch里的矩阵相乘底层是如何实现的

不会。。。
python底层是怎么用c实现的

不会。。。然后面试官问我学过编译原理没，我说我学电子的，没学过这个。。。
python的多线程，多进程，GIL锁

学过皮毛，忘掉了，没答出来
为什么激活函数很多用relu不用tanh和sigmoid

tanh和sigmoid在W*x值很大时，梯度几乎为0，无法进行梯度下降。接着问我relu为什么要把小于0的就砍掉，我不知道了。
为什么会发生梯度消失

层数多了之后，很多小于1的grad连乘，数值下溢
残差层有什么作用

方便梯度的反向传播，防止梯度消失

我记得问得不止这些，不过我不记得了，当时已经被问晕了，过了一段时间我才写了这篇文章。

二面面了也有四五十分钟，结束后hr跟我说，他们讨论过了，要让我再去面一下NLP岗，综合讨论一下，我？？？我当时投的就是nlp岗，他说技术团队评估后给我面的岗位是aml机器学习平台算法实习生，我认了，这岗位说是做机器学习中台，感觉比较像后端+提供算法模型？面完发现我不太了解计算机的底层和计算机网络，还是偏向nlp模型和算法稍微熟悉些，觉得我可能还是更适合去面nlp岗吧。

NLP岗

算法题：求sqrt(x)

我用暴力求解出来之后，面试官问我能不能用牛顿迭代法解，我不会，他就给我讲了讲让我写，我一时半会还是没听懂，我不知道到底是我理解出了问题还是他说的不够清晰，反正然后面试官就很不耐烦地挂了，跟我说今天的面试到此结束，谢谢参加我们的面试，全程不到35分钟，这是我挂得最快也最惨的一次。。。。

下面是我复习之后做出的解答，用牛顿法和二分法求平方根，无论是速度还是精度牛顿法都完爆二分法，google的时候还看到了一个更魔幻的平方根求法，不过我看不懂，网上有很多解释也不是很清楚，暂且放在这。

def sqrt_newton(y):
    '''牛顿迭代法'''
    error = 1e-6
    def f(x):
        return x**2 - y
    x = y
    n = 0
    while abs(f(x)) > error:
        x = x - f(x) / (2 * x)
        n += 1
    return x, n

def sqrt_binary_divide(y):
    '''二分法'''
    error = 1e-6
    n = 0
    def f(x):
        return x**2 - y
    low = 0
    up = 1 if y <= 1 else y
    mid = (low + up) / 2
    while abs(f(mid)) > error:
        if mid ** 2 > y:
            up = mid
        else:
            low = mid
        n += 1
        mid = (low + up) / 2

    return mid, n
  
if __name__ == '__main__':
    y = 2
    sqrty, times = sqrt_newton(y)
    # 根号2实际值 = 1.414213562373
    print('result', sqrty, '迭代次数', times)
    # result 1.4142135623746899 迭代次数 4

    sqrty, times = sqrt_binary_divide(y)
    print('result', sqrty, '迭代次数', times)
    # result 1.4142136573791504 迭代次数 21

魔幻解法

float Q_rsqrt( float number ) { 
	long i; float x2, y; const float threehalfs = 1.5F;
	x2 = number * 0.5F; 
	y = number; 
	i = * ( long * ) &y; // evil floating point bit level hacking 
	i = 0x5f3759df - ( i >> 1 ); // what the fuck? 
	y = * ( float * ) &i; 
	y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration 
	// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
	#ifndef Q3_VM #
	ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE?
	#endif
	#endif return y; 
}