Amazon VO 面试真题解析：设计播放列表随机播放系统（最近 N 首不重复）

You are asked to design a playlist shuffle system that keeps track of the last N played songs and ensures that a new song is not played again until N other songs have been played.

Implement the following operations:

• Add Song: Add a new song to the playlist.
• Play Song: Play a song from the playlist that has not been played in the last N songs. If all songs have been played recently, the system should still return a valid song according to the intended shuffle behavior.

Implement a class with the following methods:

public class Playlist {public Playlist(int n) {// Constructor implementation}

    public void addSong(String song) {// Method to add a song to the playlist}

    public String playSong() {// Method to play a song from the playlist}
}

这道题要求设计一个支持“最近 N 首不重复”的播放列表随机播放系统。核心思路通常是用一个队列或双端队列维护最近播放过的歌曲，再配合集合快速判断某首歌是否仍在冷却期内；如果歌曲池较大，还可以结合随机选择与惩罚机制，确保播放时优先避开最近 N 首。实现重点在于 addSong 维护可播放歌曲集合，playSong 在满足约束的前提下返回一首歌，并在歌曲数量不足时合理退化。