面试题精选:数据伪造 繁忙的都市(并查集、Kruskal) BFS 力扣 200.岛屿数量 深度操作系统Deepin V20正式版 2020-09-13 【OS】Bankers Algorithm 用于调用的参数太少/写入位置时发生冲突/检测到无效的异常处理程序例程 后渗透之各种维持权限的后门原理即利用 MIPS Branch Target Buffer动态分支预测(BTB) Oracle实战优化:INSERT ALL关键字的应用 Linux中MySQL数据库的使用②-----数据的基本操作 理论+实验——MySQL备份与恢复 MySQL常用数据库函数 MySQL 备份与恢复(完全备份恢复--增量备份恢复+案例演示) MySQL之基础总结部分 Oracle实战优化:递归+分析函数+OLAP函数的应用 Linux中MySQL数据库的使用③-----编码和基本数据类型 理论+实验:MySQL备份与恢复(完整备份、增量备份) “数”聚永川 “智”引未来——永川区大数据智能化产业发展强劲 从一款防疫App感受新加坡大数据智能化气息 “数”聚永川“智”引未来——永川区大数据智能化产业发展强劲 从连接量变到数据质变 物联网将二次爆发 重磅发布!猎芯半导体首创全球最小支持5G物联网的多模多频射频PA芯片 从精准授信到助企惠民,江苏银行物联网金融派上大用场 Python Selenium UI自动化_WebDriver元素_8大定位方式+总结(持续更新完善) Python中的继承、抽象基类和接口 Datawhale学习笔记【阿里云天池 金融风控-贷款违约预测】task1 赛题理解 Pytorch - torchvision计算机视觉工具库 linux 重点笔记 Ubuntu18.04安装ROS Melodic(一路到站型) 小甲鱼笔记:数据结构——线性表(一)线性表的顺序存储结构,线性表顺序存储结构的增,删,插入元素操作 实战比特币脚本编程(1) JAVA WEB DAY 01_Tomcat & Servlet Java基础算法之堆排序(Heap Sort) synchronized批量重偏向与批量撤销 终于等到了!阿里P8历时九个月整理,Java面试宝典,核心知识点笔记在此 “数字心脏”动态解析消费密码,国家级消费市场大数据联合实验室在上海先行先试 全世界运行着大约230亿台物联网设备,安全问题如何解? 物联网产业园&thinkplus解决方案中心国学讲座如期而至 都是程序员,凭什么他能站在鄙视链的顶端? 猛男必看!去小红书做程序员是种什么体验 drozer提示[Errno 2] No such file or directory 【STM32】NB-iOT BC35-G模块 AT指令应用设计指导(附代码) 【北京迅为】i.MX6ULL终结者编译LED汇编程序 Linux系统读写网卡PHY寄存器工具 洛谷:P1226 【模板】快速幂||取余运算(分治,数学) 【2020顶会KDD】AutoST:面向时空预测的高效神经网络学习模型 C/C++实现并查集disjoint_set的模板(带路径压缩优化) 实现一个百万级推送服务,除了它,还有谁 “健康守护者”——STM32标准库和HAL库的比较
您的位置:首页 >运维 >

面试题精选:数据伪造

这道题应该算是我原创的的一道题,来源于我遇到的一个具体需求。大致需求是已知一批数和每个数出现的次数,然后写个接口,每次调用都能返回已知数据中的某个数,且返回的概率和原始数据中每个数出现的概率一致,题目描述起来有些绕口,我们来举个实际的例子。 在这里插入图片描述 以上面的输入为例,要求实现的接口必须以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[]替代其功能?

xindooCSDN认证博客专家Linux分布式Spring一个有趣有料的程序猿,9年技术博主,曾在阿里做过3年运维相关工作,现为某厂Java后端开发工程师,拥有丰富的挖坑踩坑填坑背锅经验[狗头],专注于Java,对操作系统、网络、编译原理也有涉猎,梦想写一门编程语言,一部科幻小说。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。