Coding - Music Player

Problem Overview

Design a data structure that tracks music listening history with timestamps. The system needs to support adding songs with timestamps, retrieving all songs in chronological order, and removing individual or all records of a song.

This problem tests your ability to work with ordered data structures and maintain multiple access patterns efficiently.

Example

` playlist = MusicPlaylist() playlist.add("song1", 1) # Listen to song1 at time 1 playlist.add("song2", 2) # Listen to song2 at time 2 playlist.add("song1", 3) # Listen to song1 again at time 3

playlist.getAll() # Returns ["song1", "song2", "song1"]

playlist.remove("song2", 2) # Remove song2 at time 2, returns True playlist.getAll() # Returns ["song1", "song1"]

playlist.removeAll("song1") # Remove all song1 records, returns 2 playlist.getAll() # Returns [] `

Requirements

• add(song, timestamp): Add a listening record with O(log n) or O(n) complexity

• getAll(): Return songs sorted by timestamp, with same timestamps in insertion order

• remove(song, timestamp): Remove a specific record, return True if found, False otherwise

• removeAll(song): Remove all records of a song, return count of records removed

• Handle duplicate songs at different timestamps

• Preserve insertion order for songs with identical timestamps

Clarification Questions to Ask

• Can timestamps be negative or zero?

• What is the expected frequency of each operation?

• Is there a limit to the number of songs or timestamps?

• Should we optimize for reads (getAll) or writes (add/remove)?