Snapchat Intern 三轮面经

原帖地址:一亩三分地

12.18背靠背面了两轮,面完觉得bar这么高的公司肯定挂了,没想到给我加面一轮,1.4号面的,1.5号通知说挂了。发一下面经。

第一轮,面试官Waterloo本科,Caltech硕士和博士,搞computer graphics, 就做了一题,是一个computer graphics里的算法,基本和number of islands类似。

第二轮,一个AWS跳过来的小哥,给一个数组,有一个数出现一半以上,其他都只出现一遍,返回这个数。这题和majority number的不同之处是其他数都只出现一遍,需要利用这个条件。followup是,只有一个数出现一次以上,如果出现一半以上,返回这个数,否则返回出现的百分比。这个没想出来,时间到了,小哥讲了一下思路,没仔细听。。

第三轮,发挥的实在太糟糕了。。。是一个manager面的,给一个矩阵,从一个点到另一个点(上下左右对角线都可以走),走k步(可以重复走),有多少种走法。先用BFS写,写好分析时间空间复杂度。然后小哥让提高空间复杂度。我脑子短路了,说DFS的空间复杂度不也是8^k吗。。。小哥无语了。。然后DFS差不多写完,小哥也没说对错,直接让问问问题结束了。

运气比较好,碰到题目都不难,自己水平太差了。。