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

[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

然后二分查找