我预感到我今天要和面试官就一道简单的算法题进行讨(si)论(bi)了，先上 v 站和你们讨论一下，寻找一下底气。
jadetang · 2015-05-15 08:14:37 +08:00 · 9448 次点击这是一个创建于 3481 天前的主题，其中的信息可能已经有所发展或是发生改变。
今天面试，有一道面试题是这样的：
“首歌曲都是一个评分，现在有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也行。
“首歌曲都是一个评分，现在有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也行。
第 1 条附言 · 2015-05-15 09:46:19 +08:00
谢谢V友热情的打脸，对这个题目我更加理解了。
根据http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/
1 我的算法，叫做expanded，
优点：快速，简单
缺点：占有内存大。
2.面试官的算法，是in-place，占用空间都小。
其中in-place的算法又分为排序和不排序的，
如果不排序，每次选择都很慢，优点是更新快。
如果排序，每次选择速度优于不排序的in-place算法，缺点是需要预先排序，更新也很慢
根据http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/
1 我的算法，叫做expanded，
优点：快速，简单
缺点：占有内存大。
2.面试官的算法，是in-place，占用空间都小。
其中in-place的算法又分为排序和不排序的，
如果不排序，每次选择都很慢，优点是更新快。
如果排序，每次选择速度优于不排序的in-place算法，缺点是需要预先排序，更新也很慢
 |
1
laoyuan 2015-05-15 08:23:16 +08:00
虾米么，虾米收藏的音乐别人最多只能看到2000。
你的解法和面试官的不是一个意思么。。。 |
 |
2
zmj1316 2015-05-15 08:25:49 +08:00
觉得面试官的解法更加优雅一点
|
 |
3
sNullp 2015-05-15 08:31:04 +08:00 via iPhone
如果评分不是7.9而是7.96你怎么办。
|
 |
4
jadetang OP |
 |
5
crisrock 2015-05-15 08:32:32 +08:00
1首歌评1分，其余评分为0，岂不是一直播1首歌？这还是随机吗？
|
|
6
jadetang OP @sNullp
我只能说，基于题目给出的条件，这样的算法是最合适的，每个算法都是优缺点吧。如果是评分是后两位小数，那我的算法空间复杂度还是o(n),不过已经高一个数量级了。 |
 |
8
osto 2015-05-15 08:35:51 +08:00
lz你这样思路是非常清晰的. 面试官给出的solution其实是你的改进版
本质都是索引集合A映射到歌曲集合B. 你采用了粗暴的拷贝歌曲实例到集合A. 其实可以A可以只需要存歌曲号什么的, 这可以大大算减空间,映射函数也简单. 面试官的算法把A弄成自然数集合, 但是映射函数会稍微复杂. 但时空效率确实是最高的, 考虑到才2000首歌, 定义域A的范围不会超过2000*100, A用int表示也绰绰有余了. |
|
10
jadetang OP @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)) } |
 |
11
yingluck 2015-05-15 08:43:41 +08:00
‘’‘评分9.1的歌曲，复制91份‘’‘
这里是歌名或者歌曲编号复制91份吧 |
|
12
jadetang OP @raptium
二分查找的话，是离散的查找吧。比如歌曲的评分是 [1,2,3,]如果是你生成的随机数，只有1，2，3这个三个取值，那么自然hashMap什么的是最高效的。问题是，需要把离散的评分，变成连续的区间段，这个时候能用2分查找？也许线段树能做到？等高人解答。 |
 |
14
raptium 2015-05-15 08:55:01 +08:00 via iPhone
不知道我理解错了没
Guava 里 有个 RangeMap 类，就是二分查找实现的 |
|
15
laoyuan 2015-05-15 09:01:40 +08:00
歌曲的评分是 [1,2,3,]，生成的是[1,2,3,4,5,6]，同时记录[1] => 1、[2, 3] => 2、[4,5,6] => 3
所以我说和LZ的解法是一个意思 |
 |
