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

[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]

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