snapchat新鲜昂赛跪经

xiaoyehhuang23 · 2016-10-27 08:44:08

小A要当码农发表于 2016-10-26 23:47
楼主二面和三面follow up啥思路？

三面的followup见讨论，二面的其实还挺直观的，一步一步拆开来看看一共多少复杂度就好了

keytion · 2016-10-27 08:55:39

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

linweihua0 · 2016-10-27 09:10:32

"那么i节点可能的步数最多是O(i^0.5)" 明显不止啊

0 1 2 3 4 5 6 7 8 9 10
这里10这个stone就可能有 1,2,3,4,5 possible steps.你石头越多后面可能性越多

xiaoyehhuang23 · 2016-10-27 09:18:23

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

xiaoyehhuang23 · 2016-10-27 09:20:57

keytion 发表于 2016-10-27 08:55
每个节点可达步数一直存着吧。。
等于在《position, previous step》这个space上做graph traverse. Visi ...

那我们的思路大概是一样的。。哎面试的时候到后面真的是想不清楚了。。。

xiaoyehhuang23 · 2016-10-27 09:24:54

再吐个槽。。为啥我一个国人面试官的碰不上。。。而且怎么感觉比别人的面经难那么多啊。。。。

linweihua0 · 2016-10-27 10:54:34

xiaoyehhuang23 发表于 2016-10-27 09:18
我是这样证明的：
想象一下用bottomup的做法的话，维护的表格的大小是O(N*V)，计算表格里的每一个元素应 ...

你说的有道理因为去重之后就成了polynomial了
其实我觉得他家中国面试官题目更难= =

xiaoyehhuang23 · 2016-10-27 11:04:29

linweihua0 发表于 2016-10-27 10:54
你说的有道理因为去重之后就成了polynomial了
其实我觉得他家中国面试官题目更难= =

哎move on了QAQ

小A要当码农 · 2016-10-27 11:13:53

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

liurudahai · 2016-11-13 10:29:18

xiaoyehhuang23 发表于 2016-10-26 15:26
第一个问题：遍历一遍倒是可以，但是复杂度好像就会比较高，用trie会比较好。
第二个问题：加入前缀的意 ...

我也觉得是两个TRIE，应该就比较简单了