snapchat面经

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

7月底的时候在snapchat网站海投了software engineer职位，很快就被HR联系安排video面试（不知咋的没有OA，运气吧）。

电面：
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具体的函数实现。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

l 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！

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. 
   
4. using namespace std;
   
5. 
   
6. //basically we can use a dfs to solve the problem
   
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;
    
15. }
    
16. //assume init_speed >= 0
    
17. bool canJumpOverDfs(vector<int> & stone_idx, int init_speed) {
    
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. 
    
25. //dfs has a lot repeated calculation, we can use dp to avoid it
    
26. //assume init_speed >= 0
    
27. bool canJumpOverDp(vector<int> & stone_idx, int init_speed) {
    
28.     //convert stone stone_position to a bool array {1,1,1,0,0,1,1,0,0,0,0,0,1}
    
29.     int n=stone_idx.back()+1;
    
30.     vector<bool> stone_pos(n);
    
31.     for(int p:stone_idx) stone_pos[p]=true;
    
32. 
    
33.     //assume every stone_position is a stone, the max speed at the end is less than
    
34.     int safe_max_speed=init_speed+n-1;
    
35.     //the actual max speed could be calculated by:
    
36.     //(init_speed+1) + (init_speed+2) + ...  + max_speed = n;
    
37.     // max_speed < safe_max_speed
    
38. 
    
39.     //dp[p][s] means at stone_position p, if there exists a case that frog has speed s
    
40.     vector<vector<bool>> dp(n, vector<bool>(safe_max_speed+1));
    
41. 
    
42.     if(init_speed>=1) dp[0][init_speed-1]=true;
    
43.     dp[0][init_speed]=dp[0][init_speed+1]=true;
    
44.     for(int p=1; p<n; ++p) {
    
45.         if(stone_pos[p]) {
    
46.             for(int s=1; s<=safe_max_speed; ++s) {
    
47.                 //any dp[p][s] can be achived by the previous stone_position p-(s-1) with speed s-1
    
48.                 //after the jump, increase speed by 1, then we get stone_position p with speed s;
    
49.                 //also it can be achived by the previous stone_position p-s with speed s;
    
50.                 //and the previous stone_position p-(s+1) with speed s+1
    
51.                 if(p>=s-1) dp[p][s]=dp[p-s+1][s-1];
    
52.                 if(p>=s) dp[p][s]=dp[p][s] || dp[p-s][s];
    
53.                 if(p>=s+1) dp[p][s]=dp[p][s] || dp[p-s-1][s+1];
    
54.             }
    
55.         }
    
56.     }
    
57.     //check the last stone_position, if there exists a case that frog has any speed
    
58.     for(bool b:dp[n-1]) {
    
59.         if(b) return true;
    
60.     }
    
61.     return false;
    
62. }
    
63. 
    
64. int main() {
    
65.     vector<int> stone_idx={0,1,2,5,6,12};
    
66.     //initial speed 5,6,7 are good to reach the end
    
67.     cout << "Dfs: init speed=4, can jump over? " << canJumpOverDfs(stone_idx,4) << endl;
    
68.     cout << "Dp:  init speed=4, can jump over? " << canJumpOverDp(stone_idx,4) << endl;
    
69.     cout << "Dfs: init speed=5, can jump over? " << canJumpOverDfs(stone_idx,5) << endl;
    
70.     cout << "Dp:  init speed=5, can jump over? " << canJumpOverDp(stone_idx,5) << endl;
    
71. }
    

复制代码

ChrisGates23 发表于 2016-9-16 09:57
能否说说decision tree那道题， 这是coding题还是ml题

输入是一个float数组和一堆decision tree。每个decision tree每个节点有个参数，用来读取数组中的哪个数；同时还有一个factor，用来比较得出decision该走向哪个子分支（这些基本上都是自己定义）。每棵树根据前面说的参数（数组）往下走，一定会走到某片叶子，每一片叶子都有一个score，那么最后就会得到这棵树的score。现在有一堆树每个都有weight，每棵树都根据那个数组得到各自的分数，然后很简单就能算出一个平均分数来。这道题最后就是输出这个平均分数。很straight forward吧。

论坛匿名用户 发表于 2016-9-16 15:43
你是onsite也遇到一个欧洲大哥出同样的这道frog jumping river的题？

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

ofdk88 发表于 2016-9-13 01:08
祝楼主好运

多谢！承你吉言今天收到offer了

论坛匿名用户 发表于 2016-9-14 10:50
多谢！承你吉言今天收到offer了

cong！沾沾lz的喜气。。

pawprinter 发表于 2016-9-13 19:57
cong！沾沾lz的喜气。。

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

frog jumping river这个问题可以找数组2个数之差啊,比如
       a=[ 0, 1, 3, 5, 6, 8, 12, 17]
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]

然后查看任何a_diff和b_diff数组相邻2个数之差是不是属于{-1,0,1}情况的一种,是的话pass,不是的话fail
不知道是不是有bug

论坛匿名用户 发表于 2016-9-14 13:16
我觉得多多和面试官交流，只要谈得愉快就比较容易拿到offer。我面的时候没有做到bug free，也有dp没想出 ...

Have you already left your current employer? there is no handover in US?

我也是楼主的那个欧洲的大哥面我的，我都写出了dp的解法，那个欧洲的大哥还是给了挂了...

yuanxiehuang 发表于 2016-9-15 13:18
我也是楼主的那个欧洲的大哥面我的，我都写出了dp的解法，那个欧洲的大哥还是给了挂了...

你是onsite也遇到一个欧洲大哥出同样的这道frog jumping river的题？

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