一亩三分地论坛

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

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

Snapchat 电面

[复制链接] |试试Instant~ |关注本帖
godstears 发表于 2016-4-19 05:21:46 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Pass在职跳槽

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

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

x

1维的frog跳石头问题
//    0   1    2   3     4     5    6    7     8    9    10

// {'F', 'R', 'R', 'R', 'W', 'W', 'R', 'W', 'R','W', 'O'};
input: F R R R R R W W R W O and velocity = 1
output: true/false
意思是有一只青蛙在 F然后他的 起始可以跳步数是1,但是他在每一个石头上有决定自己走 (+1, 0, -1)步的权
比如这个例子青蛙可以从0->1(v=1) 然后1->3(v+1 = 2) 然后 3->6(v+1 = 3)然后6->8(v-1= 2)然后8->10(v = 2)
当然这是一个相当好的 test case,需要注意的是不要assume你要踩所有的石头。我开始没注意,后来才纠结出来。
简单写一下dp公式:
dp[v] = dp[i-(v+1)][v+1] || dp[i-(v-1)][v-1] || dp[i-v][v]
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后面试官follow up  2D的池塘,idea就是拿着终点位置和assume的velocity要写一个helper generate出所有可能的起点。 然后OR所有。
大家加油!!!!!!!!

评分

3

查看全部评分

jialegavin 发表于 2016-4-19 13:40:59 | 显示全部楼层
mingzhou1987 发表于 2016-4-19 12:30
没看懂dp公式,能简要讲讲吗,祝楼主好运

我觉得楼主的公式可能打错了。少了个。我说说我的想法,如果不对请楼主指正哈~明天我也正要面snapchat。
dp[v] = dp[i - (v - 1)][v - 1] || dp[i - v][v] || dp[i - (v + 1)][v + 1]

dp[][]是个n*n的矩阵, 你在第i个位置,v步的状态是否成立,取决于上式中后面三者是否有其一是成立的。如果第i位是W的话,应该直接算是false。最后看最后O的那边,是否有一个是true的,有的话输出就是true。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

lzb700m 发表于 2016-4-19 11:08:14 | 显示全部楼层
能解释一下R和W各是什么吗?另外什么叫“他在每一个石头上有决定自己走 (+1, 0, -1)步的权”?是速度加一吗,这个速度加减是可以累加的?
回复 支持 反对

使用道具 举报

 楼主| godstears 发表于 2016-4-19 11:11:45 | 显示全部楼层
lzb700m 发表于 2016-4-19 11:08
能解释一下R和W各是什么吗?另外什么叫“他在每一个石头上有决定自己走 (+1, 0, -1)步的权”?是速度加 ...
. more info on 1point3acres.com
R是rock, W是water, F是起始,O是终点。
每次是能变1,能累加的。
比如你第一次是1, 第二次你选择+1, 那你第二次就是走 2步, 那第三次就只能选1, 2, 3, 不能走4之类的
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-19 12:30:57 | 显示全部楼层
没看懂dp公式,能简要讲讲吗,祝楼主好运
回复 支持 反对

使用道具 举报

 楼主| godstears 发表于 2016-4-19 21:01:02 | 显示全部楼层
jialegavin 发表于 2016-4-19 13:40. visit 1point3acres.com for more.
我觉得楼主的公式可能打错了。少了个。我说说我的想法,如果不对请楼主指正哈~明天我也正要面snapchat。
...

对的
我少打了个
dp[v] = dp[i - (v - 1)][v - 1] || dp[i - v][v] || dp[i - (v + 1)][v + 1]
就是三种情况啦, 可以从前一步 v-1/v/v+1走到这一步
回复 支持 反对

使用道具 举报

 楼主| godstears 发表于 2016-4-19 21:02:00 | 显示全部楼层
jialegavin 发表于 2016-4-19 13:40. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我觉得楼主的公式可能打错了。少了个。我说说我的想法,如果不对请楼主指正哈~明天我也正要面snapchat。
...

Ugh....不是我的错,方括号 i 方括号 打不出来额。。。。
回复 支持 反对

使用道具 举报

jialegavin 发表于 2016-4-19 22:43:59 | 显示全部楼层
godstears 发表于 2016-4-19 21:02
Ugh....不是我的错,方括号 i 方括号 打不出来额。。。。

好吧……我发完没看,我自己也没打出来
回复 支持 反对

使用道具 举报

