推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4891|回复: 39
收起左侧

fb店面sign

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

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

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

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

x
哎,先抱怨一句只靠面经真的不够。
一个白人大叔,应该级别挺高,自我介绍说每天50% 工作时间在meeting。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
虚的就不说了,上题。
给一个l*w的矩阵,要随机取k个点。一个披着easy题的,蓄水池抽样。到最后也没解释清蓄水池原理。. from: 1point3acres.com/bbs
大叔深深怀疑我的概率问题(其实我也怀疑),给我张白纸就好了- -
求米,求安慰,求二面 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| waikai 发表于 2016-10-5 13:29:09 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
leixiang5 发表于 2016-10-5 13:18
哦懂了..所以是不是这个呀
http://www.geeksforgeeks.org/reservoir-sampling/

是有点这个意思。
int total = l*w. 1point 3acres 璁哄潧
for (int i = 0; i < l; i++)
  for (j=0; j < w; j++)
    if (random.nextInt(total) < k)
        grid[j] = 1; total--; k--;
    else
        total--
这会儿分分钟写出来了,当时有点蒙。
回复 支持 2 反对 0

使用道具 举报

zwcelesta 发表于 2016-10-5 06:48:52 | 显示全部楼层
关注一亩三分地微博:
Warald
不是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
楼主能详细说一下题目吗?为什么是蓄水池问题呢

我说的就是全题了呀。至于为什么是蓄水池,是我自己理解的。. From 1point 3acres 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<>();. more info on 1point3acres.com
for (int i = 0; i < k; ++i) {
        int total = n*m - k
        int index = random.nextInt(total);
        int row = index/m;
        int col = index%m;
        res.add(matrix[row][col]);
        if (index != total - 1) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                matrix[index/m][index%m] = matrix[(total-1)/m][(total-1)%m]
        }
}. From 1point 3acres bbs
回复 支持 反对

使用道具 举报

 楼主| 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. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
请问楼主面试官怎么说的?

面试官说:你这个时间复杂度是多少?我:最好情况O(m),最坏不确定,但应该可以用期望求出。
面试官:能不能稳定一点?
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 07:16:48 | 显示全部楼层
zwcelesta 发表于 2016-10-5 07:03
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.鐣欏璁哄潧-涓浜-涓夊垎鍦
不太懂题目。。。不可以randomly generate一个0 to l * w - 1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后选个根据这个number选个point么? 每次都 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
没理解错,只是面试官提出了这个可能。比如8个数,选7个,最后那个数选起来就重复可能性很大了。
现在想想应该 random.next(l*w) <= m的时候选数, 然后m--, l*w--, 否则l*w--
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-17 01:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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