我预感到我今天要和面试官就一道简单的算法题进行讨(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
目前看来，你这个答案最靠谱的，果然V站牛人多，谢谢了。

[zhsso]

我的理解
[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似乎很简单