面试题精选:数据伪造
source link: https://zxs.io/article/1750
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
面试题精选:数据伪造
这道题应该算是我原创的的一道题,来源于我遇到的一个具体需求。大致需求是已知一批数和每个数出现的次数,然后写个接口,每次调用都能返回已知数据中的某个数,且返回的概率和原始数据中每个数出现的概率一致,题目描述起来有些绕口,我们来举个实际的例子。
以上面的输入为例,要求实现的接口必须以11.96%的概率返回5、18.10%的概率返回91……16.55%的概率返回98,当然我的要求不仅仅是这几个数,而是可能有10^5个数。 先别急着往下看,给你几分钟先思考下。
各种语言其实都内置了random函数,可以随机返回int或者long型的随机数,这里我们先不考虑溢出的问题。为了方便讲解,假设我们已有n个数存在在num[n]中,其出现的频次存放在fre[n]中。 借助已有的random(),我们很简单就可以生成0-n之间的一个随机数i,但是如果直接返回num[i]的话,每个数返回的概率是一致的,明显不满足我们的需求。
其实解决方案也很简单,我们按照每个数出现的频次大小,将其映射成不同的区间大小,出现的概率越大,区间越大。想象下,这些数据按不同的区间大小把一个飞镖盘分成不同的部分,我们生成数的时候就是拿个飞镖随机扎,扎到哪个算哪个。
当然我们可以直接用一位直线区间描述上面的二维飞镖盘模型。只需要随机生成0-100%之间的数即可,假设某次随机生成的数是0.65(65%),我们算一下 正好对应在数字58对应的区间上,所以这次直接返回58就是了,我们可以开始写代码了。
int[] num; // 数字
int[] fre; // 出现的频次
double[] pro; // 出现的概率
int n; // 数据量
void init() {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += fre[i];
}
for (int i = 0; i < n; i++) {
pro[i] = fre[i]/sum; // 计算出每个数出现的概率
}
}
int getRandom() {
double rp = random.getNextDouble();
double sum = 0;
for (int i = 0; i < n; i++) {
if (sum >= r && sum + pro[i] > rp) { //找到命中的区间
return num[i];
}
sum += pro[i];
}
return num[n-1];
}
似乎一切都很完美,但每次getRandom()的时间复杂度是O(n),大量的使用性能也抗不太住。有没有更好的实现方式?既然写到这里了,必然是有的。
上面代码循环中有个sum += pro[i]; 每次计算都要累加,我们是不是可以提前在init()中累加好?然后你会发现因为每次累加的数都只正数,所以pro是个递增序列,对于有序序列的查找 二分必然是首选。这时候我们可以用二分重写上面代码。
int[] num; // 数字
int[] fre; // 出现的频次
double[] pro; // 出现的概率
int n; // 数据量
void init() {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += fre[i];
}
for (int i = 0; i < n; i++) {
pro[i] = fre[i]/sum; // 计算出每个数出现的概率
if (i != 0) {
pro[i] += pro[i-1];
}
}
}
int getRandom() {
double rp = random.getNextDouble();
int l = 0;
int r = n-1;
while (l != r) { // 二分查找确定区间位置
int mid = (l + r) >> 1;
if (pro[mid] < rp) {
l = mid + 1;
} else {
r = mid;
}
}
return num[n-1];
}
到这里问题就彻底解决了,但是最后给大家留下一个思考题。
上述代码中pro[]的计算有必要吗? 能否直接用fre[]替代其功能?
Recommend
-
86
神户制钢所承认伪造数据
-
82
骗群、换群、伪造身份,微信群里的“野蛮”销售
-
56
作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给...
-
57
前言 在阿里和腾讯工作了6年,当了3年的前端面试官,把期间我和我的同事常问的面试题和答案汇总在我 Github 的 Weekly-FE-Interview 中。希望对大家有所帮助。 如果你在bat面试的时候遇到了什么不懂的问题,欢迎给我提issue,我会把题目
-
42
分布式系统(distributed system)是建立在网络之上的软件系统。正是因为软件的特性,所以分布式系统具有高度的内聚性和透明性。因此,网络和分布式系统之间的区别更多的在于高层软件(特别是操作系统),而不是硬件。 分布式消息队列(MQ) 为什么使用
-
7
面试题精选:神奇的斐波那契数列 2020-11-20 分类:数学 /
-
9
面试题精选:单链表排序也能玩出花来 2020-10-01 分类:算法 /
-
5
面试题精选:字符串替换 2020-09-26 分类:Java / 面...
-
10
面试题精选:两个线程按顺序交替输出1-100 | XINDOO陆陆续续,各个公司的校招季都开始了,我也成为了我司的校招面试官,最近也面了不少同学了,面试过程中也发现了很多问题,即有面试者的、也有面试官的、更有自己的问题,这里先挖个坑,后续写个博客详细聊聊,...
-
4
面试题精选:循环队列 2020-05-12 分类:未分类 /
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK