《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 5082|回复: 20
收起左侧

snapchat面经

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

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

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

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

x
楼主一直在LA一小公司工作了三年多,公司要垮了,于是准备了半年多找新工作。
上周三onsite了snapchat,可是到今天晚上(周一)都还没收到回复(当时说上周三晚上或周四就会回复),现把面经发上来攒攒人品。

7月底的时候在snapchat网站海投了software engineer职位,很快就被HR联系安排video面试(不知咋的没有OA,运气吧)。
. Waral 鍗氬鏈夋洿澶氭枃绔,
电面:.鏈枃鍘熷垱鑷1point3acres璁哄潧
8月初的时候一国人墨镜大哥(IOI金牌得主,后来onsite得知)video面我。.1point3acres缃
一来就问用过snapchat没有,怎么改进。我当时说要是能设置发给朋友的snap的时效(比如24小时内)就好了,其实我也就随便想的,结果接下来半小时就一直在讨论怎么实现我想要的功能(类似系统设计)。完了还剩20多分钟就是在线做一道类似浏览器输入keyword搜索给出提示这样的题。自然用trie来做,和leetcode 208差不多,不同的是输入prefix,返回所有单词(dfs或bfs均可)。

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

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

中午12点多和一国人小哥吃饭,全程中文(就是他说的video面我的是个牛人)。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
下午1:00面试官老印,稍加介绍后问我以前遇到的challenging project,这个我面其他的说过很多遍了,最多3、5分钟我就能说完,可是正当我说到关键challenging的地方时,老印说好了我们来做题吧(第一次遇到只讲了两三分钟就被打断了的情况),但是我说我再讲几句话就完了,他不爽的让我讲完了。这是一个无边界的迷宫题,给出interface:void move()和bool checkMoveSucucess(),然后返回能不能到达目的地。在白板上用dfs做,做出了一个bug就是backtracking的时候忘了moveBack()了(因为平时做题没有什么move的动作,只需检查每一格是不是到过就行了),他提示后改了。然后一道shortenUrl的设计题,要求就是用分布式的,他问了很多细节,比如问key放在那台机器上,我说可以用%N来获取,然后问万一添加一台机器%(N+1)就要移动很多数据,我说用consistent hashing就能解决,最后他挺满意的出去了(也没啥时间说其他的了)。

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.. 1point3acres.com/bbs
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.
The frog starts from stone position 0, and the initial speed is a given value.
做了很多dp的题,这道却没见到过,我就给他说肯定dp可以做出来,想了快10分钟我当时一直犹豫dp[n]每个点会有不同速度,究竟存速度还是bool值。其实换成二维的dp[n][speed]很快就能做出来了。他说不一定要用dp啊,只要你能解出来就行了,我立马在电脑上写了个dfs,test了几个case都行。然后他说初始速度为1呢或者负数,结果马上stack overrflow了,我说当然可以加protection。后来时间就快到了,他便说这样已经不错了。然后问了一个问题后就结束了。其实这轮觉得这个欧洲大哥人很好说话,一直都在和我交流。

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

评分

1

查看全部评分

 楼主| 厉害的超人 发表于 2016-9-14 10:50:32 | 显示全部楼层
ofdk88 发表于 2016-9-13 01:08 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
祝楼主好运

多谢!承你吉言今天收到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 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

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