16
sciooga 2015-05-15 09:01:52 +08:00 via Android
看看这样如何？
评分假设只有1位小数，v = random 一位小数，抽一首歌，评分比v大则播放，比v小则跳过抽下一首？ |
|
17
laoyuan 2015-05-15 09:04:03 +08:00
自然数区间构成的序列，相当于一个连续数组，也是分多的多，分少的少，无非就是不用那么多元素了，光记个开头的数就行了其实
|
|
18
osto 2015-05-15 09:10:31 +08:00
@jadetang
用 if else 硬编码写在代码里可以接近O(1)时间, 哈哈 猜测实际项目是在数据库的歌曲表存了范围, 然后用查询语句取出歌曲.这时候时间肯定不止O(1) 这种情况的话lz的时间是要更优一点的. 假设存数组的歌曲引用只有8个字节(64bit机器), 那么需要的最大内存是 2000*8*100 <= 1.6 M. 在题目给出的设定是完全可以接受的. 开下脑洞, 在正常实际情况,这是一个用户的情况, 要支持大量用户的话可能内存就会不够了. 而感觉实际支持大规模用户的使用情况中, 时间也许没那么宝贵, 反而内存空间会. |
 |
19
Septembers 2015-05-15 09:10:49 +08:00  4
|
 |
20
Andiry 2015-05-15 09:19:56 +08:00
|
|
21
jadetang OP @Septembers
目前看来，你这个答案最靠谱的，果然V站牛人多，谢谢了。 |
 |
22
zhsso 2015-05-15 09:21:35 +08:00
我的理解
[1,2,3,4,5,6] ---> [1,3,6,10,15,21] 1-21随机取一个ra 取min(a[n] >= ra) |
 |
23
stiekel 2015-05-15 09:22:00 +08:00
这是一个典型的权重算法。比较经典和方便的方法是：
1、遍历，求出所有项的总权重 2、遍历，给每一项的权重，加一个0到总权重之间的随机数，注意，每项加的都是随机数，大小是不一样的。得出新权重 3、从所有项中，找出新权重最大的那一项。 难道我也要写一篇吗？ |
|
24
stiekel 2015-05-15 09:22:57 +08:00
这个算法，只需要遍历两次。
|
|
26
Andiry 2015-05-15 09:24:24 +08:00
算错了，a[2] = 170
|
 |
27
lijia18 2015-05-15 09:38:57 +08:00
这种问题还值得搞个算法啊
至少要把加like的时间当参数传进来才是好一点的算法啊 很多人在某个时间段喜欢听某种音乐啊 越新发布的音乐在收藏里随机到的几率越高啊 把这些元素都考虑进去再做算法吧 其他啥好友相似口味这种忽悠的我就不说了 |
 |
29
wshcdr 2015-05-15 09:43:39 +08:00
你的解法没有什么扩展性
|
 |
30
hualuogeng 2015-05-15 10:00:19 +08:00
楼主使用的是整数域， 然后用数组做了一个全map，其它的和面试官的没有什么本质区别。用空间换时间，查询的效率应该最高的。
但是在评分改变时会有一些额外的开销，比如评分减少了，那么需要重新构建数组。而且在sNullp所说的评分值进一步细化情况下，其空间开销是数量级增长的。 而面试官的方法使用的是实数域，带来的优势是在评分细化时，其时空开销是不变的，对评分改变的额外开销也比较少。当然，只要不使用全map方式，从随机值到区间的查找肯定不是O(1)，楼主的查询效率肯定要更好。 就本题的限定条件而言，我觉得楼主的算法更优。 但是如果是实际的开发需求，我会更倾向于面试官的做法，因为1. 有更好的扩展性； 2. 修改的影响小；3. 在2000首这样的数量级上，即使遍历，查询效率也应该够用。 |
 |
