新鲜G面筋（2） - 未名空间MITBBS历史存档

r*d2012-10-23 07:10

1 楼

given random generator rand(int n)
now, design a random generator such as
rand(int n, int[] except)
example, n=10, random 1-10
now, except[3]={1,5,6}
then rand(10, except) output {2,3,4, 7, 8, 9,10}
提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

q*m2012-10-23 07:10

2 楼

难道不是和except里面的数值比较，是的话就扔掉继续sample ?

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

r*d2012-10-23 07:10

3 楼

说了，对方不满意
比如说n=10000
except 有9990
要是每次都check，效率太低

【在 q****m 的大作中提到】

: 难道不是和except里面的数值比较，是的话就扔掉继续sample ?

p*22012-10-23 07:10

4 楼

output {2,3,4, 7, 8, 9,10}
这个为什么是顺序的？

r*d2012-10-23 07:10

5 楼

不是，随机的，就是说除了except,其它随机输出

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

: output {2,3,4, 7, 8, 9,10}
: 这个为什么是顺序的？

r*d2012-10-23 07:10

6 楼

不是，随机的，就是说除了except,其它随机输出

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

: output {2,3,4, 7, 8, 9,10}
: 这个为什么是顺序的？

q*m2012-10-23 07:10

7 楼

不能先 sort except 吗？然后每次对随机数 binary search ?

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

: 说了，对方不满意
: 比如说n=10000
: except 有9990
: 要是每次都check，效率太低

p*22012-10-23 07:10

8 楼

跟interval tree一类的有关系吗？

l*i2012-10-23 07:10

9 楼

Can you just generate 1 to n-k, if you have k except
then map back to the original numbers.
In your example, except = {1,5,6}
then you generate a number in [1..7]
let's say the number is x
then you need to map x to the original number
[1,2,3,4,5,6,7]
[2,3,4,7,8,9,10]
i=1;
while (i in except) { ++i; }
j=1;
while(i != j) {
++j; ++i;
while(i in except) ++i;
}

f*t2012-10-23 07:10

10 楼

你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
然后
idx = rand(include.size())
return include[idx]

f*42012-10-23 07:10

11 楼

如果n很大呢?
考虑使用except.size()的空间

【在 f*******t 的大作中提到】

: 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
: 然后
: idx = rand(include.size())
: return include[idx]

o*e2012-10-23 07:10

12 楼

http://www.careercup.com/question?id=9865865
here you go...

C*U2012-10-23 07:10

13 楼

先分成几个interval
先取interval
再从里面取数

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

R*n2012-10-23 07:10

14 楼

几个interval 的概率是不一样的。

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

: 先分成几个interval
: 先取interval
: 再从里面取数

e*s2012-10-23 07:10

15 楼

我同意。不过except[] 要先sort, 所以O(nlogn)。

【在 f*******t 的大作中提到】

: 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
: 然后
: idx = rand(include.size())
: return include[idx]

C*U2012-10-23 07:10

16 楼

He did not require uniform.

【在 R*******n 的大作中提到】

: 几个interval 的概率是不一样的。

h*u2012-10-23 07:10

17 楼

Mark

C*U2012-10-23 07:10

18 楼

请问楼主这个需要uniform么？

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

w*o2012-10-23 07:10

19 楼

我觉得应该问面试官以下几个问题before coding
1. except 是sorted吗？
2. except是［1..n]吗？
3. except 是每次都一样的吗？如果一样，可以做预处理

l*a2012-10-23 07:10

20 楼

正解。

【在 o****e 的大作中提到】

: http://www.careercup.com/question?id=9865865
: here you go...

r*d2012-10-23 07:10

21 楼

given random generator rand(int n)
now, design a random generator such as
rand(int n, int[] except)
example, n=10, random 1-10
now, except[3]={1,5,6}
then rand(10, except) output {2,3,4, 7, 8, 9,10}
提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

q*m2012-10-23 07:10

22 楼

难道不是和except里面的数值比较，是的话就扔掉继续sample ?

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

r*d2012-10-23 07:10

23 楼

说了，对方不满意
比如说n=10000
except 有9990
要是每次都check，效率太低

【在 q****m 的大作中提到】

: 难道不是和except里面的数值比较，是的话就扔掉继续sample ?

p*22012-10-23 07:10

24 楼

output {2,3,4, 7, 8, 9,10}
这个为什么是顺序的？

r*d2012-10-23 07:10

25 楼

不是，随机的，就是说除了except,其它随机输出

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

: output {2,3,4, 7, 8, 9,10}
: 这个为什么是顺序的？

r*d2012-10-23 07:10

26 楼

不是，随机的，就是说除了except,其它随机输出

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

: output {2,3,4, 7, 8, 9,10}
: 这个为什么是顺序的？

