Design a Music Player Shuffle Algorithm

Problem

You are building a music streaming application and need to implement an intelligent shuffle algorithm for playlists. The standard random shuffle often results in multiple songs from the same artist playing back-to-back, which creates a poor listening experience.

Your task is to design and implement a shuffle algorithm that distributes songs throughout the playlist to minimize consecutive plays by the same artist. When a user has a Taylor Swift album in their playlist, they shouldn't hear three Taylor Swift songs in a row even though the playlist is "shuffled."

The algorithm should balance two competing goals: maintaining the randomness users expect from shuffle while avoiding artist clustering. When perfect distribution isn't possible (for example, when one artist dominates the playlist), the algorithm should make a best-effort attempt.

Requirements

1. Implement a PlaylistShuffler class with a shuffle_playlist method
2. The method accepts a list of song objects, where each song has id, title, and artist properties
3. Return a shuffled playlist where consecutive songs from the same artist are minimized
4. When perfect distribution is impossible, make the best effort to spread out songs
5. Handle edge cases: empty playlists, single-artist playlists, and playlists dominated by one artist
6. Maintain reasonable randomness - the output shouldn't be deterministic or predictable
7. The algorithm should be efficient enough for playlists with hundreds of songs

Constraints

• 0 ≤ playlist length ≤ 1000
• Each song object contains valid id, title, and artist strings
• Multiple songs may share the same artist
• Artist names are case-sensitive
• Time complexity should be O(n log n) or better where n is the number of songs
• Space complexity should be O(n)

Examples

Example 1:

` Input: [ {"id": "1", "title": "Bohemian Rhapsody", "artist": "Queen"}, {"id": "2", "title": "We Will Rock You", "artist": "Queen"}, {"id": "3", "title": "Imagine", "artist": "John Lennon"}, {"id": "4", "title": "Hey Jude", "artist": "The Beatles"}, {"id": "5", "title": "Let It Be", "artist": "The Beatles"} ]

Output: [ {"id": "1", "title": "Bohemian Rhapsody", "artist": "Queen"}, {"id": "3", "title": "Imagine", "artist": "John Lennon"}, {"id": "4", "title": "Hey Jude", "artist": "The Beatles"}, {"id": "2", "title": "We Will Rock You", "artist": "Queen"}, {"id": "5", "title": "Let It Be", "artist": "The Beatles"} ]

Explanation: The two Queen songs and two Beatles songs are separated by other artists, creating a better listening experience than having them play consecutively. `

Example 2:

` Input: [ {"id": "1", "title": "Song A", "artist": "Artist1"}, {"id": "2", "title": "Song B", "artist": "Artist1"}, {"id": "3", "title": "Song C", "artist": "Artist1"}, {"id": "4", "title": "Song D", "artist": "Artist1"}, {"id": "5", "title": "Song E", "artist": "Artist2"} ]

Output: [ {"id": "1", "title": "Song A", "artist": "Artist1"}, {"id": "5", "title": "Song E", "artist": "Artist2"}, {"id": "2", "title": "Song B", "artist": "Artist1"}, {"id": "3", "title": "Song C", "artist": "Artist1"}, {"id": "4", "title": "Song D", "artist": "Artist1"} ]

Explanation: With Artist1 dominating the playlist, perfect separation is impossible. The algorithm places Artist2 to create at least one break, minimizing consecutive plays where possible. `

Hint 1: Group and Prioritize Start by grouping songs by artist. Artists with more songs should be prioritized for placement to ensure they get distributed first. Think about using a data structure that helps you always pick from the artist with the most remaining songs.

Hint 2: Greedy Selection Use a greedy approach: at each step, select a song from the artist that has the most songs remaining, but avoid the artist that was just played. This is similar to task scheduling problems where you want to maximize spacing between similar items.

Hint 3: Max Heap Strategy A max heap (priority queue) is perfect for this problem. Keep artists in the heap ordered by how many songs they have left. Pop the top artist, add one of their songs to the result, then temporarily set them aside. After placing another artist's song, return the previous artist to the heap with their updated count.

