S家onsite面经

nothingtrouble 发表于 2016-3-9 10:57
所以dp[j][k] =  SUM(dp[ni][nj][k-1]), ni,nj取i,j的所有neighbors对吧？这样，dp[][]其实还可以简化到二 ...

本来就是二维啊。。。

第一题用boolean存的话是不是就不能in place了？

syftalent 发表于 2016-3-10 02:00
本来就是二维啊。。。

恩，对的，lz厉害，当场想出来！祝拿offer。

hzyslddm 发表于 2016-3-10 05:45
第一题用boolean存的话是不是就不能in place了？

对的 是有道理的 int32 位 boolean两位

nothingtrouble 发表于 2016-3-9 10:57
所以dp[j][k] =  SUM(dp[ni][nj][k-1]), ni,nj取i,j的所有neighbors对吧？这样，dp[][]其实还可以简化到二 ...

你说的是空间二维吗？时间没想到能减到二维的方法

bochs 发表于 2016-3-16 13:37
你说的是空间二维吗？时间没想到能减到二维的方法

对的，时间复杂度应该是O(M*N*K)

请问楼主是海投new grad职位吗，还是找内推，谢谢！

请问LZ第三轮的思路是否还是和leetcode的ugly number II一样，k-way merge啊？

最后一轮感觉是不是相当于external sort，把available memory分成 k+1份来 k-way merge，剩下1份空间当做输出缓冲区。可能还需要谈到trade off是k越大，merge的round越少，但是读写disk的时间会增加。

1, 啥叫boolean存。。。

syftalent 发表于 2016-3-8 07:31
很多贴都有。。。。 从一个格子走到另一个格子走K部有多少不同的走法 哦对了 上下左右对角线都可以走 所 ...

感觉这个dp和bfs没啥区别啊