Frontend School

Curated Playlist Selection

DSA
medium

Curated Playlist Selection

Medium
Sorting
Searching
Arrays
Objects

Overview

Spotify is all about discovering new music. To help users find high-quality, popular tracks that align with specific listening habits, we often curate playlists dynamically. This problem focuses on the algorithmic core of selecting tracks for such a playlist, combining filtering, top-K selection, and multi-criteria sorting.

What you need to do / Task

You are tasked with implementing a function getCuratedPlaylist that takes a list of Track objects, a minPlays threshold, a maxPlays threshold, and an integer k. The function should return a list of Track objects that satisfy the following criteria:

  1. Filter by Play Count: Include only tracks whose playCount is greater than or equal to minPlays AND less than or equal to maxPlays.
  2. Select Top K by Popularity: From the filtered tracks, identify the k tracks with the highest playCount. If there are fewer than k tracks after filtering, return all of them. If multiple tracks have the same playCount and are vying for the k-th spot, any of them can be chosen.
  3. Sort by Metadata: Finally, sort these k selected tracks alphabetically by their title. If two tracks have the same title, sort them alphabetically by their artist.

Input & output

The function signature is getCuratedPlaylist(tracks: Track[], minPlays: number, maxPlays: number, k: number): Track[].

  • tracks: An array of Track objects. Each Track object has the following structure:

    interface Track {
        id: string;
        title: string;
        artist: string;
        genre: string;
        playCount: number;
    }
    
    • id: A unique string identifier for the track.
    • title: The title of the track (string).
    • artist: The artist of the track (string).
    • genre: The genre of the track (string).
    • playCount: The total play count for the track (number).
  • minPlays: A non-negative integer representing the minimum inclusive play count for a track to be considered.

  • maxPlays: A non-negative integer representing the maximum inclusive play count for a track to be considered.

  • k: A positive integer representing the maximum number of tracks to include in the curated playlist.

  • Returns: An array of Track objects, sorted as specified.

Clarifications

  • Empty tracks input: If the tracks array is empty, the function should return an empty array.
  • k value: If k is 0, an empty array should be returned. If k is larger than the number of tracks satisfying the filter and popularity criteria, return all available tracks.
  • minPlays / maxPlays: Assume minPlays <= maxPlays.
  • String comparisons: All string comparisons (title, artist) should be case-sensitive.
  • Track uniqueness: id is unique, but title and artist pairs might not be globally unique (though unlikely in practice, assume for sorting purposes).

Examples

1

Example 1

Input:

tracks = [{"id": "1", "title": "Song A", "artist": "Artist X", "genre": "Pop", "playCount": 100}, {"id": "2", "title": "Song B", "artist": "Artist Y", "genre": "Rock", "playCount": 150}, {"id": "3", "title": "Song C", "artist": "Artist X", "genre": "Pop", "playCount": 120}, {"id": "4", "title": "Song D", "artist": "Artist Z", "genre": "Jazz", "playCount": 90}], minPlays = 100, maxPlays = 200, k = 2

Output:

[{"id": "2", "title": "Song B", "artist": "Artist Y", "genre": "Rock", "playCount": 150}, {"id": "3", "title": "Song C", "artist": "Artist X", "genre": "Pop", "playCount": 120}]

Note:

Tracks with play counts between 100 and 200 are Song A (100), Song B (150), Song C (120). The top 2 by play count are Song B (150) and Song C (120). Sorted alphabetically by title, then artist: Song B, Song C.

2

Example 2

Input:

tracks = [{"id": "1", "title": "Track Alpha", "artist": "Artist A", "genre": "Pop", "playCount": 50}, {"id": "2", "title": "Track Beta", "artist": "Artist B", "genre": "Rock", "playCount": 200}], minPlays = 100, maxPlays = 300, k = 3

Output:

[{"id": "2", "title": "Track Beta", "artist": "Artist B", "genre": "Rock", "playCount": 200}]

Note:

Only 'Track Beta' (200 plays) falls within the [100, 300] range. Since k=3 and only one track is available, 'Track Beta' is returned.

3

Example 3

Input:

tracks = [{"id": "1", "title": "Great Hit", "artist": "Band A", "genre": "Pop", "playCount": 1000}, {"id": "2", "title": "Great Hit", "artist": "Band B", "genre": "Rock", "playCount": 1200}, {"id": "3", "title": "Fantastic Song", "artist": "Solo X", "genre": "Jazz", "playCount": 1100}], minPlays = 500, maxPlays = 1500, k = 3

Output:

[{"id": "3", "title": "Fantastic Song", "artist": "Solo X", "genre": "Jazz", "playCount": 1100}, {"id": "1", "title": "Great Hit", "artist": "Band A", "genre": "Pop", "playCount": 1000}, {"id": "2", "title": "Great Hit", "artist": "Band B", "genre": "Rock", "playCount": 1200}]

Note:

All three tracks are within the play count range. The top 3 by play count are all of them. When sorting, 'Fantastic Song' comes before 'Great Hit'. For 'Great Hit', 'Band A' comes before 'Band B'.

Constraints

Constraints & assumptions

  • 0 <= tracks.length <= 10^5 (N)
  • 0 <= minPlays <= maxPlays <= 10^9
  • 0 <= k <= 10^5
  • 0 <= track.playCount <= 10^9
  • track.id, track.title, track.artist, track.genre are non-empty strings.
  • The total length of all strings combined will not exceed typical memory limits.
  • Time budget: ~40 minutes.
  • Memory budget: ~256MB.

Out of scope

  • Network requests or database interactions.
  • Error handling for invalid input types (assume valid inputs as per constraints).
  • Persisting results or user interaction.

What interviewers evaluate

  • Correctness: Does the solution correctly implement all three filtering, selection, and sorting criteria, handling edge cases?
  • Efficiency: Is the solution performant in terms of time and space complexity, especially for large inputs? (e.g., O(N log K) or O(N log N) for time, O(N) or O(K) for space).
  • Clarity & Readability: Is the code well-structured, easy to understand, and does it follow good coding practices?
  • Problem Decomposition: How well is the problem broken down into logical steps and implemented?
  • Algorithm Choice: Justification for chosen sorting and selection algorithms (e.g., standard sort vs. heap-based selection).

Loading editor...