q*m2012-10-23 07:10

27 楼

不能先 sort except 吗？然后每次对随机数 binary search ?

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

: 说了，对方不满意
: 比如说n=10000
: except 有9990
: 要是每次都check，效率太低

p*22012-10-23 07:10

28 楼

跟interval tree一类的有关系吗？

l*i2012-10-23 07:10

29 楼

Can you just generate 1 to n-k, if you have k except
then map back to the original numbers.
In your example, except = {1,5,6}
then you generate a number in [1..7]
let's say the number is x
then you need to map x to the original number
[1,2,3,4,5,6,7]
[2,3,4,7,8,9,10]
i=1;
while (i in except) { ++i; }
j=1;
while(i != j) {
++j; ++i;
while(i in except) ++i;
}

f*t2012-10-23 07:10

30 楼

你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
然后
idx = rand(include.size())
return include[idx]

f*42012-10-23 07:10

31 楼

如果n很大呢?
考虑使用except.size()的空间

【在 f*******t 的大作中提到】

: 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
: 然后
: idx = rand(include.size())
: return include[idx]

o*e2012-10-23 07:10

32 楼

http://www.careercup.com/question?id=9865865
here you go...

C*U2012-10-23 07:10

33 楼

先分成几个interval
先取interval
再从里面取数

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

R*n2012-10-23 07:10

34 楼

几个interval 的概率是不一样的。

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

: 先分成几个interval
: 先取interval
: 再从里面取数

e*s2012-10-23 07:10

35 楼

我同意。不过except[] 要先sort, 所以O(nlogn)。

【在 f*******t 的大作中提到】

: 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
: 然后
: idx = rand(include.size())
: return include[idx]

C*U2012-10-23 07:10

36 楼

He did not require uniform.

【在 R*******n 的大作中提到】

: 几个interval 的概率是不一样的。

h*u2012-10-23 07:10

37 楼

Mark

C*U2012-10-23 07:10

38 楼

请问楼主这个需要uniform么？

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

w*o2012-10-23 07:10

39 楼

我觉得应该问面试官以下几个问题before coding
1. except 是sorted吗？
2. except是［1..n]吗？
3. except 是每次都一样的吗？如果一样，可以做预处理

l*a2012-10-23 07:10

40 楼

正解。

【在 o****e 的大作中提到】

: http://www.careercup.com/question?id=9865865
: here you go...

j*22012-10-23 07:10

41 楼

这个没人讨论下？是用bucket还是怎样啊？

h*i2012-10-23 07:10

42 楼

要是except的建一个bloom filter，只用处理false positive的情况。

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

: 说了，对方不满意
: 比如说n=10000
: except 有9990
: 要是每次都check，效率太低

B*t2012-10-23 07:10

43 楼

可以建一个二叉树，叶子保存interval, 内部结点保存所有孩子区间长度这样就能保
证uniform了

【在 R*******n 的大作中提到】

: 几个interval 的概率是不一样的。

Y*f2012-10-23 07:10

44 楼

首先sort except，然后用rand产生的数对数组except数组做binanry search（这个要
修改一下比较函数，不是和元素本身比较，而是与数组元素-元素index比较），时间
复杂度O(mlogm), m是except数组大小。

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

m*92012-10-23 07:10

45 楼

1. 新建一个长度为n-except的数组:
array = []
2. 数组的值是except外的值:
for i in range(n):
if i not in except:
array.append(i)
3. 随机返回数组里面对应的数：
return array[rand(n-len(except))]

j*x2012-10-23 07:10

46 楼

写了一个小时，没考虑特别的corner case，O(num of intervals of "except")，用了
上面提到的binary search：
#include
#include
#include
#include
#include
struct compareable_interval {
int start;
int end;
int real_start;
int real_end;

compareable_interval(int lhs, int rhs) : start(lhs), end(rhs), real_
start(lhs), real_end(rhs) {
}
compareable_interval(int l, int r, int rl, int rr) : start(l), end(r),
real_start(rl), real_end(rr) {
}
bool inside(int val) const {
return val >= start && val <= end;
}
int realValue(int val) const {
return real_start + val - start;
}

bool operatorreturn end < other.start;
}
bool operator==(const compareable_interval& other) const {
return inside(other.start) && inside(other.end);
}
friend std::ostream& operator<interval& other) {
out<return out;
}
};
std::vector compile(const std::vector& nums, int
n) {
std::vector res;
int prev_start = nums.front();
int prev = nums.front();
if (prev > 0) {
compareable_interval interval(0, prev_start - 1, 0, prev_start - 1);
res.push_back(interval);
}
typedef std::vector::const_iterator itor;
itor idx = nums.begin();
for (++idx; idx != nums.end(); ++idx) {
int cur = *idx;
if (cur != prev + 1) {
int len = cur - prev - 1;
compareable_interval interval(prev_start, prev_start + len - 1,
prev + 1, cur - 1);
res.push_back(interval);
prev = cur;
prev_start = prev_start + len;
} else {
prev = cur;
}
}
int len = n - prev - 1;
if (len > 0) {
compareable_interval interval_last(prev_start, prev_start + len - 1,
prev + 1, n - 1);
res.push_back(interval_last);
}
return res;
}
int rand(int n, const std::vector& except) {
std::vector candidate = compile(except, n);
int m = n - except.size();
int val = rand() % m;
typedef std::vector::iterator itor;
compareable_interval interval(val, val);
itor found = std::lower_bound(candidate.begin(), candidate.end(),
interval);
return found->realValue(val);
}
int main() {
std::vector nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(4);
nums.push_back(9);
std::vector res = compile(nums, 10);
std::copy(res.begin(), res.end(), std::ostream_iteratorinterval>(std::cout, "\n"));
srand(time(0));
std::cout<}

