求问Two Sigma店面一题如何解？

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

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

paca 发表于 2016-8-5 14:04
赶紧去学一下你说的这个Augment Data Structure。 麻烦你看一下下面这个链接里的内容是不是你说的那个考 ...

就是这个，书里可能讲的更详细些。

这面试官是UCSD的吗?
我被问到了同样的问题. 很快给了所有operation都是O(log n)的方法. 但是他觉得不够好.

后来发现有O(1) expectation的方法.(要用real RAM)  https://people.mpi-inf.mpg.de/~mehlhorn/ftp/DiscreteRandomVariates.pdf

谢谢分享

xihaokai1 发表于 2016-8-4 21:17
就是一个双向的链表，每个node存前一个node，后一个node, 还有weight。
你把每个weight想成一个线段,用 ...

很好的想法，但是想请问一下，按照你这种应该就不用HashMap了是吧

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

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

jiaozhu200601 发表于 2016-8-15 01:54
感谢提供，但是还想请问，既然已经使用了doubly linkedlist来存储object及其对应的weight，hashMap还有必 ...

Map 存object->node呀。

蓄水池抽样解决getramdom.. 肯定可行但是复杂度就是O（n）。 BIT我有点看不懂。。我也快面two sigma了

blackrose 发表于 2016-8-5 06:59
getRandom 难道不是linkedlist reservior sampling 问题么

reservoir 可以直接处理remove操作吗？

xihaokai1 发表于 2016-8-18 22:36
Map 存object->node呀。

请问为什么需要一个Node，感觉直接 Map<Object, Weight>也可以直接实现了，同时注意维持一个totalweight 的global variable。