Design and implement a music player that receives song lists from new users and returns songs to play in frequency order without repeating a song in the same cycle. The system supports two APIs: - `addUserSongs(userId, songs)`: a new user arrives with a list of song IDs. Each appearance of a song increases that song's global frequency by 1. - `getNextSong()`: returns the next song ID to play. Playback rules: 1. Among songs that have not yet been played in the current cycle, choose the song with the highest global frequency. 2. A song cannot be replayed within the same cycle. 3. Once every known song has been played once in the current cycle, the next selection starts a new cycle and all known songs are eligible again. 4. New songs can arrive at any time and should be eligible in the active cycle unless that song has already been played in that cycle. ### Constraints & Assumptions - Song IDs may be strings or integers. - The same song may appear multiple times in one user's list, and each appearance counts. - If multiple songs tie on frequency, any deterministic or arbitrary tie-break is acceptable if you state it. - Assume up to `100000` total song additions and `100000` `getNextSong()` calls. - Returning `None` or raising an empty-state exception is acceptable when no songs are known; state your choice. ### Clarifying Questions to Ask - Should ties be deterministic, such as lexicographic order, or is arbitrary order acceptable? - Do song frequencies ever decay or get deleted, or only increase? - Should a user's songs be deduplicated per user or counted by every appearance? - Is the system single-threaded for the interview implementation, or do we need concurrency controls? ### What a Strong Answer Covers - A global frequency map for songs. - A way to track which songs have already been played in the current cycle. - A max-heap or priority queue with lazy deletion for changing frequencies. - Correct handling of cycle resets and songs added mid-cycle. - Time and space complexity. ### Follow-up Questions - How would you make the implementation thread-safe? - How would you support deleting a song or decreasing its frequency? - How would you shard this if the catalog were too large for one machine? - What changes if tie-breaking must be stable across restarts?