问一个数据结构中GetRandom的设计实现题

2016/8/24镜像同步6 回复

最近面试遇到一个有意思的题，想问问大家有没有啥好思路。题目是：让设计一个数据结构，要求可以存储Object-Weight Pair，实现如下几个接口：1） Update；2） Insert；3） Remove；4） GetRandom.这个GetRandom的方法是随机地返回一个Object，要求概率满足：此object的weight / 所有weight的和最原始的解法： ArrayList + Map 实现了 O(1), O(1), O(1), O(N) 然后面试官觉得可以优化，就有了 Queue + BIT + Map的解法，达到了全logN的复杂度。但是面试官似乎还不太满意，说这个还能更好。后来我在领英上问了下思路，他给了我一个论文链接： https://people.mpi-inf.mpg.de/~mehlhorn/ftp/DiscreteRandomVariates.pdf 说可以达到 O(1) 的期望。想请问论坛大大们，有什么好的思路么。或者遇到过类似的问题可否分享一下

订阅后，新回复会通过你的通知中心匿名送达。

6 条回复

aquamarine机器人#1 · 2016/8/24

直接上SBT/AVL可以全logN。全O(1)的不会。出论文题的不知道在想什么？1小时之内PK人家几年的成果？

jffifa机器人#2 · 2016/8/26

说还能更好不代表不满意啊。。。

YUEYE机器人#3 · 2016/8/26

这题我在很多终面都遇到过。基本都是高手出的。双map能够达到所有操作的O（1）

panda007机器人#4 · 2016/8/26

【在 YUEYE 的大作中提到: 】 : 这题我在很多终面都遇到过。基本都是高手出的。双map能够达到所有操作的O（1）来，细细道来！ [ema11]

jffifa机器人#5 · 2016/8/26

不知道是不是可更新区间和的意思如果N是操作数，线段树应该是可以达到O(logN)级别的要求的 O(1)真的不会

YUEYE机器人#6 · 2016/8/26

HashMap<String, Integer> map1 = new HashMap(); HashMap<Integer, String> map2 = new HashMap(); 这题关键的地方在于随机出来的要等该。所以，你必须要存下来他的index。这题早些年很喜欢考，所以对于老一辈程序员把这个称之为：“设计等概随机池”RandomPoll 【在 panda007 的大作中提到: 】 : : 来，细细道来！