我预感到我今天要和面试官就一道简单的算法题进行讨(si)论(bi)了，先上 v 站和你们讨论一下，寻找一下底气。

[jadetang]

今天面试，有一道面试题是这样的：
“首歌曲都是一个评分，现在有2000首歌曲，要求实现一个随机播放器，每首歌曲播放的概率应该正比于它的评分，例如评分9.1的歌曲，和评分7.9的歌曲，播放的次数应该是91：79”
当时给出了一个比较复杂，但是有缺陷的接，之后面试官给出了答案，当时也没有细想，回家路上想出了更好的解法，就写在了我的博客上，顺便让面试官看一下（面试通过不通过无所谓，程序的孰优孰劣必须要分个清楚）。http://www.cnblogs.com/javanerd/p/4504482.html
总的来说我的解法：

拿空间换时间，评分9.1的歌曲，复制91份，评分7.9的歌曲复制79份，放到一个数组中，随机从里面拿。优点就是浅显易懂，实现起来也容易（当时是面试哦，手写代码，人都会紧张的吧）。缺点是空间复杂度不好，如果全是9.9分的歌曲，那么就悲剧了。但是每次随机选取的歌曲的时间还是O(1)，所以随着听得歌曲越多，效率其实越高。


面试官的解法：
将评分和歌曲序号维护成一个区间和歌曲序号的map，然后生成一个随机数，落在哪个区间里面，就是哪首歌。那么问题来了?如果是一个区间做key的map，我只有一个随机数，如何正确的拿到value？是不是应该说的是线段树？如果用线段树，是不是要先排序，才能找到最大的评分的歌曲。

面试官的小弟已经回复我了，估计一会面试官也会看到，我已经做好讨(si)论(bi)的准备了，求V友给点信心。

另外，求一个珠三角地区后端的工作，能用scala就最好不过了，java也行。

[jadetang]

@Septembers 因为内置了实现parser的包，实现简单的DSL很方便。

[akakcolin]

@sciooga 修改下：比v小则按照一定概率判断是否跳过抽下一首？我怎么看到了monte carlo的影子 :)

[SoloCompany]

不就是一个典型的加权平均发布问题么，你的复制(即使是指针)想法出发点就是错的，面试官的区间想法(我没说算法)是对的，具体怎么实现，可以自己把握，最简单易懂的，就是总分乘以0到1的随机因子，然后通过区间累加判断(当然这个累加是可以算法优化的，但通常情况下可以忽略)

[XadillaX]

关于区间的做法很平常的，比如一个随机起名字的包。

https://github.com/XadillaX/chinese-random-name/blob/master/lib/name.js#L40

金木、金金、金土等等不同的组合方式有不同的概率（当然这个概率是瞎掰的），就是用区间来判定的。

[sciooga]

@akakcolin 哈，难道我的数学水平不知不觉又上升了一个水平吗？

[jadetang]

@SoloCompany 错误肯定是谈不上，只不过这个解逼格没有那么高而已了。只不过面试官期望的不是这个解法而已了。

[jadetang]

@binux
我看了http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/
里面说的pre-caculate，本质上是排序以后，通过2分查找来确定随机数落在哪个区间的。
不过面试官给的答案，没有很详细，我自己一开始也没有想到可以用2分查找来定位。

[binux]

@jadetang 做区间不需要排序，而且我觉得这个方法是应该被想到的。。

[jadetang]

@binux 求伪代码，另外，2000首歌，评分0.1-9.9，会有评分重复的。

[SoloCompany]

@jadetang 你把浮点问题整数化这还不叫错误? 如果是的话，为何还要在计算机系统上设计浮点数表示？再者，用空间换效率是很常见的，典型的完全平面化bitset数据结构就是其中之一，但在你这个需要解决的问题上下文中显然不是那么合适，hash和list都能实现o0查找效率，你的线性设计显然是有过度优化的嫌疑

[SoloCompany]

累加算法 on
加一个中间累加结果的排序表，ologn
hash算法好像不存在，没戏想
平面化，也是o1

[binux]

@jadetang http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/ 上面就有啊。。

[hambut]

可参照游戏中常见的宝箱系统

假设设基础权重都为 10，附加权重为评分 ， 物品总权重 = 10 + star * 10
权重和 = 所有物品总权重相加

random(1, 权重和) <= 当前物品总权重 + 当前权重累计 break，以上没考虑排序

[jadetang]

@hambut 这种算法，对于有重复权重的情况也成立吗

[hambut]

@jadetang 成立，不过最好还是打乱一下顺序，最好

[imn1]

sorry，算法比较弱，没看懂原地(in-place)算法

但我想你是否把问题想复杂了？这个其实很简单
生成一个随机数 [0.1, 10.0]，如果是5.5，就只能在 [5.5, 10.0] 内再随机选歌；
如果是3.1，就 [3.1, 10.0] 内选，低于3.1的歌就不会成为候选
这样高分的歌曲被选中机会，概率必然与分数成正比，这问题不就是问概率么？
“随机”就应视为机会均等，不影响概率，所以，按正比（概率）生成候选区间就是答案

其实就是简单“置信区间”的概念
https://zh.wikipedia.org/zh/%E7%BD%AE%E4%BF%A1%E5%8C%BA%E9%97%B4
以评分作为置信度，分数越高，置信区间范围越小，可选的歌越少，选中概率越大

个人觉得面试不会问太难的算法问题，除非岗位就是专门做优化的
那些对一般岗位考很深奥算法的公司都不知道是怎么想的，期望全公司都是华罗庚？

[whahuzhihao]

第一眼看到题目，就想到了“轮盘赌”算法。
原理跟面试官给的差不多，但是解决方式更简洁。也就是@binux提到的那篇文章里的in-place(unsorted)。

[Mutoo]

同上，正是遗传算法里的「轮盘赌」按概率择优录取的简单应用。

[whatisnew]

我也曾经和楼主一样，我被 pass 了，哈哈哈 https://www.v2ex.com/t/191444

[gavin2zhang]

我就是那面试官的「小弟」:P
LZ对面试官的解答有一处不太明白，我已经在你的博客下留言了。这其实就是一道很平常的算法题，我昨天给你发了个JavaScript的实现，如果你认真看应该能想明白。
楼上有些同学不太理解这道算法题的实际意义，其实我没参与出题的过程，倒是在上家公司遇到了同样的场景，要根据用户对节目的喜好程度随机挑选节目，喜好程度越高，选到的概率越大。所以这道题目对数据工程师来说应该是恰当的。
两种算法都是work的，但正如我之前留言的，如果评分不是精确到小数点后一位，而是五位六位，你的方法会遇到麻烦，或者说不够优雅。你的算法是暴力的，而面试官的反而是一种「合理」的思考方向。
再说一句题外话，LZ其实不必太介怀，面试的结果有时可能在对错之外，别人是不是认识到你的潜力反而更关键。天大地大更要心眼大，希望LZ能收获满意的offer啦。:)