lzb700m 发表于 2016-4-20 00:00:56 | 显示全部楼层
多谢楼主的解释。还有个问题,google hangout的面试代码是用什么写呢?自己的ide然后共享屏幕,还是用online ide?
回复 支持 反对

使用道具 举报

 楼主| godstears 发表于 2016-4-20 01:02:19 | 显示全部楼层
lzb700m 发表于 2016-4-20 00:00
多谢楼主的解释。还有个问题,google hangout的面试代码是用什么写呢?自己的ide然后共享屏幕,还是用onlin ...

是面试官share一个在chat里,跟其他公司一样 的code pad,不用share 屏幕
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-20 01:43:07 | 显示全部楼层
godstears 发表于 2016-4-19 21:01
对的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我少打了个
dp[v] = dp[v - 1] || dp[v] || dp[v + 1]
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
你好,我想问下写dp的循环时这个v的范围是怎么确定的呢?谢谢~
回复 支持 反对

使用道具 举报

 楼主| godstears 发表于 2016-4-20 01:47:16 | 显示全部楼层
jy_121 发表于 2016-4-20 01:43
你好,我想问下写dp的循环时这个v的范围是怎么确定的呢?谢谢~

我是直接 0到总长度, 面试官最后说怎么shrink我说那就到 i 吧, 他问了一下为什么我说了一下最多考虑都到前面 i 步?他好像默认对了, 可是我回来试了一下错的lol,你试出来跟我说一下吧
回复 支持 反对

使用道具 举报

TsengJuiWang 发表于 2016-4-20 03:05:09 | 显示全部楼层
jialegavin 发表于 2016-4-19 13:40
我觉得楼主的公式可能打错了。少了个。我说说我的想法,如果不对请楼主指正哈~明天我也正要面snapchat。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
...

类似背包问题吧?
回复 支持 反对

使用道具 举报

TsengJuiWang 发表于 2016-4-20 05:37:57 | 显示全部楼层
楼主初始化L[0][j]和L[k][0]的?谢谢
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-20 05:41:58 | 显示全部楼层
godstears 发表于 2016-4-20 01:47
我是直接 0到总长度, 面试官最后说怎么shrink我说那就到 i 吧, 他问了一下为什么我说了一下最多考虑都 ...

好的,不过我也没想明白。。。
回复 支持 反对

使用道具 举报

 楼主| godstears 发表于 2016-4-20 06:04:58 | 显示全部楼层
TsengJuiWang 发表于 2016-4-20 05:37
楼主初始化L[0][j]和L[k][0]的?谢谢

初始化就一位: dp[0][1] = 1表示在位置0而且当前的velocity是1
回复 支持 反对

使用道具 举报

TsengJuiWang 发表于 2016-4-20 07:07:32 | 显示全部楼层
godstears 发表于 2016-4-20 06:04
初始化就一位: dp[0][1] = 1表示在位置0而且当前的velocity是1
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主,我在网上看到这个题,和你的很像,但是写法好像不太一样http://algorithmsgeek.blogspot.com/2013/06/algo28-help-frog-to-cross-river.html
回复 支持 反对

使用道具 举报

 楼主| godstears 发表于 2016-4-20 07:10:09 | 显示全部楼层
TsengJuiWang 发表于 2016-4-20 07:07
楼主,我在网上看到这个题,和你的很像,但是写法好像不太一样http://algorithmsgeek.blogspot.com/2013/ ...
. more info on 1point3acres.com
有点长啊,我就两个for loop再一个公式, 20行吧
回复 支持 反对

使用道具 举报

TsengJuiWang 发表于 2016-4-20 07:20:25 | 显示全部楼层
godstears 发表于 2016-4-20 07:10
有点长啊,我就两个for loop再一个公式, 20行吧

我是觉得你俩的等式不一样,他是L[j] = L[i - j][j] || L[i - j][j - 1] || L[i - j][j + 1],另外j的取值范围我看了他的代码之后想了一下应该是sqrt(2*n)因为第一次速度是1,下一次速度最大是2,可以跳到3,下一次速度最大是4,最远可以跳到7,也就是(1 + v) * v / 2 = n,所以v~sqrt(2n). 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-4-20 07:21):
L(i,j) i又被吞了
回复 支持 反对

使用道具 举报

 楼主| godstears 发表于 2016-4-20 07:24:53 | 显示全部楼层
TsengJuiWang 发表于 2016-4-20 07:20
我是觉得你俩的等式不一样,他是L[j] = L[j] || L[j - 1] || L[j + 1],另外j的取值范围我看了他的代码之 ...

这个公式肯定不对吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 08:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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