狗 电面

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. 
   
2. import random
   
3. class MusicPlayer:
   
4.     def __init__(self,musics,K):
   
5.         self.musics = musics
   
6.         self.K = K
   
7.         self.que_size = 0
   
8.         self.head = 0
   
9.         self.tail = -1
   
10. 
    
11.     def getNext(self):
    
12.         idx = random.randint(self.que_size,len(self.musics)-1)
    
13.         music_selected = self.musics[idx]
    
14.         if self.que_size < self.K:
    
15.             self.que_size+=1
    
16.             self.tail+=1
    
17.             self.musics[idx],self.musics[self.tail] = self.musics[self.tail],self.musics[idx]
    
18.         else:
    
19.             self.musics[idx], self.musics[self.head] = self.musics[self.head], self.musics[idx]
    
20.             self.tail = (self.tail+1)%self.K
    
21.             self.musics[self.tail] = self.musics[self.head]
    
22.             self.head = (self.head+1)%self.K
    
23.         return music_selected
    
24. 
    
25. 
    
26. mp = MusicPlayer(['A','B','C','D','E','G','H'],K=4)
    
27. for i in range(20):
    
28.     print(mp.getNext())
    
29.     print(mp.musics)

复制代码

写了一个第二题，不知道有没有问题，求大大们帮把关

第一题高频捌肆毵，第二题第一眼看了前段叙述还以为是玖贰零。。。设两个指针，一个是random的upper bound 一个是和抽到曲目对调的index，upper bound 在前K首往下降后面就都不变，另一个index一直往下降直到比第K大还小的时候再调回最后，也就是说把抽到的音乐往后仍，K次之后会再被换回可能抽到的区域这样就可以了吧

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

kaipeng21 发表于 2019-4-5 05:26
第一题高频捌肆毵，第二题第一眼看了前段叙述还以为是玖贰零。。。设两个指针，一个是random的upper bound  ...

应该对吧。。。
赞！

aizoc 发表于 2019-4-5 07:33
**** 本内容被作者隐藏 ****

我没有遇到呢

kaipeng21 发表于 2019-4-5 05:26
第一题高频捌肆毵，第二题第一眼看了前段叙述还以为是玖贰零。。。设两个指针，一个是random的upper bound  ...

根据你说的应该指的是利用已有空间（队首或者队尾）维护一个循环队列吧。

请问第二题题目是什么啊？积分不够看不了。

[quote]衫衫水水 发表于 2019-4-7 07:21

1. 
   
2. import random
   
3. class MusicPlayer:
   
4. [/quote]
6. 看了你的code, 不太能理解head, tail, que_size都是干啥的，不过应该是对的。附上我的版本，互相讨论哈
   
7. [code]
   
8.     class MusicPlayer():
   
9.         def __init__(self, musics, K):
   
10.             self.musics = musics
    
11.             self.K = K
    
12.             self.lower_bound = 0  # the lower bound for random selection from [lower_bound, -1]
    
13.             self.oldest = 0 # the oldest song played, which can be added to the pool back for the next selection
    
14.             
    
15.         def getNext(self):
    
16.             idx = random.randint(self.lower_bound, len(self.musics) - 1)
    
17.             selected = self.musics[idx]
    
18.             
    
19.             if self.lower_bound < self.K:
    
20.                 self.musics[idx], self.musics[self.lower_bound] = self.musics[self.lower_bound], self.musics[idx]
    
21.                 self.lower_bound += 1
    
22.             else:
    
23.                 self.musics[idx], self.musics[self.oldest] = self.musics[self.oldest], self.musics[idx]
    
24.                 self.oldest = (self.oldest + 1) % self.K
    
25.             
    
26.             return selected  
    
27.         
    
28.     ### driving code ###   
    
29.    
    
30.     mp = MusicPlayer(['A','B','C','D','E','G','H'], K = 4)
    
31.     for i in range(20):
    
32.         print(mp.getNext())
    
33.         print(mp.musics)
    
34.    
    
35.     mp = MusicPlayer(['A','B','C'], K = 2)
    
36.     for i in range(20):
    
37.         print(mp.getNext())
    
38.         print(mp.musics)

复制代码

补充内容 (2019-4-10 22:53):
看了你的code, 不太能理解head, tail, que_size都是干啥的，不过应该是对的。附上我的版本，互相讨论哈

ziwei1992 发表于 2019-4-10 22:52
看了你的code, 不太能理解head, tail, que_size都是干啥的，不过应该是对的。附上我的版本，互相讨论哈
...

哈哈，其实跟你的方法差不多, 我是把数组前面的空间作为一个循环队列, que_size 就是这个意思