一亩三分地论坛

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

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

热乎乎的狗家面筋

[复制链接] |试试Instant~ |关注本帖
372284362 发表于 2016-9-16 03:28:44 | 显示全部楼层 |阅读模式

2017(1-3月) 码农类 硕士 全职@Google - 实习ReturnOffer - Onsite |Otherfresh grad应届毕业生

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

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

x
今天状态还算不错的~

第一轮是个国人小哥。先问上过的一门最有意思的课。我说可计算理论,因为我们学校上这个的老爷爷超级萌。我说本来我觉得这课没啥用,但之后才发现上了之后是因为自己不够牛逼。比如之后我又上数据库理论的时候发现用到了很多可计算的东西,虽然我现在还不知道数据库理论有啥用。。。然后做题,给定几个item,每个item对应一个权重。权重之比就是随机抽到这个item的概率之比。每个item只会被抽取到一次。我是用线段树维护区间累计概率,写完代码之后剩了五六分钟。问问他做什么的,他说是硬件的。我说我以前就是ECE的,也搞硬件,但感觉不好找工作呀!周围好多ECE朋友都没找到实习。他表示欢迎内推去他们组。。。

第二轮是个美国大叔。上一轮白板没擦,他看看之后表示他都不知道啥是线段树。题是leetcode原题,393。之前看了眼感觉不难也就没做。大概二十分钟写完开始聊。先问怎么测试,我列了几个要考虑的因素,像数据大小和各种invalid cases。因为提到了数据可能非常大,他就问大的合法测试数据怎么生成,用utf8生成器直接找本小说生成一下就好。问下时间复杂度,O(n)。第二题没写代码,就是一个text file,去掉重复的行,用哈希表。然后聊了聊哈希表实现,均摊时间复杂度用英语忘了怎么说了,他一直表示average不是个好的描述,刚查了一下是amortized,好吧。。。然后说内存不够怎么办,用多路归并排序,缺点是时间复杂度提升和无法保证原顺序。. 1point3acres.com/bbs

开心地说拜拜,回来接着干活。。。. 1point3acres.com/bbs

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 372284362 发表于 2016-9-19 14:20:50 | 显示全部楼层
小A要当码农 发表于 2016-9-19 14:16
我觉得不经过的路径上的节点也要更新啊, 因为总数变了(该item不能再被抽中了), 所以其他每个item被抽 ...
. From 1point 3acres bbs
比如 i1 (10) i2 (20) i3 (30) i4 (40),那么初始的线段树是:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

root(100). visit 1point3acres.com for more.
node1 (30) node2 (70). From 1point 3acres bbs
leaf1 (10) leaf2 (20) leaf3 (30) leaf4 (40)
. 1point3acres.com/bbs
随机0-100之间的数。

假如第一轮抽到了 i2,更新成:

root(80)
node1 (10) node2 (70). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
leaf1 (10) leaf2 (0) leaf3 (30) leaf4 (40)

随机0-80之间的数。

依此类推。。。
回复 支持 2 反对 0

使用道具 举报

haveto 发表于 2016-9-16 03:36:36 | 显示全部楼层
为啥你现在还在实习。。。。不都开学了么。。。。
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2016-9-16 03:38:07 | 显示全部楼层
haveto 发表于 2016-9-16 03:36
为啥你现在还在实习。。。。不都开学了么。。。。

ucsd开学晚,我们学校很多都是明天离职。。。
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-16 03:41:12 | 显示全部楼层
楼主能说下第一题是要算什么吗,然后能具体说下解法不? 题目意思不是很明白。。。
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2016-9-16 03:47:20 | 显示全部楼层
xpli521 发表于 2016-9-16 03:41
楼主能说下第一题是要算什么吗,然后能具体说下解法不? 题目意思不是很明白。。。

比如有4个item,权重是1,2,3,4

第一轮有1/10的概率抽到item 1.1point3acres缃
如果第一轮抽到item 4,那么第二轮有1/6的概率抽到item 1
如果第二轮抽到item 3,那么第三轮有1/3的概率抽到item 1
。。。. from: 1point3acres.com/bbs

线段树里每个节点对应区间 [l,r] 存item l 到item r中没抽到items的累计概率,每轮从根向叶递归,直到取到一个item,之后再从叶子回来,更新累计概率
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-9-16 09:48:13 | 显示全部楼层
372284362 发表于 2016-9-16 03:47. visit 1point3acres.com for more.
比如有4个item,权重是1,2,3,4
. from: 1point3acres.com/bbs . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第一轮有1/10的概率抽到item 1

只计算一个总的权重和, 然后每次更新不就可以了么?

还是说每次取的 item, 是在一个范围之内取, 不是在整个的范围之内?
回复 支持 反对

使用道具 举报

lingeast 发表于 2016-9-16 11:43:08 | 显示全部楼层
第一题用key-indexed counting + binary search解就行了吧
回复 支持 反对

使用道具 举报

Wilford 发表于 2016-9-19 13:41:15 | 显示全部楼层
lingeast 发表于 2016-9-16 11:43
第一题用key-indexed counting + binary search解就行了吧

Then... how to deal with "每个item只会被抽取到一次"?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-19 14:09:25 | 显示全部楼层
372284362 发表于 2016-9-16 03:47
比如有4个item,权重是1,2,3,4

第一轮有1/10的概率抽到item 1
. visit 1point3acres.com for more.
请问楼主,每轮抽中谁是需要自己写一个random函数来定的么? 以及线段树的思路的话,你抽中一个item之后, 需要更新每个节点的信息啊?
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2016-9-19 14:13:47 | 显示全部楼层
小A要当码农 发表于 2016-9-19 14:09
请问楼主,每轮抽中谁是需要自己写一个random函数来定的么? 以及线段树的思路的话,你抽中一个item之后 ...

对的,只要更新路径上经过的节点的信息就可以了。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-19 14:16:45 | 显示全部楼层
372284362 发表于 2016-9-19 14:13
对的,只要更新路径上经过的节点的信息就可以了。

我觉得不经过的路径上的节点也要更新啊, 因为总数变了(该item不能再被抽中了), 所以其他每个item被抽中的概率都变了呀?
回复 支持 反对

使用道具 举报

wilbur_zzz 发表于 2016-9-19 14:35:37 | 显示全部楼层
utf8生成器是什么?完全没听说过啊
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-20 00:44:43 | 显示全部楼层
372284362 发表于 2016-9-19 14:20
比如 i1 (10) i2 (20) i3 (30) i4 (40),那么初始的线段树是:

root(100)

懂了,多谢,所以节点里存的应该是抽中该节点子数中的叶子的概率吧?
回复 支持 反对

使用道具 举报

 楼主| 372284362 发表于 2016-9-20 09:29:20 | 显示全部楼层
小A要当码农 发表于 2016-9-20 00:44
懂了,多谢,所以节点里存的应该是抽中该节点子数中的叶子的概率吧?
. 1point 3acres 璁哄潧
嗯,对的~
回复 支持 反对

使用道具 举报

wugoat 发表于 2016-9-24 12:50:11 | 显示全部楼层
楼主 第一题的输出是什么 得到一个item所需要取的次数期望值?
回复 支持 反对

使用道具 举报

jennyEternal 发表于 2016-10-6 12:41:49 | 显示全部楼层
楼主真是棒棒的!!祝福offer多多来!!

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 04:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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