依图科技面经分享
今天我在一天内去面了两家公司，出乎意料的都当场拿到了offer，因为之前一个offer都还没有，今天应该算是十分具有意义的一天,所以回来打算新开一贴。之前的一系列面经转
https://www.nowcoder.com/discuss/24900
约的上午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<X<100
这题我在5分钟内写出了递推式并给出了快速幂优化后的时间复杂度，面试官很满意。
二面面试官主要跟我聊简历上的几个项目，他好像不能理解词向量的形式，反复解释了很多遍，问的问题都比较简单，有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中的所有数
主要是这题表述有点模糊，理解清楚题意后就想起来解法，很快解了出来，然后写代码，但还是漏了一个细节造成一个BUG被面试官发现了
随后随便聊天，我问了一个问题，就是华为现在要用开发历史数据中挖掘信息来提高软件工程师效率，这个事能否做，面试官很鄙视的向我解释了这个事情做不了，说了一大堆，原因我其实也知道。。后来我说我们现在确实让华为提供数据和一个想做的细节点的LIST。
面完HR进来就说通过了面试问我何时能入职。
