一亩三分地论坛

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

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

snapchat onsite

[复制链接] |试试Instant~ |关注本帖
LumiG 发表于 2016-10-27 07:30:38 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
今年就多攒人品了,刚面完的snapchat,飞机延误了…在候机厅写个面经吧。公司周围很漂亮,有海滩,海滩上有漂亮姑娘。面试代码都让在自己电脑上写,写的时候他们也不怎么看,写完了跑给他们看就行,问题都还是挺简单的。
二叉树找路径和;
城市两端飞一个drone,求最短路径,好像在哪份面经里扫到过这个题;
一堆文件,每个文件每行是一个字符串,找其中出现过次数最多的字符串;.
一堆字符串,给一个每行的width,把字符串填到每一行里,每次填尽量多的word,两个词至少空一个空格。然后多余的宽度要均匀分到空格里。依稀记得以前在leetcode做过这题,但一时找不到题号了;
snap_diff. 一个很简单的小题目,这轮是manager面的,是聊天为主吧。

snapchat2.zip (11.46 KB, 下载次数: 101)

评分

5

查看全部评分

西法的洛 发表于 2016-10-27 08:36:05 | 显示全部楼层
应该分别是。。。利特口,113, 332, top k freq,68
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-27 09:17:39 | 显示全部楼层
城市两端飞一个drone ? 楼主 这是啥题。。。好像和332有区别呀
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

小A要当码农 发表于 2016-10-28 01:37:12 | 显示全部楼层
LumiG 发表于 2016-10-27 12:50
不是332,其他面经有这题吧,很容易的一个dfs,大概就是二维数组,每个值代表高度。然后一个飞机从一个点 ...

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

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

补充内容 (2016-10-28 01:53):
打不出[ i ]...
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-28 02:14:03 | 显示全部楼层
小A要当码农 发表于 2016-10-28 01:37
飞行距离怎么定义呢? 是指的最小累计高度还是? 我好像记得有一道关于helicopter的题, 但是那道题规定 ...

就是水平距离加上垂直距离。唔,最开始我写的代码没有memorization的,这是他问的时候随便改的,没仔细想过。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
但我觉得好像还是对的吧,我们是搜索过来的,比如说第一次到(i,j)的上一步是(i-1,j),那我们搜索之后找到了另三个方向的最优解,存在了visited[j]里边。唯一可能漏掉的就是往左走可能更好。但这样的话,visited[i-1][j]里的最优解一定也比当前这个更好。不过确实有点说不清楚。。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-28 02:26:47 | 显示全部楼层
LumiG 发表于 2016-10-28 02:14
就是水平距离加上垂直距离。唔,最开始我写的代码没有memorization的,这是他问的时候随便改的,没仔细想 ...

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

使用道具 举报

samuelling 发表于 2016-10-28 02:51:29 | 显示全部楼层
怎么样,楼主出结果了吗?
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-10-29 01:00:16 | 显示全部楼层
楼主有个疑问,既然初始高度,终点高度是给定的,飞机又只能往上飞,那么最终结果不就是高度差+路径长度吗
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-29 03:12:48 | 显示全部楼层
clxy2008 发表于 2016-10-29 01:00
楼主有个疑问,既然初始高度,终点高度是给定的,飞机又只能往上飞,那么最终结果不就是高度差+路径长度吗

听楼主的意思这题好像并没有限制只能往上飞。。。跟之前的不一样
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-29 09:40:45 | 显示全部楼层
samuelling 发表于 2016-10-28 02:51
怎么样,楼主出结果了吗?

应该是拿到了,约我next step了
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-29 09:41:09 | 显示全部楼层
小A要当码农 发表于 2016-10-29 03:12
听楼主的意思这题好像并没有限制只能往上飞。。。跟之前的不一样

应该是一个意思吧。就是算水平距离加上垂直高度。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-30 00:35:05 | 显示全部楼层
LumiG 发表于 2016-10-29 09:41
应该是一个意思吧。就是算水平距离加上垂直高度。

恭喜楼主啊, 问下“一堆文件,每个文件每行是一个字符串,找其中出现过次数最多的字符串”这个题有什么坑么? 是要自己实现读取文件的方法?
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-30 08:18:04 | 显示全部楼层
小A要当码农 发表于 2016-10-30 00:35
恭喜楼主啊, 问下“一堆文件,每个文件每行是一个字符串,找其中出现过次数最多的字符串”这个题有什么 ...

没啥,就是字面意义的题,然后一直是讨论为主吧,代码只写了我说的某一种方法的一部分。我为了方便给他写测试,用个generator模拟下了文件读写。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-30 08:19:55 | 显示全部楼层
LumiG 发表于 2016-10-30 08:18
没啥,就是字面意义的题,然后一直是讨论为主吧,代码只写了我说的某一种方法的一部分。我为了方便给他写 ...

👍写generator这个是要求的还是optional的呀。。
回复 支持 反对

使用道具 举报

 楼主| LumiG 发表于 2016-10-30 08:21:07 | 显示全部楼层
小A要当码农 发表于 2016-10-30 08:19. From 1point 3acres bbs
👍写generator这个是要求的还是optional的呀。。
. 1point 3acres 璁哄潧
没有没有,就都随意的,你自己写测试就行了,他只看对不对。
回复 支持 反对

使用道具 举报

西法的洛 发表于 2016-10-30 22:00:20 | 显示全部楼层
LumiG 发表于 2016-10-30 08:21
没有没有,就都随意的,你自己写测试就行了,他只看对不对。

楼主最后去了吗
回复 支持 反对

使用道具 举报

jasonliu119 发表于 2016-10-31 10:47:33 | 显示全部楼层
小A要当码农 发表于 2016-10-28 02:26
感觉这道题只能纯暴力dfs。。。我有一个想法,就是BFS + 最小堆。用一个额外的表记录每个点当前的代价, ...
. From 1point 3acres bbs
赞!其实这就是Dijkstra算法了,很经典的 哈哈
回复 支持 反对

使用道具 举报

tengpanpan 发表于 2016-11-1 06:16:17 | 显示全部楼层
给楼主点赞 还把代码分享给大家了 谢谢 恭喜恭喜
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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