一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2304|回复: 20
收起左侧

snapchat面经

[复制链接] |试试Instant~ |关注本帖
厉害的超人 发表于 2016-9-13 15:51:59 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Snapchat - 网上海投 - Onsite |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
楼主一直在LA一小公司工作了三年多,公司要垮了,于是准备了半年多找新工作。
上周三onsite了snapchat,可是到今天晚上(周一)都还没收到回复(当时说上周三晚上或周四就会回复),现把面经发上来攒攒人品。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
7月底的时候在snapchat网站海投了software engineer职位,很快就被HR联系安排video面试(不知咋的没有OA,运气吧)。. 1point 3acres 璁哄潧

电面:
8月初的时候一国人墨镜大哥(IOI金牌得主,后来onsite得知)video面我。
一来就问用过snapchat没有,怎么改进。我当时说要是能设置发给朋友的snap的时效(比如24小时内)就好了,其实我也就随便想的,结果接下来半小时就一直在讨论怎么实现我想要的功能(类似系统设计)。完了还剩20多分钟就是在线做一道类似浏览器输入keyword搜索给出提示这样的题。自然用trie来做,和leetcode 208差不多,不同的是输入prefix,返回所有单词(dfs或bfs均可)。

video面完后等了一个多星期才发信给我说onsite,我回复了接下来一周的available的时间后,又等了一个多星期然后突然收到信说第二天onsite,我正好有安排就推迟了两周到九月份(心想咋不早点通知)。

onsite:
我10:45准时到了,HR让我等着,等到11:30了终于第一位面试官来了,是位美国大哥,一来就说抱歉来得实在是太晚了。我当时还以为我的面试取消了。
也不问什么背景了,稍加介绍就做一个decision tree的题,题不难,就是输入一组数和一组有weight的decision trees,然后算出一个score来,非常straight forward一步步在白板上implement具体的函数实现。做完了小哥说挺满意再问了一两个小问题就已经12点了。

中午12点多和一国人小哥吃饭,全程中文(就是他说的video面我的是个牛人)。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
下午1:00面试官老印,稍加介绍后问我以前遇到的challenging project,这个我面其他的说过很多遍了,最多3、5分钟我就能说完,可是正当我说到关键challenging的地方时,老印说好了我们来做题吧(第一次遇到只讲了两三分钟就被打断了的情况),但是我说我再讲几句话就完了,他不爽的让我讲完了。这是一个无边界的迷宫题,给出interface:void move()和bool checkMoveSucucess(),然后返回能不能到达目的地。在白板上用dfs做,做出了一个bug就是backtracking的时候忘了moveBack()了(因为平时做题没有什么move的动作,只需检查每一格是不是到过就行了),他提示后改了。然后一道shortenUrl的设计题,要求就是用分布式的,他问了很多细节,比如问key放在那台机器上,我说可以用%N来获取,然后问万一添加一台机器%(N+1)就要移动很多数据,我说用consistent hashing就能解决,最后他挺满意的出去了(也没啥时间说其他的了)。
. 鍥磋鎴戜滑@1point 3 acres
2:00终于迎来了国人小哥。人非常不错,聊聊背景就开始问一道geo fence的题目,要求返回给定(lat lon)附近的events吧,是一个范围,自己定义怎么表示。这道题不用编程,就讲思路。我先说可以直接brute force,马上他便问events遍布美国不计其数,brute force是肯定不行的。当然不行,我就把quadtree原理和实现讲了一遍,看起来他挺满意。然后就做一道类似knight move的题目,给了一个函数list nextMoves(),返回所有下一个有效的move,棋盘无穷大,输出到目的地的最短路径。bfs就可以做好,另开一个hash表记录上一步。follow-up是输出所有的最短路径。用hash表记录上一步所有可能的位置,然后dfs返回所有路径。这道题是在电脑上编译通过的。讲完follow-up时已经没时间了,问了个小问题国人小哥就走了。

