Amazon VO Interview Question: Design a Playlist Shuffle System with a Recent Songs Constraint

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}
}

This problem asks you to design a playlist shuffle system with a recent-history constraint: a song should not be played again until N other songs have been played. A typical solution uses a queue or deque to track the most recent plays and a set to check whether a song is still in the cooldown window, often combined with a randomized or round-robin selection strategy. The main challenge is keeping addSong and playSong efficient while preserving the no-repeat-within-N behavior.