热乎乎的狗家面筋

今天状态还算不错的～

第一轮是个国人小哥。先问上过的一门最有意思的课。我说可计算理论，因为我们学校上这个的老爷爷超级萌。我说本来我觉得这课没啥用，但之后才发现上了之后是因为自己不够牛逼。比如之后我又上数据库理论的时候发现用到了很多可计算的东西，虽然我现在还不知道数据库理论有啥用。。。然后做题，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

直表示average不是个好的描述，刚查了一下是amortized，好吧。。。然后说内存不够怎么办，用多路归并排序，缺点是时间复杂度提升和无法保证原顺序。

开心地说拜拜，回来接着干活。。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

为啥你现在还在实习。。。。不都开学了么。。。。

haveto 发表于 2016-9-16 03:36
为啥你现在还在实习。。。。不都开学了么。。。。

ucsd开学晚，我们学校很多都是明天离职。。。

楼主能说下第一题是要算什么吗，然后能具体说下解法不？ 题目意思不是很明白。。。

372284362 发表于 2016-9-16 03:47
比如有4个item，权重是1，2，3，4

第一轮有1/10的概率抽到item 1

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

还是说每次取的 item, 是在一个范围之内取， 不是在整个的范围之内？

第一题用key-indexed counting + binary search解就行了吧

lingeast 发表于 2016-9-16 11:43
第一题用key-indexed counting + binary search解就行了吧

Then... how to deal with "每个item只会被抽取到一次"?

372284362 发表于 2016-9-16 03:47
比如有4个item，权重是1，2，3，4

第一轮有1/10的概率抽到item 1

请问楼主，每轮抽中谁是需要自己写一个random函数来定的么？ 以及线段树的思路的话，你抽中一个item之后， 需要更新每个节点的信息啊？

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

对的，只要更新路径上经过的节点的信息就可以了。