j*22012-10-23 07:10

47 楼

这个没人讨论下？是用bucket还是怎样啊？

h*i2012-10-23 07:10

48 楼

要是except的建一个bloom filter，只用处理false positive的情况。

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

: 说了，对方不满意
: 比如说n=10000
: except 有9990
: 要是每次都check，效率太低

B*t2012-10-23 07:10

49 楼

可以建一个二叉树，叶子保存interval, 内部结点保存所有孩子区间长度这样就能保
证uniform了

【在 R*******n 的大作中提到】

: 几个interval 的概率是不一样的。

Y*f2012-10-23 07:10

50 楼

首先sort except，然后用rand产生的数对数组except数组做binanry search（这个要
修改一下比较函数，不是和元素本身比较，而是与数组元素-元素index比较），时间
复杂度O(mlogm), m是except数组大小。

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

m*92012-10-23 07:10

51 楼

1. 新建一个长度为n-except的数组:
array = []
2. 数组的值是except外的值:
for i in range(n):
if i not in except:
array.append(i)
3. 随机返回数组里面对应的数：
return array[rand(n-len(except))]

j*x2012-10-23 07:10

52 楼

写了一个小时，没考虑特别的corner case，O(num of intervals of "except")，用了
上面提到的binary search：
#include
#include
#include
#include
#include
struct compareable_interval {
int start;
int end;
int real_start;
int real_end;

compareable_interval(int lhs, int rhs) : start(lhs), end(rhs), real_
start(lhs), real_end(rhs) {
}
compareable_interval(int l, int r, int rl, int rr) : start(l), end(r),
real_start(rl), real_end(rr) {
}
bool inside(int val) const {
return val >= start && val <= end;
}
int realValue(int val) const {
return real_start + val - start;
}

bool operatorreturn end < other.start;
}
bool operator==(const compareable_interval& other) const {
return inside(other.start) && inside(other.end);
}
friend std::ostream& operator<interval& other) {
out<return out;
}
};
std::vector compile(const std::vector& nums, int
n) {
std::vector res;
int prev_start = nums.front();
int prev = nums.front();
if (prev > 0) {
compareable_interval interval(0, prev_start - 1, 0, prev_start - 1);
res.push_back(interval);
}
typedef std::vector::const_iterator itor;
itor idx = nums.begin();
for (++idx; idx != nums.end(); ++idx) {
int cur = *idx;
if (cur != prev + 1) {
int len = cur - prev - 1;
compareable_interval interval(prev_start, prev_start + len - 1,
prev + 1, cur - 1);
res.push_back(interval);
prev = cur;
prev_start = prev_start + len;
} else {
prev = cur;
}
}
int len = n - prev - 1;
if (len > 0) {
compareable_interval interval_last(prev_start, prev_start + len - 1,
prev + 1, n - 1);
res.push_back(interval_last);
}
return res;
}
int rand(int n, const std::vector& except) {
std::vector candidate = compile(except, n);
int m = n - except.size();
int val = rand() % m;
typedef std::vector::iterator itor;
compareable_interval interval(val, val);
itor found = std::lower_bound(candidate.begin(), candidate.end(),
interval);
return found->realValue(val);
}
int main() {
std::vector nums;
nums.push_back(1);
nums.push_back(2);
nums.push_back(4);
nums.push_back(9);
std::vector res = compile(nums, 10);
std::copy(res.begin(), res.end(), std::ostream_iteratorinterval>(std::cout, "\n"));
srand(time(0));
std::cout<}

h*i2012-10-23 07:10

53 楼

此题看样有些频率, 就是考binary search.

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

x*02012-10-23 07:10

54 楼

mark