Full Solution `` Approach Explanation:

The solution uses a max heap priority queue strategy to ensure optimal distribution:

1. Grouping Phase: First, group all songs by their artist. This allows us to track how many songs each artist has remaining.
2. Randomization: Shuffle songs within each artist's group to ensure variety when multiple songs from the same artist do play.
3. Heap-based Selection: Use a max heap where artists are prioritized by their remaining song count. This ensures we place songs from artists with more tracks first, which is crucial for good distribution.
4. Avoiding Consecutiveness: When we select a song from an artist, we temporarily remove that artist from the heap. On the next iteration, we select from a different artist, then add the previous artist back. This creates a one-song buffer that prevents consecutive plays.
5. Edge Case Handling: When only one artist remains or when distribution is impossible, the algorithm gracefully handles it by placing remaining songs in the best order possible.

Time Complexity: O(n log k) where n is the total number of songs and k is the number of unique artists. Each heap operation is O(log k) and we perform n iterations.

Space Complexity: O(n) to store the grouped songs and result list.

The algorithm balances randomness with distribution quality, ensuring users get a pleasant shuffled listening experience without noticeable artist clustering.

from typing import List, Dict
import heapq
import random
from collections import defaultdict

class PlaylistShuffler:
    def shuffle_playlist(self, songs: List[Dict[str, str]]) -> List[Dict[str, str]]:
        """
        Shuffle a playlist while distributing songs from the same artist.
        
        Strategy:
        1. Group songs by artist
        2. Use a max heap to always select from the artist with most songs
        3. Track the last artist played to avoid consecutive plays
        4. Shuffle songs within each artist group for variety
        
        Time Complexity: O(n log k) where n is songs, k is unique artists
        Space Complexity: O(n) for storing grouped songs
        """
        if not songs:
            return []
        
        # Group songs by artist
        artist_to_songs = defaultdict(list)
        for song in songs:
            artist_to_songs[song['artist']].append(song)
        
        # Shuffle songs within each artist group for variety
        for artist_songs in artist_to_songs.values():
            random.shuffle(artist_songs)
        
        # Create max heap based on song count (use negative for max heap)
        # Format: (-count, artist_name)
        heap = [(-len(song_list), artist) for artist, song_list in artist_to_songs.items()]
        heapq.heapify(heap)
        
        result = []
        prev_artist = None
        temp_hold = None  # Temporarily hold an artist to avoid consecutive plays
        
        while heap or temp_hold:
            # If we only have the previous artist left, we must use it
            if not heap and temp_hold:
                heap = [temp_hold]
                temp_hold = None
            
            # Get artist with most songs (that isn't the previous artist)
            if heap:
                neg_count, artist = heapq.heappop(heap)
                count = -neg_count
                
                # Add song from this artist
                song = artist_to_songs[artist].pop()
                result.append(song)
                
                # If this artist has more songs, prepare to add back to heap
                if count > 1:
                    current_hold = (-(count - 1), artist)
                else:
                    current_hold = None
                
                # Add previously held artist back to heap
                if temp_hold:
                    heapq.heappush(heap, temp_hold)
                
                temp_hold = current_hold
                prev_artist = artist
        
        return result


# Alternative simpler implementation for comparison
class PlaylistShufflerSimple:
    def shuffle_playlist(self, songs: List[Dict[str, str]]) -> List[Dict[str, str]]:
        """
        Simpler version: sort by artist frequency, then interleave.
        Less optimal but easier to understand.
        """
        if not songs:
            return []
        
        # Group and shuffle
        artist_groups = defaultdict(list)
        for song in songs:
            artist_groups[song['artist']].append(song)
        
        for group in artist_groups.values():
            random.shuffle(group)
        
        # Sort artists by song count (descending)
        sorted_artists = sorted(artist_groups.keys(), 
                               key=lambda a: len(artist_groups[a]), 
                               reverse=True)
        
        # Round-robin through artists
        result = []
        while any(artist_groups.values()):
            for artist in sorted_artists:
                if artist_groups[artist]:
                    result.append(artist_groups[artist].pop(0))
        
        return result