问一道题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道题

问一道题# JobHunting - 待字闺中

h*d2011-02-25 08:02

1 楼

从已知范围的n个连续数里面随机取出m个数,前后不可以重复
注：不许要maintain那个原始array,否则空间上就是O(n)
要求
时间上要优于O(m^2)，(假设m^2 < n)
空间上O(m)
大家帮我想想,刚才被问了这题,我说了洗牌算法和hashtable的解法,还被要求优化.....
他说什么keep被取出数的holes... 一紧张大脑就不转了

C*y2011-02-25 08:02

2 楼

只shuffle前m个就可以了
难道这还不是最优的？

...

【在 h**********d 的大作中提到】

: 从已知范围的n个连续数里面随机取出m个数,前后不可以重复
: 注：不许要maintain那个原始array,否则空间上就是O(n)
: 要求
: 时间上要优于O(m^2)，(假设m^2 < n)
: 空间上O(m)
: 大家帮我想想,刚才被问了这题,我说了洗牌算法和hashtable的解法,还被要求优化.....
: 他说什么keep被取出数的holes... 一紧张大脑就不转了

h*d2011-02-25 08:02

3 楼

shuffle空间上要maintain O(n)的原始数组，优化是他说不需要原始数组了，就已知一
个范围的连续整数，要怎么做。。

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

: 只shuffle前m个就可以了
: 难道这还不是最优的？
:
: ...

b*y2011-02-25 08:02

4 楼

go from the start of the array, and use a random integer generator for the
index,from 0 to n-1
in each loop, pickup the number indexed by the random integer, and swap it
with the current number.move the pointer to the next of the array element,
and make it as the current number.
do it iteratively until m times.

...

【在 h**********d 的大作中提到】

: shuffle空间上要maintain O(n)的原始数组，优化是他说不需要原始数组了，就已知一
: 个范围的连续整数，要怎么做。。

g*s2011-02-25 08:02

5 楼

1. take the first m number
2. for i = m+1 to n
use probability=m/i to pickup the i th number, to replace one(random)
of the m numbers.
Space : O(m)
Time : O(n)

...

【在 h**********d 的大作中提到】

: shuffle空间上要maintain O(n)的原始数组，优化是他说不需要原始数组了，就已知一
: 个范围的连续整数，要怎么做。。

h*d2011-02-25 08:02

6 楼

这就是我说的shuffle算法，这个算法需要维护那个原始array(because of swap)，空
间为O(n)了
现在不许要原始array，就已知一个范围的连续整数数来做

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

: go from the start of the array, and use a random integer generator for the
: index,from 0 to n-1
: in each loop, pickup the number indexed by the random integer, and swap it
: with the current number.move the pointer to the next of the array element,
: and make it as the current number.
: do it iteratively until m times.
:
: ...

h*d2011-02-25 08:02

7 楼

你说的是reservior sampling吗？
这个似乎没能take advantage of 连续整数，不过我mension了他说他没听说过。。。
气死了
前面我说那个O(m^2)，就是用一个ll 去存已生成的数，然后之后生成的一个个去比较
，需要优化时间复杂度，他提到keep track of the holes of 连续整数，但我还是没
想出来。。

【在 g***s 的大作中提到】

: 1. take the first m number
: 2. for i = m+1 to n
: use probability=m/i to pickup the i th number, to replace one(random)
: of the m numbers.
: Space : O(m)
: Time : O(n)
:
: ...

g*s2011-02-25 08:02

8 楼

similar idea, but better (my solution is scanning from 1 -> n, but this
one is from n to 1)
void genknuth(int m, int n)
{
srand((unsigned int)time(NULL));
for(int i = 0; i < n; i++)
{
if((rand() % (n - i)) < m)
{
cout<m--;
}
}
}

one(random)

【在 g***s 的大作中提到】

: 1. take the first m number
: 2. for i = m+1 to n
: use probability=m/i to pickup the i th number, to replace one(random)
: of the m numbers.
: Space : O(m)
: Time : O(n)
:
: ...

C*y2011-02-25 08:02

9 楼

这就是knuth的那个
要是interviewer 问为什么概率是一样的
应该如何回答

【在 g***s 的大作中提到】