31
kifile 2015-05-15 10:06:07 +08:00
感觉两个解法一样的啊，只不过你是属于在一个池子里复制多个相同对象，而面试官则是把你那些对象的数字给他抽离了，使用开区间来处理，其实思想都是同一个，只不过他的更省空间一点。
|
|
32
jadetang OP |
 |
33
binux 2015-05-15 10:14:03 +08:00
面试官的解法明显是 Pre-calculated
我经常喜欢问的一个类似的题目是，怎样从不定多带权数列中，随机选取 n 个，只遍历一次。 |
 |
34
zjuster 2015-05-15 10:23:27 +08:00
@jadetang 这样把1和0粗暴对待太书面化了。实际上的算法应考虑边界值。比如新加入的歌曲，还没来得及评分，那么就是0。其他都有{1,0.1,0.9,0.7...}的评分，那么0就相当于被无视了。
|
|
35
jadetang OP @zjuster 面试题毕竟是面试题，不是实际开发啊，如果实际开发的话，很多条件要考虑的，比如，能不能更新评分，能不能新加歌曲，评分精确到小数点以后几位，播放的概率之比允许的偏差等等。
|
|
36
hualuogeng 2015-05-15 10:32:07 +08:00
@jadetang 对于连续存储的数组来说，增删的代价都不小。就算是scala的变长数组，在非尾端删除都会带来其后数组元素的移动。
|
 |
37
xua131988 2015-05-15 10:43:06 +08:00
scala大爱。。
|
|
38
Septembers 2015-05-15 10:45:03 +08:00
|
|
39
jadetang OP @xua131988 安利一下我写的一个scala sql的实现，可以在内存中对于Map执行sql语句 https://github.com/jadetang/scala_sql
|
|
40
Septembers 2015-05-15 11:05:12 +08:00
@jadetang scala看起来做DSL似乎很简单
|
|
41
jadetang OP @Septembers 因为内置了实现parser的包，实现简单的DSL很方便。
|
 |
43
SoloCompany 2015-05-15 13:04:02 +08:00 via Android
不就是一个典型的加权平均发布问题么，你的复制(即使是指针)想法出发点就是错的，面试官的区间想法(我没说算法)是对的，具体怎么实现，可以自己把握，最简单易懂的，就是总分乘以0到1的随机因子，然后通过区间累加判断(当然这个累加是可以算法优化的，但通常情况下可以忽略)
|
 |
44
XadillaX 2015-05-15 13:09:51 +08:00
关于区间的做法很平常的，比如一个随机起名字的包。
https://github.com/XadillaX/chinese-random-name/blob/master/lib/name.js#L40 金木、金金、金土等等不同的组合方式有不同的概率（当然这个概率是瞎掰的），就是用区间来判定的。 |
|
46
jadetang OP @SoloCompany 错误肯定是谈不上，只不过这个解逼格没有那么高而已了。只不过面试官期望的不是这个解法而已了。
|
|
47
jadetang OP @binux
我看了http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/ 里面说的pre-caculate，本质上是排序以后，通过2分查找来确定随机数落在哪个区间的。 不过面试官给的答案，没有很详细，我自己一开始也没有想到可以用2分查找来定位。 |
|
50
SoloCompany 2015-05-15 13:39:37 +08:00 via Android
@jadetang 你把浮点问题整数化这还不叫错误? 如果是的话，为何还要在计算机系统上设计浮点数表示？再者，用空间换效率是很常见的，典型的完全平面化bitset数据结构就是其中之一，但在你这个需要解决的问题上下文中显然不是那么合适，hash和list都能实现o0查找效率，你的线性设计显然是有过度优化的嫌疑
|
|
51
SoloCompany 2015-05-15 13:43:52 +08:00 via Android
累加算法 on
加一个中间累加结果的排序表，ologn hash算法好像不存在，没戏想 平面化，也是o1 |
|
52
binux 2015-05-15 13:44:54 +08:00
|
 |
