S家onsite面经

来发一个Snapchat的onsite 已挂。。。 最后一轮饿得不行脑子当机了 估计是挂那轮了 挺可惜的。。。

第一轮 GAME OF LIFE 要求用boolean 存 然后follow up如果是个无限大的图怎么办
第二轮 8*8的棋盘 走K步从

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

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

到最后一轮都感觉吃不消， 大家午饭还是要吃饱点。。。。有问题下面回复我吧 这两天天天都会上地里。 第二题解出来我简直成就感爆棚。。。。

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

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

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

那假如求从A点[0,0] 走 3步 到B点[0,1]的路径数 ,  那从A到B回到A再到B, 这条3步的路线也算在内吗？
中间已经到过B的话，这条路线要不要当做是2步的路线排除掉呢。

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

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

感谢分享，能不能细说一下第二轮题目是什么？地里在哪儿看到的？

nothingtrouble 发表于 2016-3-7 10:11
感谢分享，能不能细说一下第二轮题目是什么？地里在哪儿看到的？

很多贴都有。。。。 从一个格子走到另一个格子走K部有多少不同的走法 哦对了 上下左右对角线都可以走 所以每次有八步

请问Game of life follow up是怎么做的？ partition那个matrix吗？怎么处理边界呢？

想了半天终于稍微想通了一点楼主说第二题DP的解法了。LZ NB！

jmnjmnjmn 发表于 2016-3-9 04:12
那假如求从A点[0,0] 走 3步 到B点[0,1]的路径数 ,  那从A到B回到A再到B, 这条3步的路线也算在内吗？
中 ...

算的 你不要想得太复杂 K = 1的时候只有起始点周围是1 然后K=2的时候就扩展下去

kinggarden2001 发表于 2016-3-8 11:17
请问Game of life follow up是怎么做的？ partition那个matrix吗？怎么处理边界呢？

这个我瞎扯得。。。 面试官不是太满意 = =

syftalent 发表于 2016-3-9 07:24
算的 你不要想得太复杂 K = 1的时候只有起始点周围是1 然后K=2的时候就扩展下去

明白了 那真是跟game of life一样的，相当于把game of life迭代K遍

所以dp[i][j][k] =  SUM(dp[ni][nj][k-1]), ni,nj取i,j的所有neighbors对吧？这样，dp[][]其实还可以简化到二维。