: similar idea, but better (my solution is scanning from 1 -> n, but this
: one is from n to 1)
: void genknuth(int m, int n)
: {
: srand((unsigned int)time(NULL));
: for(int i = 0; i < n; i++)
: {
: if((rand() % (n - i)) < m)
: {
: cout<

g*s2011-02-25 08:02

10 楼

看我的方法。用数学归纳法很容易证明。

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

: 这就是knuth的那个
: 要是interviewer 问为什么概率是一样的
: 应该如何回答

h*d2011-02-25 08:02

11 楼

这space复杂读是O(m)?

【在 g***s 的大作中提到】

g*s2011-02-25 08:02

12 楼

yes. change count line to result.push(i).
then result's size is O(m).

【在 h**********d 的大作中提到】

: 这space复杂读是O(m)?

g*s2011-02-25 08:02

13 楼

so it's like given [low, high], randomly extract m numbers?
random_shuffle should work given the complexity O(m^2) and space O(m).
reservoir sampling, as grass point out, gives O(n) and space O(m).
so we can just combine them together. this is an interesting problem.
can u disclose which company it is?

...

【在 h**********d 的大作中提到】

C*y2011-02-25 08:02

14 楼

谢谢
看了半天，还是没太明白
能稍微详细点吗

【在 g***s 的大作中提到】

: 看我的方法。用数学归纳法很容易证明。

h*d2011-02-25 08:02

15 楼

就比如1-100连续数
他要keep track取出来的数的holes，如果存在linear data structure里面就需要O(m^
2)了

【在 g*********s 的大作中提到】

: so it's like given [low, high], randomly extract m numbers?
: random_shuffle should work given the complexity O(m^2) and space O(m).
: reservoir sampling, as grass point out, gives O(n) and space O(m).
: so we can just combine them together. this is an interesting problem.
: can u disclose which company it is?
:
: ...

g*s2011-02-25 08:02

16 楼

这个不是符合要求了吗？
一开始算一下m^2和n谁小。如果m^2小，用random_shuffle。如果n小，用reservoir
sampling。

m^

【在 h**********d 的大作中提到】

: 就比如1-100连续数
: 他要keep track取出来的数的holes，如果存在linear data structure里面就需要O(m^
: 2)了

h*d2011-02-25 08:02

17 楼

其实我也每明白
大牛能不能从连续整数空间上帮我想想，interviewer是这么引导我的，keep track of
连续整数空间上的holes，用linear data struct存时间就会O(m^2),怎么优化呢

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

: 谢谢
: 看了半天，还是没太明白
: 能稍微详细点吗

g*s2011-02-25 08:02

18 楼

bst, space still O(m) while time O(MlgM)

of

【在 h**********d 的大作中提到】

: 其实我也每明白
: 大牛能不能从连续整数空间上帮我想想，interviewer是这么引导我的，keep track of
: 连续整数空间上的holes，用linear data struct存时间就会O(m^2),怎么优化呢

h*d2011-02-25 08:02

19 楼

不是这意思，O(m^2)是我那个linked list存储已生成的数的解法，要比这个小

【在 g*********s 的大作中提到】

: 这个不是符合要求了吗？
: 一开始算一下m^2和n谁小。如果m^2小，用random_shuffle。如果n小，用reservoir
: sampling。
:
: m^

g*s2011-02-25 08:02

20 楼

p(i) mean the prob of the i-th item is selected.
if n=m, then all items are selected, so the each i, p(i) = (100%)
if m=k the method works, that means for the first k-th item, each item's
p(i) = m/k.
so, for the (k+1)-th item, if we use the prob= 1/(k+1) to pickup it, the
the p(k+1) = 1/(k+1). And if it is picked up, we use this item to replace
one of the m items. So, all the first k-th item's prob are same: (1-
1/(k+1))/k = 1/(k+1).
#

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

: 谢谢
: 看了半天，还是没太明白
: 能稍微详细点吗

h*d2011-02-25 08:02

21 楼

bst你怎么保证取出来每次插入都为balanced bst?

【在 g*********s 的大作中提到】

: bst, space still O(m) while time O(MlgM)
:
: of

g*s2011-02-25 08:02

22 楼

要求
时间上不可以超过O(m^2)或者O(n),whichever is smaller
空间上O(m)
then my solution meets all requirements ah.

【在 h**********d 的大作中提到】

: 不是这意思，O(m^2)是我那个linked list存储已生成的数的解法，要比这个小

g*s2011-02-25 08:02

23 楼

then just do balanced bst.

【在 h**********d 的大作中提到】

: bst你怎么保证取出来每次插入都为balanced bst?

h*d2011-02-25 08:02

24 楼

我可能说的不清楚，假设m^2比n小的话，问能不能优化到比m^2小

【在 g*********s 的大作中提到】

: 要求
: 时间上不可以超过O(m^2)或者O(n),whichever is smaller
: 空间上O(m)
: then my solution meets all requirements ah.

g*s2011-02-25 08:02

25 楼

if m^2
【在 h**********d 的大作中提到】

: 我可能说的不清楚，假设m^2比n小的话，问能不能优化到比m^2小

h*d2011-02-25 08:02

26 楼

how do you do a balanced bst?　from your randomly generated new numbers?
notice we are inserting new numbers into a bst here, not create a bst

【在 g*********s 的大作中提到】

: if m^2

g*s2011-02-25 08:02

27 楼

balanced bst's insert() algorithm will guarantee the tree is still
balanced after insertion.
u can check the algorithm in CLRS, red-black tree chapter.

【在 h**********d 的大作中提到】

: how do you do a balanced bst?　from your randomly generated new numbers?
: notice we are inserting new numbers into a bst here, not create a bst

C*y2011-02-25 08:02

28 楼

thanks
弄明白了
总的来说就是归纳法证明
假设第i个元素处理完后，每个元素（1...i)被选中的概率为k/i成立
再归纳证明第i+1处理完后，概率变为k/(i+1)

【在 g***s 的大作中提到】

: p(i) mean the prob of the i-th item is selected.
: if n=m, then all items are selected, so the each i, p(i) = (100%)
: if m=k the method works, that means for the first k-th item, each item's
: p(i) = m/k.
: so, for the (k+1)-th item, if we use the prob= 1/(k+1) to pickup it, the
: the p(k+1) = 1/(k+1). And if it is picked up, we use this item to replace
: one of the m items. So, all the first k-th item's prob are same: (1-
: 1/(k+1))/k = 1/(k+1).
: #