Google Phone Screen

先上题求大米：
Design a playlist that intiallly has a list of songs and a cool down value k. The playlist should randomly return a song to play.
Implement the

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

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

16 +8:00):
补充1：原来楼主想复杂了，不需要linked list也不需要ordered hashmap，只需要交换这次选中的歌曲和即将被解放的歌曲就行。

补充2：今早面的

可不可以用 一个arr存 等待播放的歌曲 song= [1,3,4,5,6,7,8]
然后另一个 queue 存已经播放的  queue = [0,2,9,10]
当 len(queue) < k 时，随机从song里选出元素，打印，然后放到 queue队尾
如果 len(queue) ==k 时， 把队收的元素popleft出来放回 song。 这样就能保证每次选出的歌曲都是随机，并且满足冷却时间要求

我的想法是two pointer, 原本的array首尾相连，每次播放都在left到right之间随机选一个，然后把它和left交换，left++，当外面的数量大于k的时候right++，然后循环就行了。

1. def __init__( songs, k):
   
2.         self.songs = songs
   
3.         self.left = self.right = 0
   
4.         self.cap = len(songs) - k
   
5. 
   
6. def GetSong():
   
7.         index = ( self.left + ramdom.randInt( ( self.right - self.left + len( songs)) % len( songs))) % len( songs)
   
8.         songs[self.left], songs[index] = songs[index], songs[self.left]
   
9.         self.left = ( self.left + 1) % len( songs)
   
10.         if ( self.right - self.left + len( songs)) % len( songs) < self.cap:
    
11.                 self.right = ( self.right + 1) % len( songs)

复制代码

更新：刚刚反应过来，应该把right更新放在left更新前面，否则在cap = 1的时候会出错

playlist那个题我的思路是
playlist: [1,2,3,4,5,6] + [0,1, k-1]
            可用区          最近播放区
每次搜索时只在“可用区”搜索
1. 后面类似循环链表，维护一个指针指向k个中最早进入的歌曲，下次play的时候，k个中最早进入的歌曲被交换出“最近播放区”，refill到“可用区”。
2. 注意一开始“最近播放区”是空的，所以需要区别处理

1. 
   
2. def PlayList(songs: list[int], k: int):
   
3.     self.songs = songs
   
4.     self.k = k
   
5.     # 最近k首播放过的不播，播一首增加1，直到k
   
6.     self.exlude_songs_count = 0
   
7.     # 一开始play的歌曲交换到最后一个
   
8.     self.refill_pointer = len(songs) - 1
   
9. 
   
10. def GetSong():
    
11.      n = len(self.songs)
    
12.      k = self.k
    
13.      # 在可选区随机选择一首歌
    
14.      index = random.randint(0, n - 1 - self.played_count)
    
15.      ret = self.songs[index]
    
16.      # 与refill_pointer交换
    
17.      self.songs[index], self.songs[self.refill_pointer] = self.songs[self.refill_pointer], self.songs[index]
    
18.      # 最多排除k首歌
    
19.      if self.exlude_songs_count < k:
    
20.          self.exlude_songs_count += 1
    
21.      self.refill_pointer -= 1
    
22.      # 如果refill_pointer 超出最后k个，跳回整个list尾部（n - 1）
    
23.      if self.refill_pointer == n - 1 - k:
    
24.          self.refill_pointer = n - k
    
25.      return ret
    

复制代码

例如：
songs = [1,2,3,4 || ], k = 2, exlude_songs_count = 0, refill_pointer = 3
                      ^ <- refill_pointer
"||" 分隔可用区和最近播放区
那么exlude_songs_count = 0, refill_pointer = 3
1. 播放songs[0:3]任意一首，假设songs[0] = 1
songs = [4,2,3,|| 1], k = 2, exlude_songs_count = 1, refill_pointer = 2
                   ^
2. 播放songs[0:2]任意一首，假设songs[0] = 4
songs = [3,2, || 4,1], k = 2, exlude_songs_count = 2, refill_pointer = 3 {开始等于2 - 1 = 1 == (n - 1 - k)， 所以跳到列表尾}
                          ^
3. 再播放一首后，1被交换出“最近播放区”，refill到可用区，最近播放的那一首放入“最近播放区”

补充内容 (2021-09-15 10:36 +8:00):
     if self.refill_pointer == n - 1 - k:
         self.refill_pointer = n - k # 这里应该是 n - 1

anyonedy 发表于 2021-9-14 12:29
playlist那个题我的思路是
playlist: [1,2,3,4,5,6] + [0,1, k-1]
            可用区          最近播放 ...

我是用的count来track number of calls to GetSong，end = songs.Length - 1 - Min(count, k)。然后从0到end里面随机选取一首歌。和你的思路差不多。不过原来简单的swap就可以了，我硬是想到了double linked list😂。完了，简单问题复杂化了，开始担心面试结果了。

anyonedy 发表于 2021-9-14 12:29
playlist那个题我的思路是
playlist: [1,2,3,4,5,6] + [0,1, k-1]
            可用区          最近播放 ...

最后一行是不是错了，应该跳回到最后一个索引。
         self.refill_pointer = n - 1

shenji 发表于 2021-9-14 12:38
我是用的count来track number of calls to GetSong，end = songs.Length - 1 - Min(count, k)。然后从0到 ...

面试官不是说接受吗？可能想听一听新的思路？
希望楼主好运。

irwinplimpton 发表于 2021-9-14 19:23
最后一行是不是错了，应该跳回到最后一个索引。
         self.refill_p ...

是的。。写错了。。