设计一个generic class，要求支持add(T), remove(T), randomRemove(T)三个操作，并且必须保证都是O(1)。比如说add(cat), add(dog), add(pig), add(cat), remove(cat), remove(dog)等等，她还特意说必须要考虑重复，也就是说删掉一个cat后另一个cat必须还在，而且randomRemove()必须保证所有元素被删掉的概率均等。
所以这题应该是用第一个HashMap放index + 元素内容，重复的元素要分开放，第二个HashMap放元素内容＋arrayList of indexes，把重复元素的indexes放在一起。所以上面的例子就应该是HashMap1 : (1, cat), (2, dog), (3, pig), (4, cat), HashMap2: (cat, (1, 4)), (dog, 2), (pig, 3)这样。add, remove很容易O(1)，randomRemove()时生成一个1-4的随机数，比如2，然后从第一个map里找2对应的是dog，然后从第二个HashMap里找到dog，把dog删掉。但有一个小问题我觉得她自己也没想清楚，就是如果有很多dog，那么dog的list很长，并不能保证O(1)找到要删的那个dog的index吧？。。另外还有一个trick，就是删掉dog后，要用第一个map中的最后一个元素去填补中间的gap，否则下次如果再生成随机数2，就找不到元素了。
[?]*Add, Remove and randomRemove in O(1)
原文：http://www.cnblogs.com/hygeia/p/5156453.html