Design playlist with add/remove/shuffle

Music Playlist Data Structure

Design an in-memory Playlist data structure that supports the following operations on a set of songs:

• add(songId) : Add a song to the playlist if it is not already present.
• remove(songId) : Remove a song from the playlist if it exists.
• shuffle() : Return a uniformly random song currently in the playlist (i.e., every song has equal probability).

Requirements

• Aim for average O(1) time per operation.
• Use O(n) space where n is the number of songs currently in the playlist.
• Assume songId is an integer.

Edge cases to handle

• Removing a song that is not present.
• Calling shuffle() when the playlist is empty (define behavior: e.g., return null / raise an exception).

(In a real interview setting, you may be asked to implement a class and run provided unit tests on the spot.)