53
hambut 2015-05-15 14:01:20 +08:00
可参照游戏中常见的宝箱系统
假设设基础权重都为 10，附加权重为评分 ， 物品总权重 = 10 + star * 10 权重和 = 所有物品总权重相加 random(1, 权重和) <= 当前物品总权重 + 当前权重累计 break，以上没考虑排序 |
 |
56
imn1 2015-05-15 14:42:05 +08:00
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 以评分作为置信度，分数越高，置信区间范围越小，可选的歌越少，选中概率越大 个人觉得面试不会问太难的算法问题，除非岗位就是专门做优化的 那些对一般岗位考很深奥算法的公司都不知道是怎么想的，期望全公司都是华罗庚？ |
 |
57
whahuzhihao 2015-05-15 15:37:25 +08:00
第一眼看到题目，就想到了“轮盘赌”算法。
原理跟面试官给的差不多，但是解决方式更简洁。也就是@binux提到的那篇文章里的in-place(unsorted)。 |
 |
58
Mutoo 2015-05-16 00:07:37 +08:00
同上，正是遗传算法里的「轮盘赌」按概率择优录取的简单应用。
|
 |
59
whatisnew 2015-05-16 00:23:29 +08:00
我也曾经和楼主一样，我被 pass 了，哈哈哈 https://www.v2ex.com/t/191444
|
 |
60
gavin2zhang 2015-05-16 01:39:47 +08:00 via iPhone 1
我就是那面试官的「小弟」:P
LZ对面试官的解答有一处不太明白，我已经在你的博客下留言了。这其实就是一道很平常的算法题，我昨天给你发了个JavaScript的实现，如果你认真看应该能想明白。 楼上有些同学不太理解这道算法题的实际意义，其实我没参与出题的过程，倒是在上家公司遇到了同样的场景，要根据用户对节目的喜好程度随机挑选节目，喜好程度越高，选到的概率越大。所以这道题目对数据工程师来说应该是恰当的。 两种算法都是work的，但正如我之前留言的，如果评分不是精确到小数点后一位，而是五位六位，你的方法会遇到麻烦，或者说不够优雅。你的算法是暴力的，而面试官的反而是一种「合理」的思考方向。 再说一句题外话，LZ其实不必太介怀，面试的结果有时可能在对错之外，别人是不是认识到你的潜力反而更关键。天大地大更要心眼大，希望LZ能收获满意的offer啦。:) |
 |
61
remenberl 2015-05-16 03:44:28 +08:00
|
|
62
jadetang OP @gavin2zhang 我只是对于面试官的解答没有很清楚，所以发个帖子太讨论一下吧。心眼问题谈不上吧。各种算法的优劣，http://www.electricmonk.nl/log/2009/12/23/weighted-random-distribution/ 这里面说的很清楚了，根据不同的场景选择最合适的，才是最好的。我昨天吃饭的时候还和朋友讨论，说这样的面试题才好的，能把简单的算法题目变化成一个实际应用的场景，比起直接出LEETCODE上的那种题目，要高明一些。所以，我没用黑你们公司的意思啊，心眼问题实在谈不上。
|
 |
63
starqoq 2015-05-17 19:25:33 +08:00
你好，不需要排序的。直接算出得分数组的前缀和，然后随机一个数字，二分查找前缀和数组就可以了。
复杂度预处理 O(N) 取一个数是 O(ln(n)) |
|
64
starqoq 2015-05-17 19:27:08 +08:00
对了要特殊处理一下评分为0的歌曲。
|
 |
65
bugcoder 2015-05-18 01:54:16 +08:00
取所有的评分，均一化，作为狄利克雷分布的参数，然后每次选歌就是一次狄利克雷分布的采样。
|
 |
66
mengzhuo 2015-05-18 12:33:55 +08:00
轮盘赌啊
才2000，Log(n)没有问题 |
 |
67
iannil 2015-05-18 14:48:34 +08:00
我是来赞楼主头像的，太萌了！
|
Select Language