依图科技面经分享

今天我在一天内去面了两家公司，出乎意料的都当场拿到了offer，因为之前一个offer都还没有，今天应该算是十分具有意义的一天,所以回来打算新开一贴。之前的一系列面经转

约的上午9点半面百姓网，下午2点面依图科技，虽然百姓网现在没落了，但有机会去涨涨面试经验还是可以的，面试官也没让我失望，出了一些有意思的题，下面分享一下。

因为早班车堵车严重，我9点50才到，首先进行感觉这公司好多女员工。

一面面试官拿着我的笔试试卷和简历进来，依个问我做错的题。首先是最短路径算法你理解哪些？答：floyd, dijkstra,

bellman-ford,spfa，分别适用什么场景？答：除了floyd是计算两两最短路，其它都计算单源最短路径。复杂度各是多少？答：一堆分析。然后让我把笔试中写的复杂度过高的一题再重新优化了一下。

两道概率题：

1. 一个人在沙漠中车抛锚了，已知每天有车经过的概率是60%，问他在前8个小时获救的概率是多少？

2. 扫雷游戏：在一个局部的情形中，点开了1和2，X表示未知，问A,B,C,D中哪一点是雷的概率最大？

X X X X X

A 1 B 2 C

X X D X X

两题我都没答对，承认我的概率论学的真心不好。后来面试官给我讲了解法，豁然开朗。一道codeForces原题(我没做过)：从N个数中可放回的抽取B次，问B次取出的数的和被X模余K的方法总数是多少，N<50000,B<10E9,K

二面面试官主要跟我聊简历上的几个项目，他好像不能理解词向量的形式，反复解释了很多遍，问的问题都比较简单，有TF-IDF,余弦相似度，分词工具等等。面完已经12点多了，在全家随便买了个饭吃后直奔依图。到了感觉技术氛围很浓厚，工位是像网吧一样连成一排的，桌面上各种纸笔凌乱。被安排在咖啡厅面试，但因为面试官有事，直到下午2点半才开始，我都困得不行了，这里要感谢HR给我点了一杯冰拿铁提了提神。

一面面试官是个看起来就觉得很聪明的人，或者说长的很聪明的人，先问了问3个项目。因为我直说机器学习这块我正在恶补，他就说那就不问机器

学习，直接出算法。

第一题很简单：有序数组从中间某点隔开，右边的放到左边，然后问在这个数组中怎么进行二分查找。讲了思路后手写代码

第二题第一问也很简单：

一个矩阵上每一点都有分值，从左上角走到右下角，只能往下或者往右，问走一遍能够取到的最大分值，简单DP一下。第二问比较有难度，问走两遍能够取到的最大分值，大概花费了15分钟才解出来，面试官很满意。

二面面试官看起来也蛮聪明，上来啥都不说直接出算法题

第一题：有一个数组，让找到两个不重复的连续子序列A,B ，求Max(Sum(A)-Sum(B)。 3分钟解出，10分钟写完代码

第二题：有一个GOD（）函数，能够以C的概率返回0，以1-C的概率返回1，C未知，让利用GOD（）构造P（x )实现以X的概率返回0,1-X的概率返回1，不能使用随机函数

我说了两个解法，但都是错的，因为还是用了随机函数。最后面试官说了解法，感觉trick痕迹太明显了，正常根本想不出来啊。

三面主管面，首先让我讲一个我觉得最值得讲的项目，我选了股票舆情分类来讲，但应该是被鄙视了，面试官言外之意就是个二分类而已。然后还问了些为什么不尝试用深度模型之类。然后又出了道算法题：

LeetCode原题：

有一个集合A包含了一些数，输入N，求元素个数最小的集合B，使得A并B后内的数组合相加能够组成1到N中的所有数