由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一道题
相关主题
贡献两个面经吧Zillow screen 面经,兼打听工资
Dynamical Programming该如何复习求整数对排序算法
大家有没有经历过interviewer出错的时候?CLRS 这本书要看哪几章?
问一道古老的面试题key 相同的话怎么搞 direct access table 阿?
碰到不置可否的面试官怎么办?Potential error in the algorithm RB-INSERT-FIXUP in CLRS (p.316, 3rd ed.)?
Google onsite 5天后被拒了最近连着几个面试都是印度人。
请教一个题目google phone interview
面试题库除了careercup还有哪里有?有这样的东西么(描述见内)小公司软工第一轮电面
相关话题的讨论汇总
话题: bst话题: random话题: item话题: th话题: space
进入JobHunting版参与讨论
1 (共1页)
h**********d
发帖数: 4313
1
从已知范围的n个连续数里面随机取出m个数,前后不可以重复
注:不许要maintain那个原始array,否则空间上就是O(n)
要求
时间上要优于O(m^2),(假设m^2 < n)
空间上O(m)
大家帮我想想,刚才被问了这题,我说了洗牌算法和hashtable的解法,还被要求优化.....
他说什么keep被取出数的holes... 一紧张大脑就不转了
C***y
发帖数: 2546
2
只shuffle前m个就可以了
难道这还不是最优的?

...

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

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

【在 C***y 的大作中提到】
: 只shuffle前m个就可以了
: 难道这还不是最优的?
:
: ...

b*******y
发帖数: 16
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***s
发帖数: 3811
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**********d
发帖数: 4313
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**********d
发帖数: 4313
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***s
发帖数: 3811
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***y
发帖数: 2546
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***s
发帖数: 3811
10
看我的方法。用数学归纳法很容易证明。

【在 C***y 的大作中提到】
: 这就是knuth的那个
: 要是interviewer 问为什么概率是一样的
: 应该如何回答

相关主题
Google onsite 5天后被拒了Zillow screen 面经,兼打听工资
请教一个题目求整数对排序算法
面试题库除了careercup还有哪里有?有这样的东西么(描述见内)CLRS 这本书要看哪几章?
进入JobHunting版参与讨论
h**********d
发帖数: 4313
11
这space复杂读是O(m)?

【在 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***s
发帖数: 3811
12
yes. change count line to result.push(i).
then result's size is O(m).

【在 h**********d 的大作中提到】
: 这space复杂读是O(m)?
g*********s
发帖数: 1782
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 的大作中提到】
: 从已知范围的n个连续数里面随机取出m个数,前后不可以重复
: 注:不许要maintain那个原始array,否则空间上就是O(n)
: 要求
: 时间上要优于O(m^2),(假设m^2 < n)
: 空间上O(m)
: 大家帮我想想,刚才被问了这题,我说了洗牌算法和hashtable的解法,还被要求优化.....
: 他说什么keep被取出数的holes... 一紧张大脑就不转了

C***y
发帖数: 2546
14
谢谢
看了半天,还是没太明白
能稍微详细点吗

【在 g***s 的大作中提到】
: 看我的方法。用数学归纳法很容易证明。
h**********d
发帖数: 4313
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*********s
发帖数: 1782
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**********d
发帖数: 4313
17
其实我也每明白
大牛能不能从连续整数空间上帮我想想,interviewer是这么引导我的,keep track of
连续整数空间上的holes,用linear data struct存时间就会O(m^2),怎么优化呢

【在 C***y 的大作中提到】
: 谢谢
: 看了半天,还是没太明白
: 能稍微详细点吗

g*********s
发帖数: 1782
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**********d
发帖数: 4313
19
不是这意思,O(m^2)是我那个linked list存储已生成的数的解法,要比这个小

【在 g*********s 的大作中提到】
: 这个不是符合要求了吗?
: 一开始算一下m^2和n谁小。如果m^2小,用random_shuffle。如果n小,用reservoir
: sampling。
:
: m^

g***s
发帖数: 3811
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 的大作中提到】
: 谢谢
: 看了半天,还是没太明白
: 能稍微详细点吗

相关主题
key 相同的话怎么搞 direct access table 阿?google phone interview
Potential error in the algorithm RB-INSERT-FIXUP in CLRS (p.316, 3rd ed.)?小公司软工第一轮电面
最近连着几个面试都是印度人。用什么数据结构快速insert, get median
进入JobHunting版参与讨论
h**********d
发帖数: 4313
21
bst你怎么保证取出来每次插入都为balanced bst?

【在 g*********s 的大作中提到】
: bst, space still O(m) while time O(MlgM)
:
: of

g*********s
发帖数: 1782
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*********s
发帖数: 1782
23
then just do balanced bst.

【在 h**********d 的大作中提到】
: bst你怎么保证取出来每次插入都为balanced bst?
h**********d
发帖数: 4313
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*********s
发帖数: 1782
25
if m^2
【在 h**********d 的大作中提到】
: 我可能说的不清楚,假设m^2比n小的话,问能不能优化到比m^2小
h**********d
发帖数: 4313
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*********s
发帖数: 1782
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***y
发帖数: 2546
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).
: #

1 (共1页)
进入JobHunting版参与讨论
相关主题
小公司软工第一轮电面碰到不置可否的面试官怎么办?
用什么数据结构快速insert, get medianGoogle onsite 5天后被拒了
问道题请教一个题目
shuffle card 算法面试题库除了careercup还有哪里有?有这样的东西么(描述见内)
贡献两个面经吧Zillow screen 面经,兼打听工资
Dynamical Programming该如何复习求整数对排序算法
大家有没有经历过interviewer出错的时候?CLRS 这本书要看哪几章?
问一道古老的面试题key 相同的话怎么搞 direct access table 阿?
相关话题的讨论汇总
话题: bst话题: random话题: item话题: th话题: space