一亩三分地论坛

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

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

fb店面sign

[复制链接] |试试Instant~ |关注本帖
waikai 发表于 2016-10-5 06:24:55 | 显示全部楼层 |阅读模式

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

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

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

x
哎,先抱怨一句只靠面经真的不够。
一个白人大叔,应该级别挺高,自我介绍说每天50% 工作时间在meeting。
虚的就不说了,上题。
给一个l*w的矩阵,要随机取k个点。一个披着easy题的,蓄水池抽样。到最后也没解释清蓄水池原理。
大叔深深怀疑我的概率问题(其实我也怀疑),给我张白纸就好了- -
求米,求安慰,求二面

评分

1

查看全部评分

 楼主| waikai 发表于 2016-10-5 13:29:09 | 显示全部楼层
leixiang5 发表于 2016-10-5 13:18.鏈枃鍘熷垱鑷1point3acres璁哄潧
哦懂了..所以是不是这个呀
http://www.geeksforgeeks.org/reservoir-sampling/
. more info on 1point3acres.com
是有点这个意思。
int total = l*w
for (int i = 0; i < l; i++)
  for (j=0; j < w; j++) . visit 1point3acres.com for more.
    if (random.nextInt(total) < k) . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        grid[j] = 1; total--; k--;
    else . visit 1point3acres.com for more.
        total--. Waral 鍗氬鏈夋洿澶氭枃绔,
这会儿分分钟写出来了,当时有点蒙。
回复 支持 2 反对 0

使用道具 举报

zwcelesta 发表于 2016-10-5 06:48:52 | 显示全部楼层
不是stream的话你直接 index = random.nextInt(n * m); row = index/m;col = index%m不就完了吗
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-10-5 06:32:36 | 显示全部楼层
FB最近也出新题了
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-10-5 06:33:21 | 显示全部楼层
我刚面完,也是easy,今天迷得很
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-5 06:34:26 | 显示全部楼层
为啥一定要是matrix啊?data 是streaming吗 楼主能具体说下题目的环境吗 感谢
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 06:36:22 | 显示全部楼层
kobe24 发表于 2016-10-5 06:34
为啥一定要是matrix啊?data 是streaming吗 楼主能具体说下题目的环境吗 感谢

题目要求是matrix中取random的取出K个啊。不是streaming
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 06:37:26 | 显示全部楼层
gaocan1992 发表于 2016-10-5 06:33
我刚面完,也是easy,今天迷得很

而然,刨去寒暄背景啥的, 25分钟这样一题。。我觉得是跪定了
回复 支持 反对

使用道具 举报

kobe24 发表于 2016-10-5 06:38:14 | 显示全部楼层
reservior sampling 面试官叫你证明一系列数学依据吗
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 06:39:20 | 显示全部楼层
kobe24 发表于 2016-10-5 06:38
reservior sampling 面试官叫你证明一系列数学依据吗

要自证是对的呀
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-5 06:43:38 | 显示全部楼层
楼主能详细说一下题目吗?为什么是蓄水池问题呢
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 06:48:03 | 显示全部楼层
chestnut9919 发表于 2016-10-5 06:43. 1point 3acres 璁哄潧
楼主能详细说一下题目吗?为什么是蓄水池问题呢

我说的就是全题了呀。至于为什么是蓄水池,是我自己理解的。. from: 1point3acres.com/bbs
因为你直接random的取数,万一每次都random同一个数。时间复杂度就不稳定了,
蓄水池能保证O(l*w)复杂度
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 06:50:06 | 显示全部楼层
zwcelesta 发表于 2016-10-5 06:48
不是stream的话你直接 index = random.nextInt(n * m); row = index/m;col = index%m不就完了吗

见楼上的回复
回复 支持 反对

使用道具 举报

steveguang 发表于 2016-10-5 07:01:28 | 显示全部楼层
为什么要考虑复杂度?假如10个点取两个,就算每次都相同,只能说那个点幸运啊
回复 支持 反对

使用道具 举报

zwcelesta 发表于 2016-10-5 07:03:20 | 显示全部楼层

Random random = new Random();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < k; ++i) {
        int total = n*m - k.鏈枃鍘熷垱鑷1point3acres璁哄潧
        int index = random.nextInt(total);
        int row = index/m;
        int col = index%m;. 1point3acres.com/bbs
        res.add(matrix[row][col]);
        if (index != total - 1) {. 1point 3acres 璁哄潧
                matrix[index/m][index%m] = matrix[(total-1)/m][(total-1)%m]
        }
. more info on 1point3acres.com}
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 07:03:57 | 显示全部楼层
steveguang 发表于 2016-10-5 07:01
为什么要考虑复杂度?假如10个点取两个,就算每次都相同,只能说那个点幸运啊

我也不想考虑啊。。
面试官的引导
回复 支持 反对

使用道具 举报

steveguang 发表于 2016-10-5 07:06:21 | 显示全部楼层
waikai 发表于 2016-10-5 07:03
我也不想考虑啊。。
面试官的引导

请问楼主面试官怎么说的?
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 07:10:30 | 显示全部楼层
steveguang 发表于 2016-10-5 07:06
请问楼主面试官怎么说的?

.鏈枃鍘熷垱鑷1point3acres璁哄潧面试官说:你这个时间复杂度是多少?我:最好情况O(m),最坏不确定,但应该可以用期望求出。
面试官:能不能稳定一点?
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 07:16:48 | 显示全部楼层
zwcelesta 发表于 2016-10-5 07:03.1point3acres缃
Random random = new Random();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
List res = new ArrayList();
for (int i = 0; i < k; ++i) {

恩,这样应该也行。不过要加工下,原题意思是取出点,然后把它变成1,其他的点都是0。
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-10-5 10:34:47 | 显示全部楼层
不太懂题目。。。不可以randomly generate一个0 to l * w - 1
然后选个根据这个number选个point么? 每次都random同一个数字?...那probability要多低啊。。
n^n ways to select n elements with replacement....这是要 l * w ^ (l * w)......假设l = 5, w = 6...30^30....难道我理解错题目了吗.
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 10:46:40 | 显示全部楼层
leixiang5 发表于 2016-10-5 10:34. 1point3acres.com/bbs
不太懂题目。。。不可以randomly generate一个0 to l * w - 1
然后选个根据这个number选个point么? 每次都 ...

没理解错,只是面试官提出了这个可能。比如8个数,选7个,最后那个数选起来就重复可能性很大了。
现在想想应该 random.next(l*w) <= m的时候选数, 然后m--, l*w--, 否则l*w--
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 10:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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