随机数问题——微软面试题

  1. 云栖社区>
  2. 博客列表>
  3. 正文

随机数问题——微软面试题

奈良佳晴子 2018-08-10 15:21:31 浏览1106 评论1

摘要: 之前同学面试微软,问了一个问题:如果给你一列物品,这列物品各自都有一个权重。如果根据权重随机选取物品。权重值越大,选中的概率就越大。 第一想法肯定就是根据权重的大小扩充这个数组。比如数组里有[‘apple’,’cherry’,’banana’],对应的权重是[3,4,1]。

之前同学面试微软,问了一个问题:如果给你一列物品,这列物品各自都有一个权重。如果根据权重随机选取物品。权重值越大,选中的概率就越大。
QQ_20180808145819

第一想法肯定就是根据权重的大小扩充这个数组。比如数组里有[‘apple’,’cherry’,’banana’],对应的权重是[3,4,1]。那么我们把数组扩充成

[‘apple’,’apple’,’apple’,’cherry’,’cherry’,’banana’]

就像这样,然后每个物品选取的概率就是1/(sum(权重))。
但是这个方法有个问题,第一:占用了太多空间。如果权值很大,则需要一个很大数组。

用云栖社区APP,舒服~

【云栖快讯】诚邀你用自己的技术能力来用心回答每一个问题,通过回答传承技术知识、经验、心得,问答专家期待你加入!  详情请点击

网友评论

1F
赵志腾

在(0,sum(权重)]内根据权重分区间,每个区间代表物品,然后在此范围内取随机数

1721235007744388奈良佳晴子 赞同
奈良佳晴子
文章18篇 | 关注36
关注
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
大数据开发套件(Data IDE),提供可视化开发界面、离线任务调度运维、快速数据集成、多人... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航