一亩三分地论坛

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

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

Facebook Intern 面经

[复制链接] |试试Instant~ |关注本帖
theanois 发表于 2016-11-12 03:01:37 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 实习@Facebook - 内推 - 在线笔试 |Other其他

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

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

x
刚刚面完,感觉不是太好。
题目很简单,可惜不是面经。reservior sampling的题目. From 1point 3acres bbs
windows里面的扫雷,给一个h,w和m. 生成一个高度h,宽度w,总共m颗雷的矩阵。要求m颗雷随机分布。

第一个想法是把雷都放在前m个位置,从m+1的位置开始产生一个index小于m+1的位置,然后交换雷的位置。这一问写的磕磕绊绊,然后结果居然swap function 写错了,有个地方写太快把i写成了j。被指出来了之后很尴尬。
. more info on 1point3acres.com
然后小哥又问了运行时间。说了是O(hw)。然后问能不能在O(m)时间内搞定。才想起来正确的reservior sampling的写法。

哎,就免了这一道题,感觉要挂了,求大米和祝福,谢谢!.鐣欏璁哄潧-涓浜-涓夊垎鍦

.1point3acres缃

补充内容 (2016-11-12 03:33):
现在想想好像O(m)时间是不对的,不知道为什么这么问。感觉上至少要遍历完所有位置[x,y]才能决定。

评分

1

查看全部评分

ykben 发表于 2016-11-12 03:27:50 | 显示全部楼层
楼主加油!我一个小时之后第二面!
回复 支持 反对

使用道具 举报

wangyuesong2 发表于 2016-11-12 04:38:51 | 显示全部楼层
挺奇怪的,不就是得所有都遍历一遍才能搞定吗
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-12 23:19:22 | 显示全部楼层
我猜是不是说k比较小的时候不需要reservior sampling?
回复 支持 反对

使用道具 举报

 楼主| theanois 发表于 2016-11-13 02:14:05 | 显示全部楼层
鼓頔娜夫 发表于 2016-11-12 23:19
我猜是不是说k比较小的时候不需要reservior sampling?

感觉不是这个意思,我怀疑他是想说能不能用O(m)的空间做。但是矛盾的地方在于即使用O(m)的空间做,我最后如果返回的是个matrix的话空间依然不可能小于O(hw)
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-13 02:46:07 | 显示全部楼层
theanois 发表于 2016-11-13 02:14
感觉不是这个意思,我怀疑他是想说能不能用O(m)的空间做。但是矛盾的地方在于即使用O(m)的空间做,我最后 ...

用O(m)空间是什么思路?时间上会快一些吗?
回复 支持 反对

使用道具 举报

yhatl 发表于 2016-11-13 12:52:41 | 显示全部楼层
可以O(m)做完,只要把有雷的位置移除再sample就行了
回复 支持 反对

使用道具 举报

yun5260561 发表于 2016-11-14 05:31:07 | 显示全部楼层
  1. vector<vector<int>> saolei(int h, int w, int m){
  2.     vector<vector<int>> mtx(h, vector<int>(w,0));
  3.     int tail = h*w;
  4.     for(int i = 0; i < m; i++){
  5.         tail--;
  6.         mtx[tail/w][tail%w] = rand()%(tail+1);
  7.     }
  8.    
  9.     for(int i = 0; i < m; i++) {
  10.         int cur = mtx[tail/w][tail%w];
  11.         swap(mtx[tail/w][tail%w],mtx[cur/w][cur%w]);
  12.         tail++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  13.     }
  14.     return mtx;
  15. }
复制代码


感觉o(m)是能做的,就跟一维的一样
回复 支持 反对

使用道具 举报

鼓頔娜夫 发表于 2016-11-14 08:52:01 | 显示全部楼层
yun5260561 发表于 2016-11-14 05:31.1point3acres缃
感觉o(m)是能做的,就跟一维的一样