3:00一欧洲大哥(听口音就知道是欧洲那边的),挺爱开玩笑的。没怎么聊背景就开始问问题。他打开snapchat的discover page,随便打开比如cnn channel,然后要在里面某些page加入一个poll问题,问怎么实现(系统设计),问得很具体,貌似需要马上就能implement出来,我的每一个想法他都会提问看实不实际,最后数据库也需要用nosql来保存。这部分我觉得答得一般般。然后开始在电脑上做题:frog jumping river,和这道题几乎一样:http://www.mitbbs.com/article_t1 ... 763_31443769_1.html
A frog is trying to jump across a river by hopping on rocks in between the left and right banks.
At each step, the frog can choose 3 speeds to jump to the next rocks (not necessary neighbor), increase 1 speed, decrease 1 speed or keep the same speed.
You are given a list of rock's positions (sorted), and need return if the frog can jump cross the river.. From 1point 3acres bbs
The frog starts from stone position 0, and the initial speed is a given value.-google 1point3acres
做了很多dp的题,这道却没见到过,我就给他说肯定dp可以做出来,想了快10分钟我当时一直犹豫dp[n]每个点会有不同速度,究竟存速度还是bool值。其实换成二维的dp[n][speed]很快就能做出来了。他说不一定要用dp啊,只要你能解出来就行了,我立马在电脑上写了个dfs,test了几个case都行。然后他说初始速度为1呢或者负数,结果马上stack overrflow了,我说当然可以加protection。后来时间就快到了,他便说这样已经不错了。然后问了一个问题后就结束了。其实这轮觉得这个欧洲大哥人很好说话,一直都在和我交流。

面完后心情不错直接去沙滩玩了会儿,这里提醒大家千万别被沙滩那里的黑人小哥骗了,他们拿张唱片来签个名给你然后让你给点小费。我当时心情不错就给了5块,之后就一堆黑人过来了,我就再给了另两个分别5块,最后说no more!

评分

1

查看全部评分

 楼主| 厉害的超人 发表于 2016-9-14 10:50:32 | 显示全部楼层

. Waral 鍗氬鏈夋洿澶氭枃绔,多谢!承你吉言今天收到offer了
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-14 11:57:03 | 显示全部楼层
厉害的超人 发表于 2016-9-14 10:50
多谢!承你吉言今天收到offer了

cong!沾沾lz的喜气。。
回复 支持 反对

使用道具 举报

 楼主| 厉害的超人 发表于 2016-9-14 13:16:30 | 显示全部楼层
pawprinter 发表于 2016-9-13 19:57
cong!沾沾lz的喜气。。

我觉得多多和面试官交流,只要谈得愉快就比较容易拿到offer。我面的时候没有做到bug free,也有dp没想出来的题,最后拿到了offer,运气占了很大成分。准备明天就签他家了。最后祝大家都能拿到心仪的offer!
回复 支持 反对

使用道具 举报

gamesover 发表于 2016-9-14 23:01:15 | 显示全部楼层
frog jumping river这个问题可以找数组2个数之差啊,比如
       a=[ 0, 1, 3, 5, 6, 8, 12, 17]. 1point 3acres 璁哄潧
a_diff =    [1,2, 2,  1, 2, 4,  5]
     b=[0, 1, 2, 3, 4, 8, 9, 11]
b_diff=[ 1, 1, 1, 1, 4, 1, 2]
. from: 1point3acres.com/bbs
然后查看任何a_diff和b_diff数组相邻2个数之差是不是属于{-1,0,1}情况的一种,是的话pass,不是的话fail
不知道是不是有bug
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-9-14 23:09:02 | 显示全部楼层
厉害的超人 发表于 2016-9-14 13:16
我觉得多多和面试官交流,只要谈得愉快就比较容易拿到offer。我面的时候没有做到bug free,也有dp没想出 ...

Have you already left your current employer? there is no handover in US?
回复 支持 反对

使用道具 举报

yuanxiehuang 发表于 2016-9-16 05:18:37 | 显示全部楼层
我也是楼主的那个欧洲的大哥面我的,我都写出了dp的解法,那个欧洲的大哥还是给了挂了...
回复 支持 反对

使用道具 举报

 楼主| 厉害的超人 发表于 2016-9-16 15:43:07 | 显示全部楼层
yuanxiehuang 发表于 2016-9-15 13:18
我也是楼主的那个欧洲的大哥面我的,我都写出了dp的解法,那个欧洲的大哥还是给了挂了...

你是onsite也遇到一个欧洲大哥出同样的这道frog jumping river的题?
回复 支持 反对

使用道具 举报

 楼主| 厉害的超人 发表于 2016-9-16 15:44:00 | 显示全部楼层
