一亩三分地论坛

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

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

Facebook PE面经

[复制链接] |试试Instant~ |关注本帖
hongbiao.yang 发表于 2016-7-29 05:22:28 | 显示全部楼层 |阅读模式

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

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

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

x
facebook pe职位的电面,coding题。由于我是coding和system一起面,每个30分钟,貌似给了我一个很easy的题:生成扫雷

Given a height and a width and number of mines, return a minesweeper
field with mines in random positions
input: 2, 3, 3. from: 1point3acres.com/bbs
return:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
-------------
-   -   - X -
-------------
- X - X -   -
-------------


我用loop,每次random一个0~width*height的数,然后转化为x和y,给mine二位数组赋值 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

follow up question:
1.  what if input: 100, 100, 9999.  雷太多怎么办
2.  what if input: 10000, 10000, 10000*10000/2. 上一题我答的用雷过半就算没雷的地方,保证不过半。然后他就问如果刚好一半怎么办,如何检测conflict

半个小时后system面,问得很杂,就先不写了。版上的面经挺有用的,问了经典的 "ls foo*"问题,中间各种发散

求onsite!


评分

1

查看全部评分

genericname 发表于 2016-8-9 04:43:43 | 显示全部楼层
请问楼主第二个followup怎么回答的?
检测conflict又是什么意思?
回复 支持 反对

使用道具 举报

 楼主| hongbiao.yang 发表于 2016-8-9 05:08:30 | 显示全部楼层
genericname 发表于 2016-8-9 04:43
请问楼主第二个followup怎么回答的?
检测conflict又是什么意思?

我说worst case会很慢,比如不停的随机到有雷的地方然后就得跳过继续循环,虽然时间一久终究不会永远随机到已经有雷的地方(也就conflict)
然后他提示我是不是有更好的方法,我说是有,不过得增加空间复杂度,用不放回抽取,用一个ArrayList把所有位置坐标放进去,每抽取一次就把这个位置从ArrayList里面删掉,那么下次就肯定不会再抽到了,保证worst case就是雷的个数,并且这个数永远< N/2. 然后他说对,这就是他要的答案
回复 支持 反对

使用道具 举报

phantom 发表于 2016-8-9 06:52:38 | 显示全部楼层
是不是应该用reservoir sampling先把位置固定了。
二维数组可以展开成一维数组嘛。。先把有雷的位置确定了就好了
回复 支持 反对

使用道具 举报

 楼主| hongbiao.yang 发表于 2016-8-9 06:59:49 | 显示全部楼层
phantom 发表于 2016-8-9 06:52
是不是应该用reservoir sampling先把位置固定了。
二维数组可以展开成一维数组嘛。。先把有雷的位置确定了 ...

恩 是用的一维随机,随机一个[0,m*n-1]的index,然后再转化为二位数组的x=r/m和y=r%m
reservoir sampling没听过额。。
回复 支持 反对

使用道具 举报

phantom 发表于 2016-8-9 07:16:16 | 显示全部楼层
hongbiao.yang 发表于 2016-8-9 06:59
恩 是用的一维随机,随机一个[0,m*n-1]的index,然后再转化为二位数组的x=r/m和y=r%m-google 1point3acres
reservoir samplin ...
. more info on 1point3acres.com
reservoir sampling就是先开一个长度为K(地雷数)的数组(1,2,3.. K). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后从P = K+1到N。。生成一个从1-P的随机数Q。如果Q在1-K以内就用P替换掉数组里的Q。
这样每个数取到的概率是一样的。。而且不用担心重复
回复 支持 反对

使用道具 举报

 楼主| hongbiao.yang 发表于 2016-8-9 07:25:09 | 显示全部楼层
phantom 发表于 2016-8-9 07:16
reservoir sampling就是先开一个长度为K(地雷数)的数组(1,2,3.. K). 鍥磋鎴戜滑@1point 3 acres
然后从P = K+1到N。。生成一个从 ...

那时间复杂度不一定低吧,每次查找Q是否在1-K中,都得遍历K个数来确认。如果是K=N/2的情况,那岂不是相当于O(N^2)了。用HashSet等可能会快点,但HashSet的查找也不能被当做是O(1)的吧?
回复 支持 反对

使用道具 举报

phantom 发表于 2016-8-9 07:46:19 | 显示全部楼层
hongbiao.yang 发表于 2016-8-9 07:25
那时间复杂度不一定低吧,每次查找Q是否在1-K中,都得遍历K个数来确认。如果是K=N/2的情况,那岂不是相当 ...

O(n)啊。。是否在1-K。。Q<K不就判断了。。
回复 支持 反对

使用道具 举报

 楼主| hongbiao.yang 发表于 2016-8-9 09:35:04 | 显示全部楼层
phantom 发表于 2016-8-9 07:46
O(n)啊。。是否在1-K。。Q

哦 也就是之前被替换过的数,后面还有可能被重复替换覆盖掉?
回复 支持 反对

使用道具 举报

maihuabu 发表于 2016-8-9 11:38:26 | 显示全部楼层
祝楼主好运!
.1point3acres缃
求问经典"ls foo*"是什么题,好像没有查到,多谢!
回复 支持 反对

使用道具 举报

 楼主| hongbiao.yang 发表于 2016-8-9 11:43:30 | 显示全部楼层
maihuabu 发表于 2016-8-9 11:38
祝楼主好运!

求问经典&quot;ls foo*&quot;是什么题,好像没有查到,多谢!

哎 谢谢你,可惜我已经挂了。 ls foo*就是问你当你type ls foo* 系统经历了哪些系统调用,看完这个帖子就差不多了: http://sysadvent.blogspot.com/2010/12/day-15-down-ls-rabbit-hole.html  
回复 支持 反对

使用道具 举报

phantom 发表于 2016-8-9 13:13:54 | 显示全部楼层
hongbiao.yang 发表于 2016-8-9 09:35 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
哦 也就是之前被替换过的数,后面还有可能被重复替换覆盖掉?

嗯。。确实是有可能的。。
回复 支持 反对

使用道具 举报

null_point_exc 发表于 2016-8-9 15:23:57 | 显示全部楼层
hongbiao.yang 发表于 2016-8-9 05:08. from: 1point3acres.com/bbs
我说worst case会很慢,比如不停的随机到有雷的地方然后就得跳过继续循环,虽然时间一久终究不会永远随机 ...

的一个随机数 r, 重复了就 r++ 直到不重复位置。这样和你的arrayList本质上一样,并不需要额外空间。如果是雷多的情况,我觉得可以事先生成好,用的时候随机交换几个行列就可以了,不需要每次都重新生成,很慢的。
回复 支持 反对

使用道具 举报

 楼主| hongbiao.yang 发表于 2016-8-9 20:27:34 | 显示全部楼层
null_point_exc 发表于 2016-8-9 15:23
的一个随机数 r, 重复了就 r++ 直到不重复位置。这样和你的arrayList本质上一样,并不需要额外空间。如 ...

每次都随机到1(或者很多次都随机到1),然后一路++上去,还不是也很慢啊。这里说的是worst case的速度。还有,什么叫事先生成啊?一次rabdom不就返回一个数?
回复 支持 反对

使用道具 举报

maihuabu 发表于 2016-8-10 02:05:12 | 显示全部楼层
hongbiao.yang 发表于 2016-8-9 11:43
哎 谢谢你,可惜我已经挂了。 ls foo*就是问你当你type ls foo* 系统经历了哪些系统调用,看完这个帖子就 ...

多谢分享!楼主找工加油
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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