Snapchat onsite 面经

这篇面试其实是我在1月中旬的时候

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

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

定捧个场，给点米哈！

手快点出去了，接下来正文哈。
Snapchat 是我一位同学的朋友帮忙内推的。先是一轮online test，题目是地里出现过的valid sudoku. 然后就是一轮电面，是sudoku solver.
后来HR很快就通知我去洛杉矶onsite. 那时我因为已经拿了facebook的intern，洋洋得意之际已经1个月木有刷题了，手感其实已经有点生疏了。但本着农村人进城看看的原则也就去了。
先废话，直接开始po面试过程吧。
第一轮是一个大胡子白人，扎着马尾辫。看起来还是挺严肃的。先聊简历，聊了很多。他问到有个我做过的项目，如果想再做一遍的话，问我想怎样改进。编程题是给定一个有向关系图，在给定2个名字，求出这两个人的共同朋友（即2个点能达到的共同节点，类似树的共同祖先）

第二轮是一个白人小哥，人很nice。简单的聊了一下简历后就开始编程。题目是如果通讯录里从某一个名字开始翻转了，请把这个名字找出来。类似leetcode这道题：。这题我二分搜索算法犯了个低级错误，大概被扣分不少。

第三轮是一个印度小哥，这轮开始题目就有点飘了。题目是这样的，通过二维数组来建一颗四叉树。四叉树的叶子节点来自二维数组相邻的上左下右四个方块的值。建树规则是，四个节点的都是0，则父节点也是0，如果四个节点都是1，则父节点也是1.如果四个节点既有0，又有1，则父节点是2.如果四个节点都是2，则父节点是1.(规则有点复杂，一些细节我可能忘记了，但大体是这样）我是用递归的方式建树的。但因为代码量太大，导致我这一轮没完成编码。所以大概挂在这里了。

第四轮，国人小哥。我也不知道他后来有没有放水，反正是挂了。但过程中他给了很多的提示。题目是这样的：一棵树，代表上司和员工的关系，然后每个节点都有一个对应的权值。然后公司开了一个party，为了让员工们更好的交流，有个规定，如果上司去参加party，那么他的直接下属（直接孩子节点)就不去（同理，如果下属去了，直接上司，父节点就不去）。然后设计一个算法，参加party的人的权值总和最高。这是一道动态规划题，思路是每次计算一个员工去的权值之和与不去的权值之和，从叶子开始。

结束之后HR会简单的和你聊会儿天。当然，第二轮和第三轮面试之间有一个午餐，帮忙内推你的人会带你去吃饭。Snapchat专门租了一个地方当餐厅。然后就回家啦。很遗憾，木有见到传说中的CEO。

PS：snapchat的办公室位于洛杉矶 Santa Monica海滩，海滩本身很漂亮，但海滩上各样怪咖，流浪汉都有。还有国内各种卖T恤和纪念品的店，里面的商品大概是义乌进的货吧。如果喜欢这样自由而略带混乱的环境的话，可以考虑去snapchat工作，我是没机会了，就算吃不到葡萄就说葡萄酸的吐槽一下吧。


补充内容 (2016-4-19 03:17):
求大米求大米！

补充内容 (2016-4-19 12:30):
在补充一点，snapchat的面试需要你在电脑上编程，面试官还坐在你旁边，然后你的code需要编译运行通过才可以。而且题目真的很灵活，我在面经里都木有刷到类似的题目。所以，大家平常除了刷leetcode以外，还需要多z...

补充内容 (2016-4-19 12:31):
注意灵活变通

楼主，请问第一题是不是只考虑两个人的direct friends？朋友的朋友算不算?如果朋友的朋友也算的话，那如果找到一个共同朋友，那么这个人的所有朋友也是算共同朋友了？之后这些人的所有朋友也是算共同朋友了？

第二题是字符串翻转还是名字顺序翻转？
1. ["aaron","bob","Jack","Tom","Zack"] -> ["aaron","bob","Zack", "Tom","Jack"]
2. ["aaron","bob","Jack","Tom","Zack"] ->  ["aaron","bob","kcaJ","moT","kcaZ"]

第三题的话，edge 和corner(上左下右 少于4个值) 的点怎么算？
比如，4x4的矩阵有多少个叶子节点？

第四题，是不是可以是多叉树？

感谢楼主！

mooc 发表于 2016-4-28 06:17
1.只考虑直接朋友,
2. 名字顺序翻转，比如aron, bob, case, doug ->case, doug, aron, bob
3. 没有不是 ...

这一题我有个疑惑，根节点是给定的吗？然后根节点的上下左右都是他的儿子，那首先他的子女就只有3个子女吧？比如根节点是下面的7，那么11，是不是就只有3个子女，同时10是不是同时是6和11的子女，也就是一个节点不一定只有一个父节点？那么10只有2个子女？
1   2     3      4
5   6     7      8
9  10    11    12
13 14    15   16

请问楼主，第二个题通讯录那道能说详细一点吗？具体是和Leetcode上哪一题比较像呢？

garderobin 发表于 2016-4-20 08:47
请问楼主，第二个题通讯录那道能说详细一点吗？具体是和Leetcode上哪一题比较像呢？

不好意思，忘记给链接了https://leetcode.com/problems/fi ... tated-sorted-array/。

楼主第一轮找共同好友的题，请问共同好友的祖先们都算是共同好友吗？

楼主，开party那个直接DFS吧。。。基本就是max(root去，root不去)

jiebour 发表于 2016-4-25 07:19
楼主，开party那个直接DFS吧。。。基本就是max(root去，root不去)

同LC 337加个HashMap保存已经DFS过的，避免重复计算。

TsengJuiWang 发表于 2016-4-25 07:43
同LC 337加个HashMap保存已经DFS过的，避免重复计算。

直接bottom up DFS，时间复杂度是O N，为什么需要额外hash map呢

jiebour 发表于 2016-4-25 09:13
直接bottom up DFS，时间复杂度是O N，为什么需要额外hash map呢

我可能第一次是Top-down做的，会超时，后来就拿HashMap保存已经计算过的节点结果。Bottom up咋做的？

1. int dfs(TreeNode* root){
   
2.   if(!root) return 0;
   
3.   int val = 0;
   
4.   if(root->left) val += dfs(root->left->left) + dfs(root->left->right);
   
5.   if(root->right) val += dfs(root->right->left) + dfs(root->right->right);
   
6. return max(val + root->val, dfs(root->left) + dfs(root->right));
   
7. }

复制代码

TsengJuiWang 发表于 2016-4-25 06:15
楼主第一轮找共同好友的题，请问共同好友的祖先们都算是共同好友吗？

这是一个有向图，没有祖先的说法吧？我记得2个节点连接的才算朋友