能解释一下第二个for循环吗?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-14 10:05:29 | 显示全部楼层
我觉得,这题也许不用水槽原理吧?. 鍥磋鎴戜滑@1point 3 acres
基本就是 row * col, 然后generate m个数。
比如 row是3, col 是4.
一共有12种可能,我们就随机产生m个数在12之内。
假设每个数是n,那对他对应到matrix里面的坐标,就是  (n/col,n%col).
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-14 10:06:48 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-14 10:05
我觉得,这题也许不用水槽原理吧?
基本就是 row * col, 然后generate m个数。
比如 row是3, col 是4.
...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这题的follow up,如果matrix 超级大,怎么generate 概率相同的数,那我觉得,应该用水槽原理。
回复 支持 反对

使用道具 举报

 楼主| theanois 发表于 2016-11-15 02:53:13 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-14 10:06
这题的follow up,如果matrix 超级大,怎么generate 概率相同的数,那我觉得,应该用水槽原理。

应该是,如果直接generate的话应该是个shuffle array
回复 支持 反对

使用道具 举报

angryR 发表于 2016-11-15 08:55:16 | 显示全部楼层
关注一下。reservoir sampling主要是从头扫到尾,每次变化分母。感觉直接把雷放好,然后swap 不是一个等价的方法啊
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-15 09:00:40 | 显示全部楼层
theanois 发表于 2016-11-15 02:53
应该是,如果直接generate的话应该是个shuffle array

lz收到通知了么。
回复 支持 反对

使用道具 举报

 楼主| theanois 发表于 2016-11-15 09:38:18 | 显示全部楼层
刚刚收到通知,跪了。面经刷题为了fb准备了不少,可惜水平还有欠缺。
回复 支持 反对

使用道具 举报

dokolo 发表于 2016-11-15 11:51:20 | 显示全部楼层
我的想法是,从[0,hw-1]中随机一个数,如果这个数不是hw-1,那么用一个hashtable记下来这个位置应该是对应hw-1这个位置。
第二个位置从[0,hw-2]随机,如果是之前那么个数,那么把第二个元素的位置记为hw-1,否则记做随机到的数字,然后把这个数字对应到hw-2。依次类推...
最后按地雷的位置在地图上埋雷就行了

  1. def insert(h,w,m):.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.     position = [None]*m
  3.     lut = {}
  4.     for i in range(h*w):
  5.         pos = randint(0,h*w-i-1)
  6.         if pos in lut:
  7.             position[i] = lut[pos]
  8.         else:
  9.             position[i] = pos
  10.         lut[pos] = h*w-i-1
复制代码
回复 支持 反对

使用道具 举报

Alice_koi 发表于 2016-11-15 12:13:16 | 显示全部楼层
答主有follow up嘛?
回复 支持 反对

使用道具 举报

 楼主| theanois 发表于 2016-11-16 02:20:26 | 显示全部楼层
Alice_koi 发表于 2016-11-15 12:13
答主有follow up嘛?
. from: 1point3acres.com/bbs
不好意思,因为跪了,所以也不知道follow up答的对不对,你看帖子里的讨论吧,觉得挺有用的
回复 支持 反对

使用道具 举报

wangyuesong2 发表于 2016-11-16 08:09:30 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-14 10:05
我觉得,这题也许不用水槽原理吧?
基本就是 row * col, 然后generate m个数。
比如 row是3, col 是4.
...

感觉不是很好搞,如果12个里面让放11个雷,这个方法不容易genreate 11个不同的数
回复 支持 反对

使用道具 举报

wangyuesong2 发表于 2016-11-16 08:24:42 | 显示全部楼层
yun5260561 发表于 2016-11-14 05:31. 1point3acres.com/bbs
感觉o(m)是能做的,就跟一维的一样

同求解释,感觉这样的话好像概率不对啊,最后一个元素只有1/h*w的概率是雷,因为倒数第二个元素generate雷位置的时候范围就不包括最后一个元素了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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