不是这样,速度可以往上加,即使两块石头相隔很远,速度足够大也能跳过去。那个链接的Ilikemac回帖已基本给出正确答案了。
现在给出dfs和dp的解,可能有bug,没做深度测试。
  1. #include <vector>
  2. #include <iostream>
  3. . 鍥磋鎴戜滑@1point 3 acres
  4. using namespace std;
  5. . visit 1point3acres.com for more.
  6. //basically we can use a dfs to solve the problem. 1point3acres.com/bbs
  7. bool jumpDfs(vector<bool> & stone_pos, int pos, int speed) {
  8.     int n=stone_pos.size(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9.     if(pos==n-1) return true;
  10.     if(!stone_pos[pos] || pos>=n || speed<1) return false;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.     for(int s=speed-1; s<=speed+1; ++s) {
  12.         if(jumpDfs(stone_pos,pos+s,s)) return true;
  13.     }
  14.     return false;. visit 1point3acres.com for more.
  15. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16. //assume init_speed >= 0
  17. bool canJumpOverDfs(vector<int> & stone_idx, int init_speed) {. more info on 1point3acres.com
  18.     //convert stone stone_position to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}
  19.     int n=stone_idx.back()+1;
  20.     vector<bool> stone_pos(n);
  21.     for(int p:stone_idx) stone_pos[p]=true;
  22.     return jumpDfs(stone_pos,0,init_speed);
  23. }

  24. //dfs has a lot repeated calculation, we can use dp to avoid it
  25. //assume init_speed >= 0
  26. bool canJumpOverDp(vector<int> & stone_idx, int init_speed) {
  27.     //convert stone stone_position to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}
  28.     int n=stone_idx.back()+1;
  29.     vector<bool> stone_pos(n);
  30.     for(int p:stone_idx) stone_pos[p]=true;
  31. . From 1point 3acres bbs
  32.     //assume every stone_position is a stone, the max speed at the end is less than
  33.     int safe_max_speed=init_speed+n-1;. 1point 3acres 璁哄潧
  34.     //the actual max speed could be calculated by:
  35.     //(init_speed+1) + (init_speed+2) + ...  + max_speed = n;
  36.     // max_speed < safe_max_speed. from: 1point3acres.com/bbs

  37.     //dp[p][s] means at stone_position p, if there exists a case that frog has speed s
  38.     vector<vector<bool>> dp(n, vector<bool>(safe_max_speed+1));. from: 1point3acres.com/bbs

  39.     if(init_speed>=1) dp[0][init_speed-1]=true;
  40.     dp[0][init_speed]=dp[0][init_speed+1]=true;
  41.     for(int p=1; p<n; ++p) {
  42.         if(stone_pos[p]) {
  43.             for(int s=1; s<=safe_max_speed; ++s) {
  44.                 //any dp[p][s] can be achived by the previous stone_position p-(s-1) with speed s-1
  45.                 //after the jump, increase speed by 1, then we get stone_position p with speed s;
  46.                 //also it can be achived by the previous stone_position p-s with speed s;
  47.                 //and the previous stone_position p-(s+1) with speed s+1
  48.                 if(p>=s-1) dp[p][s]=dp[p-s+1][s-1];
  49.                 if(p>=s) dp[p][s]=dp[p][s] || dp[p-s][s];. visit 1point3acres.com for more.
  50.                 if(p>=s+1) dp[p][s]=dp[p][s] || dp[p-s-1][s+1];
  51.             }
  52.         }
  53.     }
  54.     //check the last stone_position, if there exists a case that frog has any speed
  55.     for(bool b:dp[n-1]) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  56.         if(b) return true;. 1point3acres.com/bbs
  57.     }
  58.     return false;
  59. }

  60. int main() {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  61.     vector<int> stone_idx={0,1,2,5,6,12};
  62.     //initial speed 5,6,7 are good to reach the end
  63.     cout << "Dfs: init speed=4, can jump over? " << canJumpOverDfs(stone_idx,4) << endl;
  64.     cout << "Dp:  init speed=4, can jump over? " << canJumpOverDp(stone_idx,4) << endl;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  65.     cout << "Dfs: init speed=5, can jump over? " << canJumpOverDfs(stone_idx,5) << endl;
  66.     cout << "Dp:  init speed=5, can jump over? " << canJumpOverDp(stone_idx,5) << endl;
  67. }
复制代码
回复 支持 反对

使用道具 举报

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题

输入是一个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没想出 ...
. from: 1point3acres.com/bbs
恭喜楼主啊, 能问一下楼主分布式和系统设计那些东西是怎么准备的呢? 完全没学过。。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-18 14:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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