Snapchat 电面

1维的frog跳石头问题

//    0   1    2   3     4     5    6    7     8    9    10

// {'F', 'R', 'R', 'R', 'W', 'W', 'R', 'W', 'R','W', 'O'};<

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

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

align="left">然后面试官follow up  2D的池塘，idea就是拿着终点位置和assume的velocity要写一个helper generate出所有可能的起点。 然后OR所有。

大家加油！！！！！！！！

mingzhou1987 发表于 2016-4-19 12:30
没看懂dp公式，能简要讲讲吗，祝楼主好运

我觉得楼主的公式可能打错了。少了个[i]。我说说我的想法，如果不对请楼主指正哈~明天我也正要面snapchat。
dp[i][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。

godstears 发表于 2016-4-20 07:10
有点长啊，我就两个for loop再一个公式， 20行吧

我是觉得你俩的等式不一样，他是L[i][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)

补充内容 (2016-4-20 07:21):
L(i,j) i又被吞了

能解释一下R和W各是什么吗？另外什么叫“他在每一个石头上有决定自己走 （+1， 0， -1）步的权”？是速度加一吗，这个速度加减是可以累加的？

lzb700m 发表于 2016-4-19 11:08
能解释一下R和W各是什么吗？另外什么叫“他在每一个石头上有决定自己走 （+1， 0， -1）步的权”？是速度加 ...

R是rock， W是water， F是起始，O是终点。
每次是能变1，能累加的。
比如你第一次是1， 第二次你选择+1， 那你第二次就是走 2步， 那第三次就只能选1， 2， 3， 不能走4之类的

没看懂dp公式，能简要讲讲吗，祝楼主好运

jialegavin 发表于 2016-4-19 13:40
我觉得楼主的公式可能打错了。少了个。我说说我的想法，如果不对请楼主指正哈~明天我也正要面snapchat。
...

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

jialegavin 发表于 2016-4-19 13:40
我觉得楼主的公式可能打错了。少了个。我说说我的想法，如果不对请楼主指正哈~明天我也正要面snapchat。
...

Ugh....不是我的错，方括号 i 方括号 打不出来额。。。。

godstears 发表于 2016-4-19 21:02
Ugh....不是我的错，方括号 i 方括号 打不出来额。。。。

好吧……我发完没看，我自己也没打出来

多谢楼主的解释。还有个问题，google hangout的面试代码是用什么写呢？自己的ide然后共享屏幕，还是用online ide？

lzb700m 发表于 2016-4-20 00:00
多谢楼主的解释。还有个问题，google hangout的面试代码是用什么写呢？自己的ide然后共享屏幕，还是用onlin ...

是面试官share一个在chat里，跟其他公司一样 的code pad，不用share 屏幕