依图科技SP专场算法岗面经

昨天刚刚结束第三面，应该是没有技术面了，都是现场面，发个帖子回馈牛友，顺便攒攒RP嘻嘻~~~

1面 07/31

1.自我介绍：略。

2.介绍项目：说的是我的一个数据挖掘项目，详细说明算法模型结构，一共试过哪些模型，为什么选用这个模型，数据清洗难点，特征工程怎么做的（非数值型构建三元组+TransR生成embedding，数值型分箱+one-hot，特征组合，构建梯度特征，归一化）。

3.算法题：（都是现场手撕，思考时间基本上是5分钟以内，但是可以边写边想思路）

一.两字符串a,b,求a+b。先填充然后再进位加，比较简单。

二.N皇后问题。（LeetCode 52）当时忘记了现场写了个低效版本然后在面试官的提醒下优化了一下。

附官方题解：

在建立算法之前，我们来考虑两个有用的细节。

一行只可能有一个皇后且一列也只可能有一个皇后。

这意味着没有必要再棋盘上考虑所有的方格。只需要按列循环即可。

 对于所有的主对角线有 行号 + 列号 = 常数，对于所有的次对角线有 行号 - 列号 = 常数.

这可以让我们标记已经在攻击范围下的对角线并且检查一个方格 (行号, 列号) 是否处在攻击位置。

从第一个 row = 0 开始.

循环列并且试图在每个 column 中放置皇后.

    如果方格 (row, column) 不在攻击范围内
        在 (row, column) 方格上放置皇后。
        排除对应行，列和两个对角线的位置。
        If 所有的行被考虑过，row == N
            意味着我们找到了一个解
        Else
            继续考虑接下来的皇后放置 backtrack(row + 1).
        回溯：将在 (row, column) 方格的皇后移除.

class Solution:
    def totalNQueue(self,n):
        def is_not_under_attack(row,col):
            return not (rows[col] or hills[row-col] or dales[row+col])
        
        def place_queue(row,col):
            rows[col] = 1
            hills[row-col] = 1
            dales[row+col] = 1
        
        def remove_queue(row,col):
            rows[col] = 0
            hills[row-col] = 0
            dales[row+col] = 0
        
        def dfs(row,count):
            for col in range(n):
                if is_not_under_attack(row,col):
                    place_queue(row,col)
                    if row + 1 == n:
                        count += 1
                    else:
                        count = dfs(row+1,count)
                    remove_queue(row,col)
            return count
        
        rows = [0] * n
        hills = [0] * (2*n-1)
        dales = [0] * (2*n-1)
        return dfs(0,0)

4.逻辑题：

两个人拿石头，一个人可以拿1或者2个，问什么情况下第一个拿的人必胜？

找规律：1，2个石头的时候第一个人必赢（先拿一个，先拿两个），3个石头的时候第二个人必赢，推下去得出规律，n为3的倍数的时候第二个人必赢，不为n的倍数的时候第一个人必赢，先拿n%3个石头。

5.基础知识细节。LightGBM的GOSS算法和EFB算法以及和XGBoost的区别，这个在我之前的博客里有就不写了。

2面 07/31

1.自我介绍（吐槽一下，二面面试官很不友善，感觉时间很紧的样子）。

2.命名实体识别项目详细说一下，输入是什么输出是什么，模型结构，难点，评判指标。回答的很差，因为问得很细但是项目复习不到位。

3.算法题：

第一题螺旋矩阵做过直接过。（LeetCode 54）

class Solution:
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return []
        res,i,j,di,dj=[],0,0,0,1
        for _ in range(len(matrix)*len(matrix[0])):
            res.append(matrix[i][j])
            matrix[i][j] = None
            # 走到头了
            if matrix[(i+di)%len(matrix)][(j+dj)%len(matrix[0])] == None:
                di, dj = dj, -di
            i += di
            j += dj
        return res

第二题基本计算器虽然也做过但是条件判断的好好思考不然容易出错。

class Solution:
    def calculate(self, s: str):
        def compare(op1,op2):
            return op1 in ['*'] and op2 in ['+','-']
        def getvalue(a,b,op):
            if op == '+':
                return a+b
            elif op == '-':
                return a-b
            else:
                return a*b
        def process(data,opt):
            op = opt.pop()
            b = data.pop()
            a = data.pop()
            data.append(getvalue(a,b,op))
        data = []
        opt = []
        i = 0
        while i < len(s):
            if s[i].isdigit():
                start = i
                while i+1 < len(s) and s[i+1].isdigit():
                    i += 1
                data.append(int(s[start:i+1]))
            elif s[i] == ')':
                while opt[-1] != '(':
                    process(data,opt)
                opt.pop()
            elif not opt or opt[-1] == '(':
                opt.append(s[i])
            elif s[i] == '(' or compare(s[i],opt[-1]):
                opt.append(s[i])
            else:
                while opt and not compare(s[i],opt[-1]):
                    if opt[-1] == '(':
                        break
                    process(data,opt)
                opt.append(s[i])
            i += 1
        while opt:
            process(data,opt)
        return data.pop()

4.逻辑题

平均需要抛掷多少次硬币，才会首次出现连续的两个正面？（想岔了没想出来）

假设连续两个正面的期望是E，那么，先看第一次跑硬币：

1.如果抛到反面，那么还期望E次，就是E+1次；

2.如果抛到正面：第二次正面，那么结束，总数是2，如果是正面，那么相当于重头来过，总数是E+2次。

故：E = 0.5(E+1)+0.25 * 2+0.25 * (E+2)

解得：E = 6

5.基础细节。特征工程一般怎么做，Transformer的Multi-head attention计算细节。

总结一下，二面项目回答的很差，然后数学题没做出来，本来以为凉了，结果居然隔了2礼拜还给了我3面，我自己估计呢是因为SP考核没过，但是给了我一个普通offer的机会。

3面 08/14

1.自我介绍。

2.算法题：

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。要求求和复杂度为O(1)。

思路就是构建一个DP数组（原地修改也行，就是注意一下边界就好），dp(i)(j)表示原矩阵0,0到i,j这片区域的和。

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        self.m = len(matrix) 
        self.n = 0 if self.m == 0 else len(matrix[0])
        self.dp = [[0] * (self.n+1) for _ in range(self.m+1)]
        for i in range(1, self.m+1):
            for j in range(1, self.n+1):
                self.dp[i][j] = matrix[i-1][j-1] + self.dp[i-1][j] + self.dp[i][j-1] - self.dp[i-1][j-1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = self.dp[row2+1][col2+1] - self.dp[row1][col2+1] - self.dp[row2+1][col1] + self.dp[row1][col1]
        return res

3.项目细节，就是一个一个点扣，问的还是蛮细的要是对自己项目不了解就会出问题（还好专门复习了一下）。

4.数学题：

某大公司有这么一个规定：只要有一个员工过生日，当天所有员工全部放假一天。但在其余时候，所有员工都没有假期，必须正常上班。这个公司需要雇用多少员工，才能让公司一年内所有员工的总工作时间期望值最大？

假设一年恒定365天，每个员工的生日都概率均等地分布在这365天里。

对E求导，得到n约等于365。（总感觉这个数学题醉翁之意不在酒。。。）

5.闲聊时间，部门是干嘛的啊，文本生成你现在主要用什么模型，你做了这么些时间NLP了，对这个领域最大的感受是什么这样的。

秋招到现在面的公司也就3家，第二家完整面完的公司，现在心态也淡定了很多，继续努力，希望能在9月初结束秋招，有个好结果，UPUP！

#依图科技##面经##算法工程师##校招#