snapchat onsite

今年就多攒人品了，刚面完的snapchat，飞机延误了…在候机厅写个面经吧。公司周围很漂亮，有海滩，海滩上有漂亮姑娘。面试代码都让在自己电脑上写，写的时候他们也不怎么看，写完了跑给他们看就行，问题都还是挺简单的。
二叉树找路径和；
城市两端

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

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

得比较麻烦的面经题，也包括了刚刚onstie每轮写的代码，希望能帮到有需要的同学吧。都是python写的，轻拍哈哈。

小A要当码农 发表于 2016-10-28 01:37
飞行距离怎么定义呢？ 是指的最小累计高度还是？ 我好像记得有一道关于helicopter的题， 但是那道题规定 ...

就是水平距离加上垂直距离。唔，最开始我写的代码没有memorization的，这是他问的时候随便改的，没仔细想过。

但我觉得好像还是对的吧，我们是搜索过来的，比如说第一次到(i,j)的上一步是(i-1,j)，那我们搜索之后找到了另三个方向的最优解，存在了visited[i][j]里边。唯一可能漏掉的就是往左走可能更好。但这样的话，visited[i-1][j]里的最优解一定也比当前这个更好。不过确实有点说不清楚。。

LumiG 发表于 2016-10-28 02:14
就是水平距离加上垂直距离。唔，最开始我写的代码没有memorization的，这是他问的时候随便改的，没仔细想 ...

感觉这道题只能纯暴力dfs。。。我有一个想法，就是BFS ＋ 最小堆。用一个额外的表记录每个点当前的代价，再用一个最小堆， 每次让目前总累积代价最小的向四周挪动一步。到了一个点如果没访问过，就加入最小堆里面。如果访问过了但是之前代价比现在的代价大，把它从堆里面删掉，更新后再放回去？

小A要当码农 发表于 2016-11-9 12:45
晕。。LSU是啥呀， Map Reduce也不太了解啊。。。能具体说一下题嘛。。。多谢

就是两个文件，里边有很多行，不考虑顺序输出他们不同的行。

比如
1： A; A; B; C
2.   A; B; D

那就输出
- A
- C
+ D

弄个hashmap就行。然后内存放不下的话，就先hash一次，然后对每个bucket里的输出。并行就mapper负责hash，reducer负责输出

应该分别是。。。利特口，113, 332, top k freq,68

城市两端飞一个drone ? 楼主 这是啥题。。。好像和332有区别呀

小A要当码农 发表于 2016-10-27 09:17
城市两端飞一个drone ? 楼主 这是啥题。。。好像和332有区别呀

不是332，其他面经有这题吧，很容易的一个dfs，大概就是二维数组，每个值代表高度。然后一个飞机从一个点飞到另一个点，遇到高楼就要抬高飞行高度，求从A到B的最短飞行距离。

LumiG 发表于 2016-10-27 12:50
不是332，其他面经有这题吧，很容易的一个dfs，大概就是二维数组，每个值代表高度。然后一个飞机从一个点 ...

飞行距离怎么定义呢？ 是指的最小累计高度还是？ 我好像记得有一道关于helicopter的题， 但是那道题规定了飞机还能往高飞，不能下降。 请问你这题是这样的么？

补充内容 (2016-10-28 01:53):
看了看楼主的代码，感觉有点不明白。。visited[i][j]存的是从[i, j]出发到destination的最小距离吧？
那第二次访问到i,j点的时候，visited[i][j]有可能被更新啊，因为第二次的maxHeight可能更小？

补充内容 (2016-10-28 01:53):
打不出[ i ]...

稳如泰山

怎么样，楼主出结果了吗？

楼主有个疑问，既然初始高度，终点高度是给定的，飞机又只能往上飞，那么最终结果不就是高度差+路径长度吗