r**d
发帖数: 90 | 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****m
发帖数: 177 | 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**d
发帖数: 90 | 3 说了，对方不满意
比如说n=10000
except 有9990
要是每次都check，效率太低
【在 q****m 的大作中提到】
: 难道不是和except里面的数值比较，是的话就扔掉继续sample ?
| p*****2
发帖数: 21240 | 4 output {2,3,4, 7, 8, 9,10}
这个为什么是顺序的？ | r**d
发帖数: 90 | 5 不是，随机的，就是说除了except,其它随机输出
【在 p*****2 的大作中提到】
: output {2,3,4, 7, 8, 9,10}
: 这个为什么是顺序的？
| r**d
发帖数: 90 | 6 不是，随机的，就是说除了except,其它随机输出
【在 p*****2 的大作中提到】
: output {2,3,4, 7, 8, 9,10}
: 这个为什么是顺序的？
| q****m
发帖数: 177 | 7 不能先 sort except 吗？ 然后每次对随机数 binary search ?
【在 r**d 的大作中提到】
: 说了，对方不满意
: 比如说n=10000
: except 有9990
: 要是每次都check，效率太低
| p*****2
发帖数: 21240 | | l***i
发帖数: 1309 | 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*******t
发帖数: 7549 | 10 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
然后
idx = rand(include.size())
return include[idx] | | | f*******4
发帖数: 64 | 11 如果n很大呢?
考虑使用except.size()的空间
【在 f*******t 的大作中提到】
: 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
: 然后
: idx = rand(include.size())
: return include[idx]
| o****e
发帖数: 916 | | C***U
发帖数: 2406 | 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*******n
发帖数: 162 | 14 几个interval 的 概率是不一样的。
【在 C***U 的大作中提到】
: 先分成几个interval
: 先取interval
: 再从里面取数
| e***s
发帖数: 799 | 15 我同意。不过except[] 要先sort, 所以O(nlogn)。
【在 f*******t 的大作中提到】
: 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
: 然后
: idx = rand(include.size())
: return include[idx]
| C***U
发帖数: 2406 | 16 He did not require uniform.
【在 R*******n 的大作中提到】
: 几个interval 的 概率是不一样的。
| h*u
发帖数: 122 | | C***U
发帖数: 2406 | 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***o
发帖数: 109 | 19 我觉得应该问面试官以下几个问题before coding
1. except 是sorted吗？
2. except是［1..n]吗？
3. except 是每次都一样的吗？如果一样，可以做预处理 | l*****a
发帖数: 559 | | | | r**d
发帖数: 90 | 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****m
发帖数: 177 | 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**d
发帖数: 90 | 23 说了，对方不满意
比如说n=10000
except 有9990
要是每次都check，效率太低
【在 q****m 的大作中提到】
: 难道不是和except里面的数值比较，是的话就扔掉继续sample ?
| p*****2
发帖数: 21240 | 24 output {2,3,4, 7, 8, 9,10}
这个为什么是顺序的？ | r**d
发帖数: 90 | 25 不是，随机的，就是说除了except,其它随机输出
【在 p*****2 的大作中提到】
: output {2,3,4, 7, 8, 9,10}
: 这个为什么是顺序的？
| r**d
发帖数: 90 | 26 不是，随机的，就是说除了except,其它随机输出
【在 p*****2 的大作中提到】
: output {2,3,4, 7, 8, 9,10}
: 这个为什么是顺序的？
| q****m
发帖数: 177 | 27 不能先 sort except 吗？ 然后每次对随机数 binary search ?
【在 r**d 的大作中提到】
: 说了，对方不满意
: 比如说n=10000
: except 有9990
: 要是每次都check，效率太低
| p*****2
发帖数: 21240 | | l***i
发帖数: 1309 | 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*******t
发帖数: 7549 | 30 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
然后
idx = rand(include.size())
return include[idx] | | | f*******4
发帖数: 64 | 31 如果n很大呢?
考虑使用except.size()的空间
【在 f*******t 的大作中提到】
: 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
: 然后
: idx = rand(include.size())
: return include[idx]
| o****e
发帖数: 916 | | C***U
发帖数: 2406 | 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*******n
发帖数: 162 | 34 几个interval 的 概率是不一样的。
【在 C***U 的大作中提到】
: 先分成几个interval
: 先取interval
: 再从里面取数
| e***s
发帖数: 799 | 35 我同意。不过except[] 要先sort, 所以O(nlogn)。
【在 f*******t 的大作中提到】
: 你有except[],从{1,...,n}里去掉它可以得出include[]，复杂度O(n)
: 然后
: idx = rand(include.size())
: return include[idx]
| C***U
发帖数: 2406 | 36 He did not require uniform.
【在 R*******n 的大作中提到】
: 几个interval 的 概率是不一样的。
| h*u
发帖数: 122 | | C***U
发帖数: 2406 | 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***o
发帖数: 109 | 39 我觉得应该问面试官以下几个问题before coding
1. except 是sorted吗？
2. except是［1..n]吗？
3. except 是每次都一样的吗？如果一样，可以做预处理 | l*****a
发帖数: 559 | | | | j******2
发帖数: 362 | | h***i
发帖数: 1970 | 42 要是except的建一个bloom filter，只用处理false positive的情况。
【在 r**d 的大作中提到】
: 说了，对方不满意
: 比如说n=10000
: except 有9990
: 要是每次都check，效率太低
| B********t
发帖数: 147 | 43 可以建一个二叉树，叶子保存interval, 内部结点保存所有孩子区间长度 这样就能保
证uniform了
【在 R*******n 的大作中提到】
: 几个interval 的 概率是不一样的。
| Y********f
发帖数: 410 | 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****9
发帖数: 492 | 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********x
发帖数: 2330 | 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 operator<(const compareable_interval& other) const {
return end < other.start;
}
bool operator==(const compareable_interval& other) const {
return inside(other.start) && inside(other.end);
}
friend std::ostream& operator<<(std::ostream& out, const compareable_
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_iterator
interval>(std::cout, "\n"));
srand(time(0));
std::cout<
} | j******2
发帖数: 362 | | h***i
发帖数: 1970 | 48 要是except的建一个bloom filter，只用处理false positive的情况。
【在 r**d 的大作中提到】
: 说了，对方不满意
: 比如说n=10000
: except 有9990
: 要是每次都check，效率太低
| B********t
发帖数: 147 | 49 可以建一个二叉树，叶子保存interval, 内部结点保存所有孩子区间长度 这样就能保
证uniform了
【在 R*******n 的大作中提到】
: 几个interval 的 概率是不一样的。
| Y********f
发帖数: 410 | 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****9
发帖数: 492 | 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********x
发帖数: 2330 | 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 operator<(const compareable_interval& other) const {
return end < other.start;
}
bool operator==(const compareable_interval& other) const {
return inside(other.start) && inside(other.end);
}
friend std::ostream& operator<<(std::ostream& out, const compareable_
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_iterator
interval>(std::cout, "\n"));
srand(time(0));
std::cout<
} | h***i
发帖数: 1970 | 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*****0
发帖数: 452 | | s********x
发帖数: 914 | 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*****a
发帖数: 1718 | 56 career cup上的回帖绝大部分都是浪费读者的时间
【在 o****e 的大作中提到】
: http://www.careercup.com/question?id=9865865
: here you go...
| p*****2
发帖数: 21240 | 57
大牛说说怎么做比较好？
【在 h*****a 的大作中提到】
: career cup上的回帖绝大部分都是浪费读者的时间
| h*****a
发帖数: 1718 | 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*****a
发帖数: 1718 | 59 我不是大牛，你才是大牛。回大牛，我觉得seattlexxx写的不错，我正在学习体会。
【在 p*****2 的大作中提到】
:
: 大牛说说怎么做比较好？
| h***i
发帖数: 1970 | 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*****a
发帖数: 1718 | 61 能不能share一下怎么不用额外空间光binary search找到下一个合适的random number?
【在 h***i 的大作中提到】
: hints: 不要用任何的辅助数组,题目已经说了excpts可以很大.
|
|
