我预感到我今天要和面试官就一道简单的算法题进行讨(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也行。

谢谢V友热情的打脸，对这个题目我更加理解了。
根据http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/
1 我的算法，叫做expanded，
优点：快速，简单
缺点：占有内存大。

2.面试官的算法，是in-place，占用空间都小。
其中in-place的算法又分为排序和不排序的，
如果不排序，每次选择都很慢，优点是更新快。

如果排序，每次选择速度优于不排序的in-place算法，缺点是需要预先排序，更新也很慢

[laoyuan]

虾米么，虾米收藏的音乐别人最多只能看到2000。
你的解法和面试官的不是一个意思么。。。

[zmj1316]

觉得面试官的解法更加优雅一点

[sNullp]

如果评分不是7.9而是7.96你怎么办。

[jadetang]

@laoyuan
不是虾米

@zmj1316
关键是我想不明白，如何从区间里面拿到对应的key，例如有三首歌的评分[1,2,3],那么有三个区间[0-1,1-3,3-6],现在给出一个随机数3.6，有什么数据结构能够判断出，3.6是在第三个区间里面？
也许我真的想错了，所以要先到V站上来找答案啊。

[crisrock]

1首歌评1分，其余评分为0，岂不是一直播1首歌？这还是随机吗？

[jadetang]

@sNullp
我只能说，基于题目给出的条件，这样的算法是最合适的，每个算法都是优缺点吧。如果是评分是后两位小数，那我的算法空间复杂度还是o(n),不过已经高一个数量级了。

[jadetang]

@crisrock
看题目的字面要求，如果是评分是1和0的话，那么播放的概率比应该是1：0。

[osto]

lz你这样思路是非常清晰的. 面试官给出的solution其实是你的改进版

本质都是索引集合A映射到歌曲集合B.

你采用了粗暴的拷贝歌曲实例到集合A.
其实可以A可以只需要存歌曲号什么的, 这可以大大算减空间,映射函数也简单.
面试官的算法把A弄成自然数集合, 但是映射函数会稍微复杂. 但时空效率确实是最高的, 考虑到才2000首歌, 定义域A的范围不会超过2000*100, A用int表示也绰绰有余了.

[raptium]

@jadetang 未必要 O(1) 啊，这种规模二分也找的过来
差不了几毫秒

[jadetang]

@osto
你说到点子上了，我的scala解，返回的就是歌曲的下标。而且每次选择都是o(1)的时间。

我主要想不出面试官的的映射函数是怎么样的，这个函数能否达到o(1)的时间。或者根本没有这样的映射？



class RandomSong(val rate: Array[Double]) {
val rateWithIndex = rate.map(x => (x * 10).toInt).zipWithIndex

val songPool = rateWithIndex.flatMap { case (rate, index) => Array(index).padTo(rate, index)}

def pickSong:Int = songPool(Random.nextInt(songPool.size))

}

[yingluck]

‘’‘评分9.1的歌曲，复制91份‘’‘

这里是歌名或者歌曲编号复制91份吧

[jadetang]

@raptium
二分查找的话，是离散的查找吧。比如歌曲的评分是 [1,2,3,]如果是你生成的随机数，只有1，2，3这个三个取值，那么自然hashMap什么的是最高效的。问题是，需要把离散的评分，变成连续的区间段，这个时候能用2分查找？也许线段树能做到？等高人解答。

[jadetang]

@yingluck
我给的出的解是一个数组，下标是歌曲的编号，数组值是歌曲的评分，每次返回下标。

[raptium]

不知道我理解错了没
Guava 里 有个 RangeMap 类，就是二分查找实现的

[laoyuan]

歌曲的评分是 [1,2,3,]，生成的是[1,2,3,4,5,6]，同时记录[1] => 1、[2, 3] => 2、[4,5,6] => 3
所以我说和LZ的解法是一个意思

[sciooga]

看看这样如何？
评分假设只有1位小数，v = random 一位小数，抽一首歌，评分比v大则播放，比v小则跳过抽下一首？

[laoyuan]

自然数区间构成的序列，相当于一个连续数组，也是分多的多，分少的少，无非就是不用那么多元素了，光记个开头的数就行了其实

[osto]

@jadetang
用 if else 硬编码写在代码里可以接近O(1)时间, 哈哈

猜测实际项目是在数据库的歌曲表存了范围, 然后用查询语句取出歌曲.这时候时间肯定不止O(1)
这种情况的话lz的时间是要更优一点的.

假设存数组的歌曲引用只有8个字节(64bit机器), 那么需要的最大内存是 2000*8*100 <= 1.6 M.
在题目给出的设定是完全可以接受的.

开下脑洞, 在正常实际情况,这是一个用户的情况, 要支持大量用户的话可能内存就会不够了. 而感觉实际支持大规模用户的使用情况中, 时间也许没那么宝贵, 反而内存空间会.

[Septembers]

有个东西叫：加权随机分布
see http://www.electricmonk.nl/Writings/HomePage?action=download&upname=weighted_random_dist.pdf
see http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/

[Andiry]

@jadetang 不就是个数组吗，有什么高级的
a[0] = 0
a[1] = 91 // point(0) = 91
a[2] = 160 // point(1) = 79

然后二分查找

[jadetang]

@Septembers
目前看来，你这个答案最靠谱的，果然V站牛人多，谢谢了。

[WDsUO7HnS2Na1DFC]

我的理解
[1,2,3,4,5,6] ---> [1,3,6,10,15,21]
1-21随机取一个ra
取min(a[n] >= ra)

[stiekel]

这是一个典型的权重算法。比较经典和方便的方法是：
1、遍历，求出所有项的总权重
2、遍历，给每一项的权重，加一个0到总权重之间的随机数，注意，每项加的都是随机数，大小是不一样的。得出新权重
3、从所有项中，找出新权重最大的那一项。
难道我也要写一篇吗？

[stiekel]

这个算法，只需要遍历两次。

[jadetang]

@Andiry
啊，我想通了，确实这样能达到Log(n)的速度。

[Andiry]

算错了，a[2] = 170

[lijia18]

这种问题还值得搞个算法啊
至少要把加like的时间当参数传进来才是好一点的算法啊
很多人在某个时间段喜欢听某种音乐啊
越新发布的音乐在收藏里随机到的几率越高啊
把这些元素都考虑进去再做算法吧
其他啥好友相似口味这种忽悠的我就不说了

[ffffwh]

@crisrock
这种常见做法是把0变成0.1之类的

[wshcdr]

你的解法没有什么扩展性

[hualuogeng]

楼主使用的是整数域， 然后用数组做了一个全map，其它的和面试官的没有什么本质区别。用空间换时间，查询的效率应该最高的。
但是在评分改变时会有一些额外的开销，比如评分减少了，那么需要重新构建数组。而且在sNullp所说的评分值进一步细化情况下，其空间开销是数量级增长的。

而面试官的方法使用的是实数域，带来的优势是在评分细化时，其时空开销是不变的，对评分改变的额外开销也比较少。当然，只要不使用全map方式，从随机值到区间的查找肯定不是O(1)，楼主的查询效率肯定要更好。

就本题的限定条件而言，我觉得楼主的算法更优。
但是如果是实际的开发需求，我会更倾向于面试官的做法，因为1. 有更好的扩展性； 2. 修改的影响小；3. 在2000首这样的数量级上，即使遍历，查询效率也应该够用。

[kifile]

感觉两个解法一样的啊，只不过你是属于在一个池子里复制多个相同对象，而面试官则是把你那些对象的数字给他抽离了，使用开区间来处理，其实思想都是同一个，只不过他的更省空间一点。

[jadetang]

@hualuogeng
评分减少了，只需要扫一遍数组，把对应的元素个数给删除出去就行。如果评分增多了，就加元素。

每个算法都有优缺点，只是看特殊的场景下选择最合适的。

受教了。

[binux]

面试官的解法明显是 Pre-calculated

我经常喜欢问的一个类似的题目是，怎样从不定多带权数列中，随机选取 n 个，只遍历一次。

[zjuster]

@jadetang 这样把1和0粗暴对待太书面化了。实际上的算法应考虑边界值。比如新加入的歌曲，还没来得及评分，那么就是0。其他都有{1,0.1,0.9,0.7...}的评分，那么0就相当于被无视了。

[jadetang]

@zjuster 面试题毕竟是面试题，不是实际开发啊，如果实际开发的话，很多条件要考虑的，比如，能不能更新评分，能不能新加歌曲，评分精确到小数点以后几位，播放的概率之比允许的偏差等等。

[hualuogeng]

@jadetang 对于连续存储的数组来说，增删的代价都不小。就算是scala的变长数组，在非尾端删除都会带来其后数组元素的移动。

[xua131988]

scala大爱。。

[Septembers]

@jadetang
对于音乐应用这些处理都可以压到后台预处理
但是考虑到 嵌入式设备 的特殊性，算法的各方面复杂度应该压到最低（电池啊 电池啊 电池啊

[jadetang]

@xua131988 安利一下我写的一个scala sql的实现，可以在内存中对于Map执行sql语句 https://github.com/jadetang/scala_sql

[Septembers]

@jadetang scala看起来做DSL似乎很简单

[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啦。:)

[remenberl]

可以用alias method 应该是最优解 见 https://hips.seas.harvard.edu/blog/2013/03/03/the-alias-method-efficient-sampling-with-many-discrete-outcomes/

[jadetang]

@gavin2zhang 我只是对于面试官的解答没有很清楚，所以发个帖子太讨论一下吧。心眼问题谈不上吧。各种算法的优劣，http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/ 这里面说的很清楚了，根据不同的场景选择最合适的，才是最好的。我昨天吃饭的时候还和朋友讨论，说这样的面试题才好的，能把简单的算法题目变化成一个实际应用的场景，比起直接出LEETCODE上的那种题目，要高明一些。所以，我没用黑你们公司的意思啊，心眼问题实在谈不上。

[starqoq]

你好，不需要排序的。直接算出得分数组的前缀和，然后随机一个数字，二分查找前缀和数组就可以了。
复杂度预处理 O(N)
取一个数是 O(ln(n))

[starqoq]

对了要特殊处理一下评分为0的歌曲。

[bugcoder]

取所有的评分，均一化，作为狄利克雷分布的参数，然后每次选歌就是一次狄利克雷分布的采样。

[mengzhuo]

轮盘赌啊
才2000，Log(n)没有问题

[iannil]

我是来赞楼主头像的，太萌了！