s*x2012-10-23 07:10

55 楼

切磋一下. running time 应该是 less than log(K)
public class RandomNextIntExceptK {
private int[] kk;
private int[] kAdd;
private Random rand = new Random();
public RandomNextIntExceptK(int[] k) {
Map kCount = new TreeMap();
for (int i = 0; i < k.length; i++)
{
int key = k[i] - i;
if (kCount.containsKey(key))
{
int count = kCount.get(key);
kCount.put(key, count + 1);
}
else
{
kCount.put(key, 1);
}
}

this.kk = new int[kCount.size()];
this.kAdd = new int[kCount.size()];
int index = 0, sum = 0;
for (Map.Entry entry : kCount.entrySet())
{
this.kk[index] = entry.getKey();
int count = entry.getValue();
this.kAdd[index] = sum + count;
sum += count;
index++;
}
}

public int nextInt2(int n) {
int result = rand.nextInt(n - k.length);
if (result >= this.kk[0])
{
int indexInK = binarySearch(this.kk, result);
result += this.kAdd[indexInK];
}
return result;
}
/**
k = [1, 3, 4, 7, 8]
kk = [1, 2, 2, 4, 4] => [1(1), 2(2), 4(2)]
kAdd = [1, 3, 3, 5, 5] => [1(1), 2(3), 4(5)]
n - k.length = 5
[0, 1, 2, 3, 4] => [0, 2, 5, 6, 9] => [+0, (>=1)+1, (>=2)+3, (>=2)+3, (>=4)+
5]
*/
public static void main(String[] args) {
int[] k = new int[]{1, 3, 4, 7, 8};
RandomNextIntExceptK r = new RandomNextIntExceptK(k);
for (int i = 0; i < 100 ; i++)
{
System.out.print(r.nextInt(10));
}
}
// int[] a = new int[] {1, 3, 5, 9};
// 0 or 1 or 2 -> return i = 0 where a[0] = 1
// 3 or 4 -> return i = 1 where a[1] = 3
// 5 or 6 or 7 or 8 -> return i = 2 where a[2] = 5
// 9 or 10 or bigger -> return i = 3 where a[3] = 9
private static int binarySearch(int[] a, int targetNum) {
// if (a[0] > targetNum) return 0;
// if (a[a.length -1] < targetNum) return a.length - 1;
int low = 0;
int high = a.length - 1;
while(true) {
int mid = low + ((high - low) >>> 1); // divide by 2
if (high <= low) {
return low;
}

if (a[mid] == targetNum || (a[mid] < targetNum && targetNum < a[
mid+1])) {
return mid;
}

if (a[mid] < targetNum) {
low = mid + 1;
} else { // a[mid] > targetNum
high = mid - 1;
}
}
}
}

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

: given random generator rand(int n)
: now, design a random generator such as
: rand(int n, int[] except)
: example, n=10, random 1-10
: now, except[3]={1,5,6}
: then rand(10, except) output {2,3,4, 7, 8, 9,10}
: 提到hashtable, 对方说，如果n很大，百万，output 几个数，怎么办？

h*a2012-10-23 07:10

56 楼

career cup上的回帖绝大部分都是浪费读者的时间

【在 o****e 的大作中提到】

: http://www.careercup.com/question?id=9865865
: here you go...

p*22012-10-23 07:10

57 楼

大牛说说怎么做比较好？

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

: career cup上的回帖绝大部分都是浪费读者的时间

h*a2012-10-23 07:10

58 楼

赞，写的不错

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

: 切磋一下. running time 应该是 less than log(K)
: public class RandomNextIntExceptK {
: private int[] kk;
: private int[] kAdd;
: private Random rand = new Random();
: public RandomNextIntExceptK(int[] k) {
: Map kCount = new TreeMap();
: for (int i = 0; i < k.length; i++)
: {
: int key = k[i] - i;

h*a2012-10-23 07:10

59 楼

我不是大牛，你才是大牛。回大牛，我觉得seattlexxx写的不错，我正在学习体会。

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

:
: 大牛说说怎么做比较好？

h*i2012-10-23 07:10

60 楼

hints: 不要用任何的辅助数组,题目已经说了excpts可以很大.

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

: 切磋一下. running time 应该是 less than log(K)
: public class RandomNextIntExceptK {
: private int[] kk;
: private int[] kAdd;
: private Random rand = new Random();
: public RandomNextIntExceptK(int[] k) {
: Map kCount = new TreeMap();
: for (int i = 0; i < k.length; i++)
: {
: int key = k[i] - i;

h*a2012-10-23 07:10

61 楼

能不能share一下怎么不用额外空间光binary search找到下一个合适的random number?

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

: hints: 不要用任何的辅助数组,题目已经说了excpts可以很大.