一个set，有add(i), del(i), count(i), size。写random()。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一个set，有add(i), del(i), count(i), size。写random()。

一个set，有add(i), del(i), count(i), size。写random()。# JobHunting - 待字闺中

y*r2013-04-10 07:04

1 楼

一个package要signature，投递了三次病人没法收。病人要我call fedex 去掉
signature requirement.
病人和fedex打了两次电话，fedex说要shipper打。我打了两次，都说去不掉。
病人急了，说那我不要了。
我急了，行情跌了这么多，你不要我也不能退给护士了。
我就又给fedex打电话，说，你要是去不掉signature，please deliver it to pacafic
ocean, I don't want it back。
折腾半天，又说行了。
真烂，这些员工都没培训过？

j*22013-04-10 07:04

2 楼

请问这题的count(i)究竟咩意思？
二爷为何说这题跟O(1) add(), del(), rand() data structure 那题一样？恕愚钝。
难道是：用random产生0到size()间的整数i，然后遍历整个set，凡count(j)>count(
i)的，delete之并存之。然后delete(i)。最后把delete的其他数又insert进去。
感觉很不efficient但是题目不要求complexity的话也可以。

I*92013-04-10 07:04

3 楼

drive a airplane and crash into fEdEx HQ

l*a2013-04-10 07:04

4 楼

把题目说清楚点,不要道听途说的题都拿出来
另外,数据结构相关题目提到random access,都是用数组index访问
跟概率无关

【在 j******2 的大作中提到】

: 请问这题的count(i)究竟咩意思？
: 二爷为何说这题跟O(1) add(), del(), rand() data structure 那题一样？恕愚钝。
: 难道是：用random产生0到size()间的整数i，然后遍历整个set，凡count(j)>count(
: i)的，delete之并存之。然后delete(i)。最后把delete的其他数又insert进去。
: 感觉很不efficient但是题目不要求complexity的话也可以。

a*e2013-04-10 07:04

5 楼

病人不会去pickup？

pacafic

【在 y***r 的大作中提到】

: 一个package要signature，投递了三次病人没法收。病人要我call fedex 去掉
: signature requirement.
: 病人和fedex打了两次电话，fedex说要shipper打。我打了两次，都说去不掉。
: 病人急了，说那我不要了。
: 我急了，行情跌了这么多，你不要我也不能退给护士了。
: 我就又给fedex打电话，说，你要是去不掉signature，please deliver it to pacafic
: ocean, I don't want it back。
: 折腾半天，又说行了。
: 真烂，这些员工都没培训过？

j*22013-04-10 07:04

6 楼

原题如下
Given a set, and functions insert(i), delete(i), count(i), size(), random.
Design a data structure and implement PopRandom() to pop a random element
from the set and return it.