亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1747|回复: 21
收起左侧

Facebook电面

[复制链接] |试试Instant~ |关注本帖
cli94 发表于 2017-7-14 07:23:30 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
7.13的电面

扫雷地图,给一个地图的长和宽,以及雷的数量,要求返回一个让雷随机分布的grid,雷用-1表示,随机函数直接用random函数就行

应该是像这样
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
public int[][] getGrid(int H, int W, int M) {
    // 返回M个雷随机分布的地图
}.鏈枃鍘熷垱鑷1point3acres璁哄潧

写完了代码问了complexity,我回答Space是O(H*W), Time on average是O(M) 前提是Sparse Grid, 如果是Dense Grid那Time Complexity 就是O(M^2) 或者O(M * W * H), 因为这个时候M基本上等于Grid的size

follow up: 如果一个位置没有雷,要求在没有雷的地方标出周围雷的数量,周围就是指上下左右对角线一共八个位置

我就写了一个遍历整个地图的function,面试官又问:如果是sparse grid该怎么样?当时很紧张,时间还剩5分钟没有答出来,然后就是问还有没有问题,我说没有就挂了电话。-google 1point3acres

挂了电话才想出来,如果是sparse grid可以把随机生成的雷的坐标保存在一个list里面,这样标雷数量的时候就只用遍历雷的坐标就可以了

我想可能是跪了

评分

3

查看全部评分

本帖被以下淘专辑推荐:

edyyy 发表于 2017-7-14 07:34:24 来自手机 | 显示全部楼层
这题明显比以往的题难。楼主答得很好了 加油
回复 支持 反对

使用道具 举报

 楼主| cli94 发表于 2017-7-14 07:45:15 | 显示全部楼层
edyyy 发表于 2017-7-14 07:34
这题明显比以往的题难。楼主答得很好了 加油

谢谢安慰啊 太紧张容易脑子短路
回复 支持 反对

使用道具 举报

 楼主| cli94 发表于 2017-7-14 08:07:50 | 显示全部楼层
我现在没有回复消息的权限 所以回答不了短消息
回复 支持 反对

使用道具 举报

zephyryin 发表于 2017-7-14 08:11:33 | 显示全部楼层
这应该是用水塘抽样把,时间复杂度O(H*W)
回复 支持 反对

使用道具 举报

 楼主| cli94 发表于 2017-7-14 08:15:40 | 显示全部楼层
zephyryin 发表于 2017-7-14 08:11. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这应该是用水塘抽样把,时间复杂度O(H*W)

只是电面,我估计没有你说的这么复杂
回复 支持 反对

使用道具 举报

 楼主| cli94 发表于 2017-7-14 08:20:24 | 显示全部楼层
zephyryin 发表于 2017-7-14 08:11
这应该是用水塘抽样把,时间复杂度O(H*W)
.1point3acres缃
而且如果是sparse grid的话M很小复杂度只有O(M),水塘复杂度O(H*W)就有点不太好了吧
回复 支持 反对

使用道具 举报

2011051305 发表于 2017-7-14 08:23:28 | 显示全部楼层
cli94 发表于 2017-7-14 08:07
我现在没有回复消息的权限 所以回答不了短消息

.鐣欏璁哄潧-涓浜-涓夊垎鍦感谢楼主 我想问一下您是PhD的new grad么? 我以为fb的"fresh grad"ms及以下的head count好像还没开始呢?
. 鍥磋鎴戜滑@1point 3 acres
还是说您的简历很多前端和mobile的project ?
回复 支持 反对

使用道具 举报

zhuyinghua1203 发表于 2017-7-14 08:24:28 | 显示全部楼层
Time complexity 是不是应该永远是O(M).鏈枃鍘熷垱鑷1point3acres璁哄潧

生成雷的过程和生成随机数列的算法类似,每一次生成一个雷的时间是一样的?
回复 支持 反对

使用道具 举报

 楼主| cli94 发表于 2017-7-14 08:27:44 | 显示全部楼层
