一亩三分地论坛

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

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

S家onsite面经

[复制链接] |试试Instant~ |关注本帖
syftalent 发表于 2016-3-7 06:09:26 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Snapchat - 内推 - Onsite |Failfresh grad应届毕业生

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

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

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

第一轮 GAME OF LIFE 要求用boolean 存 然后follow up如果是个无限大的图怎么办
第二轮 8*8的棋盘 走K步从一个点走到另一个点有多少不同路径,之前在地里看到过但下面的都不对,先写了个dfs, 然后说简化,我说两头dfs, 然后说再简化,然后经他提示用dp做出来了, 思路是第K步走到一个格子一共有多少不同路径, 那么K+1步走到他周围八个点就是多少路径,解法类似Game of life开个buff数组
第三轮 ugly number 有k个prime -google 1point3acres
第四轮 merge k sorted list 但没有足够的空间存储所有结果 所以要priorityqueue存所有list的开头的数字然后取了存进disk 当时真是蒙圈了各种思路混乱 哎。。。。

面试就是个体力活,每次我到最后一轮都感觉吃不消, 大家午饭还是要吃饱点。。。。有问题下面回复我吧 这两天天天都会上地里。 第二题解出来我简直成就感爆棚。。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

1

查看全部评分

nothingtrouble 发表于 2016-3-7 10:11:48 | 显示全部楼层
感谢分享,能不能细说一下第二轮题目是什么?地里在哪儿看到的?
回复 支持 反对

使用道具 举报

 楼主| syftalent 发表于 2016-3-8 07:31:41 | 显示全部楼层
nothingtrouble 发表于 2016-3-7 10:11
感谢分享,能不能细说一下第二轮题目是什么?地里在哪儿看到的?

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

使用道具 举报

kinggarden2001 发表于 2016-3-8 11:17:08 | 显示全部楼层
请问Game of life follow up是怎么做的? partition那个matrix吗?怎么处理边界呢?
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-3-8 11:46:29 | 显示全部楼层
想了半天终于稍微想通了一点楼主说第二题DP的解法了。LZ NB!
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-3-9 04:12:21 | 显示全部楼层
syftalent 发表于 2016-3-8 07:31. From 1point 3acres bbs
很多贴都有。。。。 从一个格子走到另一个格子走K部有多少不同的走法 哦对了 上下左右对角线都可以走 所 ...

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

使用道具 举报

 楼主| syftalent 发表于 2016-3-9 07:24:57 | 显示全部楼层
jmnjmnjmn 发表于 2016-3-9 04:12. From 1point 3acres bbs
那假如求从A点[0,0] 走 3步 到B点[0,1]的路径数 ,  那从A到B回到A再到B, 这条3步的路线也算在内吗? . Waral 鍗氬鏈夋洿澶氭枃绔,
中 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
算的 你不要想得太复杂 K = 1的时候只有起始点周围是1 然后K=2的时候就扩展下去
回复 支持 反对

使用道具 举报

 楼主| syftalent 发表于 2016-3-9 07:26:18 | 显示全部楼层
kinggarden2001 发表于 2016-3-8 11:17
请问Game of life follow up是怎么做的? partition那个matrix吗?怎么处理边界呢?

这个我瞎扯得。。。 面试官不是太满意 = =
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-3-9 09:25:14 | 显示全部楼层
syftalent 发表于 2016-3-9 07:24
算的 你不要想得太复杂 K = 1的时候只有起始点周围是1 然后K=2的时候就扩展下去

明白了 那真是跟game of life一样的,相当于把game of life迭代K遍
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2016-3-9 10:57:36 | 显示全部楼层
所以dp[i][j][k] =  SUM(dp[ni][nj][k-1]), ni,nj取i,j的所有neighbors对吧?这样,dp[][]其实还可以简化到二维。
回复 支持 反对

使用道具 举报

 楼主| syftalent 发表于 2016-3-10 02:00:56 | 显示全部楼层
nothingtrouble 发表于 2016-3-9 10:57
所以dp[j][k] =  SUM(dp[ni][nj][k-1]), ni,nj取i,j的所有neighbors对吧?这样,dp[][]其实还可以简化到二 ...

本来就是二维啊。。。
回复 支持 反对

使用道具 举报

hzyslddm 发表于 2016-3-10 05:45:55 | 显示全部楼层
第一题用boolean存的话是不是就不能in place了?
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2016-3-10 05:51:08 | 显示全部楼层
syftalent 发表于 2016-3-10 02:00
本来就是二维啊。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
恩,对的,lz厉害,当场想出来!祝拿offer。
回复 支持 反对

使用道具 举报

 楼主| syftalent 发表于 2016-3-10 07:53:43 | 显示全部楼层
hzyslddm 发表于 2016-3-10 05:45
第一题用boolean存的话是不是就不能in place了?

对的 是有道理的 int32 位 boolean两位
回复 支持 反对

使用道具 举报

bochs 发表于 2016-3-16 13:37:54 | 显示全部楼层
nothingtrouble 发表于 2016-3-9 10:57
所以dp[j][k] =  SUM(dp[ni][nj][k-1]), ni,nj取i,j的所有neighbors对吧?这样,dp[][]其实还可以简化到二 ...
. visit 1point3acres.com for more.
你说的是空间二维吗?时间没想到能减到二维的方法
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2016-3-17 10:42:07 | 显示全部楼层
bochs 发表于 2016-3-16 13:37
你说的是空间二维吗?时间没想到能减到二维的方法

对的,时间复杂度应该是O(M*N*K)
回复 支持 反对

使用道具 举报

kemeng1314 发表于 2016-3-17 10:53:11 | 显示全部楼层
请问楼主是海投new grad职位吗,还是找内推,谢谢!
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-3-20 04:44:54 | 显示全部楼层
请问LZ第三轮的思路是否还是和leetcode的ugly number II一样,k-way merge啊?

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

使用道具 举报

tigercode 发表于 2016-9-15 13:22:13 | 显示全部楼层
1, 啥叫boolean存。。。
回复 支持 反对

使用道具 举报

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

感觉这个dp和bfs没啥区别啊
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 10:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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