leonardcohen 发表于 2016-9-14 07:09
Have you already left your current employer? there is no handover in US?

not yet. I will leave my current company at the end of this month
回复 支持 反对

使用道具 举报

 楼主| 厉害的超人 发表于 2016-9-16 17:40:31 | 显示全部楼层
gamesover 发表于 2016-9-14 07:01.鐣欏璁哄潧-涓浜-涓夊垎鍦
frog jumping river这个问题可以找数组2个数之差啊,比如
       a=[ 0, 1, 3, 5, 6, 8, 12, 17]
a_diff = ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
不是这样,速度可以往上加,即使两块石头相隔很远,速度足够大也能跳过去。那个链接的Ilikemac回帖已基本给出正确答案了。
现在给出dfs和dp的解,可能有bug,没做深度测试。
  1. #include <vector>. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  2. #include <iostream>
  3. . 1point 3acres 璁哄潧
  4. using namespace std;

  5. //basically we can use a dfs to solve the problem. from: 1point3acres.com/bbs
  6. bool jumpDfs(vector<bool> & stone_pos, int pos, int speed) {
  7.     int n=stone_pos.size();
  8.     if(pos==n-1) return true;
  9.     if(!stone_pos[pos] || pos>=n || speed<1) return false;
  10.     for(int s=speed-1; s<=speed+1; ++s) {
  11.         if(jumpDfs(stone_pos,pos+s,s)) return true;
  12.     }
  13.     return false;
  14. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  15. //assume init_speed >= 0-google 1point3acres
  16. bool canJumpOverDfs(vector<int> & stone_idx, int init_speed) {
  17.     //convert stone stone_position to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}
  18.     int n=stone_idx.back()+1;. visit 1point3acres.com for more.
  19.     vector<bool> stone_pos(n);
  20.     for(int p:stone_idx) stone_pos[p]=true;.1point3acres缃
  21.     return jumpDfs(stone_pos,0,init_speed);
  22. }

  23. //dfs has a lot repeated calculation, we can use dp to avoid it. from: 1point3acres.com/bbs
  24. //assume init_speed >= 0
  25. bool canJumpOverDp(vector<int> & stone_idx, int init_speed) {
  26.     //convert stone stone_position to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}. 鍥磋鎴戜滑@1point 3 acres
  27.     int n=stone_idx.back()+1;
  28.     vector<bool> stone_pos(n);
  29.     for(int p:stone_idx) stone_pos[p]=true;

  30.     //assume every stone_position is a stone, the max speed at the end is less than
  31.     int safe_max_speed=init_speed+n-1;
  32.     //the actual max speed could be calculated by:
  33.     //(init_speed+1) + (init_speed+2) + ...  + max_speed = n;. 鍥磋鎴戜滑@1point 3 acres
  34.     // max_speed < safe_max_speed

  35.     //dp[p][s] means at stone_position p, if there exists a case that frog has speed s. visit 1point3acres.com for more.
  36.     vector<vector<bool>> dp(n, vector<bool>(safe_max_speed+1));

  37.     if(init_speed>=1) dp[0][init_speed-1]=true;
  38.     dp[0][init_speed]=dp[0][init_speed+1]=true;
  39.     for(int p=1; p<n; ++p) {
  40.         if(stone_pos[p]) {
  41.             for(int s=1; s<=safe_max_speed; ++s) {
  42.                 //any dp[p][s] can be achived by the previous stone_position p-(s-1) with speed s-1
  43.                 //after the jump, increase speed by 1, then we get stone_position p with speed s;-google 1point3acres
  44.                 //also it can be achived by the previous stone_position p-s with speed s;
  45.                 //and the previous stone_position p-(s+1) with speed s+1
  46.                 if(p>=s-1) dp[p][s]=dp[p-s+1][s-1];.1point3acres缃
  47.                 if(p>=s) dp[p][s]=dp[p][s] || dp[p-s][s];
  48.                 if(p>=s+1) dp[p][s]=dp[p][s] || dp[p-s-1][s+1];
  49.             }
  50.         }
  51.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  52.     //check the last stone_position, if there exists a case that frog has any speed
  53.     for(bool b:dp[n-1]) {
  54.         if(b) return true;
  55.     }
  56.     return false;
  57. }
  58. -google 1point3acres
  59. int main() {
  60.     vector<int> stone_idx={0,1,2,5,6,12};
  61.     //initial speed 5,6,7 are good to reach the end
  62.     cout << "Dfs: init speed=4, can jump over? " << canJumpOverDfs(stone_idx,4) << endl;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  63.     cout << "Dp:  init speed=4, can jump over? " << canJumpOverDp(stone_idx,4) << endl;
  64.     cout << "Dfs: init speed=5, can jump over? " << canJumpOverDfs(stone_idx,5) << endl;. 1point3acres.com/bbs
  65.     cout << "Dp:  init speed=5, can jump over? " << canJumpOverDp(stone_idx,5) << endl;
  66. }
复制代码
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2016-9-17 01:57:30 | 显示全部楼层
能否说说decision tree那道题, 这是coding题还是ml题
回复 支持 反对

使用道具 举报

OaPhoneOnsite 发表于 2016-9-17 02:02:31 来自手机 | 显示全部楼层
恭喜LZ! 各种DFS BFS..
回复 支持 反对

使用道具 举报

yuanxiehuang 发表于 2016-9-17 10:51:39 | 显示全部楼层
厉害的超人 发表于 2016-9-16 15:43
你是onsite也遇到一个欧洲大哥出同样的这道frog jumping river的题?

是的,而且我上来就是出dp解,然后他说能不能用其他的,我说dfs,我觉得他是想用speed是0的case来让我测试,让我stackoverflow, 然后我就stackoverflow了,然后我还调了一会bug,但调完后就写了dp的,也是一遍就过了,一开始确实没考虑到speed等于0的情况也没有想到会出问题,所以真是有点不甘心要是一开始写dp,就肯定不会爆掉就可以一遍过了...
回复 支持 反对

使用道具 举报

 楼主| 厉害的超人 发表于 2016-9-17 11:39:54 | 显示全部楼层
ChrisGates23 发表于 2016-9-16 09:57
能否说说decision tree那道题, 这是coding题还是ml题
. 1point 3acres 璁哄潧
输入是一个float数组和一堆decision tree。每个decision tree每个节点有个参数,用来读取数组中的哪个数;同时还有一个factor,用来比较得出decision该走向哪个子分支(这些基本上都是自己定义)。每棵树根据前面说的参数(数组)往下走,一定会走到某片叶子,每一片叶子都有一个score,那么最后就会得到这棵树的score。现在有一堆树每个都有weight,每棵树都根据那个数组得到各自的分数,然后很简单就能算出一个平均分数来。这道题最后就是输出这个平均分数。很straight forward吧。
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-9-17 23:23:00 | 显示全部楼层

恭喜楼主~ 沾点喜气
回复 支持 反对

使用道具 举报

 楼主| 厉害的超人 发表于 2016-9-20 02:58:36 | 显示全部楼层
最后一道题收录进leetcode了,呵呵。我觉得难度等级应该是medium,因为这个dp很容易理解,只是一开始可能不容易想到,不像有些dp的题看解答要理解就得花很多时间,比如BuyandSellStockIV,Regular Expression Matching等
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-20 03:38:56 | 显示全部楼层
厉害的超人 发表于 2016-9-14 13:16
我觉得多多和面试官交流,只要谈得愉快就比较容易拿到offer。我面的时候没有做到bug free,也有dp没想出 ...

恭喜楼主啊, 能问一下楼主分布式和系统设计那些东西是怎么准备的呢? 完全没学过。。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-20 03:40:21 | 显示全部楼层
厉害的超人 发表于 2016-9-20 02:58
最后一道题收录进leetcode了,呵呵。我觉得难度等级应该是medium,因为这个dp很容易理解,只是一开始可能不 ...

LC那道题DP解O(N^2)好像不让过。。。还是得用dfs
回复 支持 反对

使用道具 举报

 楼主| 厉害的超人 发表于 2016-9-20 06:55:04 | 显示全部楼层
小A要当码农 发表于 2016-9-19 11:38
恭喜楼主啊, 能问一下楼主分布式和系统设计那些东西是怎么准备的呢? 完全没学过。。

这里的信息很有用。http://blog.baozitraining.org/20 ... sign-questions.html
如果你是fresh grad,应该不会考系统设计的东西。我本来平时就要设计些公司的系统,他问到的时候我就直接说我现在的公司是怎么做的,不一定最好,反正是个参考吧,然后再根据一些其他知识说怎样处理最好。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 18:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表