San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5415|回复: 39
收起左侧

fb店面sign

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

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

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

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

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| waikai 发表于 2016-10-5 13:29:09 | 显示全部楼层
leixiang5 发表于 2016-10-5 13:18. 1point3acres
哦懂了..所以是不是这个呀-google 1point3acres
http://www.geeksforgeeks.org/reservoir-sampling/

是有点这个意思。
int total = l*w
for (int i = 0; i < l; i++)
  for (j=0; j < w; j++)
    if (random.nextInt(total) < k) . visit 1point3acres for more.
        grid[j] = 1; total--; k--;
    else
        total--
这会儿分分钟写出来了,当时有点蒙。
回复 支持 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吗 楼主能具体说下题目的环境吗 感谢
. 1point3acres
题目要求是matrix中取random的取出K个啊。不是streaming
回复 支持 反对

使用道具 举报

 楼主| waikai 发表于 2016-10-5 06:37:26 | 显示全部楼层
gaocan1992 发表于 2016-10-5 06:33
我刚面完,也是easy,今天迷得很
-google 1point3acres
而然,刨去寒暄背景啥的, 25分钟这样一题。。我觉得是跪定了
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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. more info on 1point3acres
楼主能详细说一下题目吗?为什么是蓄水池问题呢

我说的就是全题了呀。至于为什么是蓄水池,是我自己理解的。
因为你直接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-google 1point3acres
        int index = random.nextInt(total);. 围观我们@1point 3 acres
        int row = index/m;
        int col = index%m;
        res.add(matrix[row][col]);
        if (index != total - 1) {
                matrix[index/m][index%m] = matrix[(total-1)/m][(total-1)%m]
        }. Waral 博客有更多文章,
}
回复 支持 反对

使用道具 举报

 楼主| 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
我也不想考虑啊。。.1point3acres网
面试官的引导
.1point3acres网
请问楼主面试官怎么说的?
回复 支持 反对

使用道具 举报

 楼主| 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();. 围观我们@1point 3 acres
List res = new ArrayList();. more info on 1point3acres
for (int i = 0; i < k; ++i) {

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

使用道具 举报

leixiang5 发表于 2016-10-5 10:34:47 | 显示全部楼层
不太懂题目。。。不可以randomly generate一个0 to l * w - 1.1point3acres网
然后选个根据这个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. 围观我们@1point 3 acres
不太懂题目。。。不可以randomly generate一个0 to l * w - 1
然后选个根据这个number选个point么? 每次都 ...

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-26 12:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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