依图科技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!

#依图科技##面经##算法工程师##校招#
全部评论
真的强。。
点赞 回复
分享
发布于 2019-08-15 23:11
这tm是要招神仙吗?
4 回复
分享
发布于 2019-08-15 23:27
春招专场
校招火热招聘中
官网直投
大佬
点赞 回复
分享
发布于 2019-08-15 23:12
真大佬
点赞 回复
分享
发布于 2019-08-15 23:17
真是厉害,对比下来我的三面惨不忍睹
点赞 回复
分享
发布于 2019-08-16 00:53
好奇怪…我每一面问的内容都比楼主少,是我太走运了吗。。。
点赞 回复
分享
发布于 2019-08-16 02:12
依图太硬核了
点赞 回复
分享
发布于 2019-08-16 10:23
昨天三面只面了40分钟是不是凉了。。还没安排hr面
点赞 回复
分享
发布于 2019-08-16 12:07
.......这面经看上去好硬核啊_(:з」∠)_大佬是真的强_(:з」∠)_
点赞 回复
分享
发布于 2019-08-17 18:10
四面HR面
点赞 回复
分享
发布于 2019-08-18 13:58
不是吧,E那题你想错了吧,那E+3,E+4怎么说? E =0.25 * 2+ 0.5(E+1)+0.25 * (E+2)+0.125*(E+3) + 0.0625* (E+4) .....
点赞 回复
分享
发布于 2019-09-18 20:23

相关推荐

15 163 评论
分享
牛客网
牛客企业服务