2011051305 发表于 2017-7-14 08:23
感谢楼主 我想问一下您是PhD的new grad么? 我以为fb的"fresh grad"ms及以下的head count好像还没开始呢?
...

是吗?我不太清楚 我是本科毕业有两年工作经验 然后在读一个Online Master,所以我也不知道被分为哪种,recruiter是负责校招的
回复 支持 反对

使用道具 举报

 楼主| cli94 发表于 2017-7-14 08:33:38 | 显示全部楼层
zhuyinghua1203 发表于 2017-7-14 08:24
Time complexity 是不是应该永远是O(M)

生成雷的过程和生成随机数列的算法类似,每一次生成一个雷的时间 ...

我不太清楚,我写的就是用hashset记录之前雷的位置,如果hashset里面有这个数再生成一个新的。我说完complexity之后,面试官也没有让优化,估计写成这样就是可以了,然后就直接是followup了
回复 支持 反对

使用道具 举报

zhuyinghua1203 发表于 2017-7-14 08:39:30 | 显示全部楼层
你这样dart throwing 的算法complexity 是会变高

如果格子是10*20的,雷的位置就是0, 1..., 199
把这个数列随机化,每O(1)可以得到一个数字,重复M次就是M个雷的位置
回复 支持 反对

使用道具 举报

 楼主| cli94 发表于 2017-7-14 08:43:07 | 显示全部楼层
zhuyinghua1203 发表于 2017-7-14 08:39
你这样dart throwing 的算法complexity 是会变高

如果格子是10*20的,雷的位置就是0, 1..., 199

可是生成0,1...199的过程Complexity是不是还是O(H*W)呢?
回复 支持 反对

使用道具 举报

zhuyinghua1203 发表于 2017-7-14 08:45:49 | 显示全部楼层
试试用类似洗扑克牌的方法?
回复 支持 反对

使用道具 举报

 楼主| cli94 发表于 2017-7-14 08:47:14 | 显示全部楼层
我写完了第一问的代码,然后面试官问完complexity,听面试官说话的感觉还算挺满意的,所以感觉用HashSet记录之前出现的雷就足够了
回复 支持 反对

使用道具 举报

zhuyinghua1203 发表于 2017-7-14 08:47:41 | 显示全部楼层
第一次生成一个0到199的随机数,那个位置的数字就是第一个雷的位置,然后把这个数和倒数第一个数字交换

第二次生成一个0到198的随机数,那个位置的数字就是第二个雷的位置,然后把这个数和倒数第二个数字交换

重复M次
回复 支持 反对

使用道具 举报

forteller 发表于 2017-7-14 10:15:41 | 显示全部楼层
同意水塘抽样。. from: 1point3acres.com/bbs
楼主投的是什么岗?能说一下吗?这边new grad都等这投/推呢~~谢谢啦
回复 支持 反对

使用道具 举报

returning 发表于 2017-9-25 07:06:55 | 显示全部楼层
dense graph的话应该用resovir samping, 复杂度是H*W。
sparse的话估计有O(M)的做法,因为H*W>>M,所以直接生成M个0-H*W之间的随机数,应该就不会重复,当然可以hashset存一下,如果重复的话再生成一次。
回复 支持 反对

使用道具 举报

张欣 发表于 2017-9-26 11:06:53 | 显示全部楼层
zhuyinghua1203 发表于 2017-7-14 08:47. 1point3acres.com/bbs
第一次生成一个0到199的随机数,那个位置的数字就是第一个雷的位置,然后把这个数和倒数第一个数字交换. From 1point 3acres bbs

...

请问这样的复杂度是o(m)吗
回复 支持 反对

使用道具 举报

zhuyinghua1203 发表于 2017-9-26 13:13:16 | 显示全部楼层
张欣 发表于 2017-9-26 11:06. visit 1point3acres.com for more.
请问这样的复杂度是o(m)吗


字数补丁
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-19 13:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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