How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Netflix.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Netflix during technical interviews.

Design playlist with add/remove/shuffle

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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.)*

Quick Answer: This question evaluates data structure design and algorithmic complexity skills, focusing on managing dynamic sets, uniform random selection, and average-case time/space trade-offs.

You are given a sequence of operations to perform on a playlist of unique integer song IDs. Implement an in-memory playlist that supports average O(1) add, remove, and shuffle operations, and return the result of each operation. For 'add(songId)', insert the song only if it is not already present. For 'remove(songId)', delete it only if it exists. For 'shuffle()', return one song currently in the playlist; if the playlist is empty, return None. In a real interview, any uniform random choice from the current playlist would be acceptable. For deterministic grading in this problem, use the following exact rule: keep songs in a dynamic array, remove a song by swapping it with the last song before deleting it, and on each non-empty shuffle update state = (1103515245 * state + 12345) % 2^31, then return songs[state % len(songs)]. The initial state is the given seed. If shuffle() is called when the playlist is empty, return None and do not update the state.

Constraints

0 <= len(operations) <= 200000
len(operations) == len(values)
Each operation is one of: 'add', 'remove', 'shuffle'
For 'add' and 'remove', songId is an integer in the range [-10^9, 10^9]
For 'shuffle', the corresponding value is None
0 <= seed < 2^31

Examples

Input: (["add", "add", "shuffle", "remove", "shuffle"], [10, 20, None, 10, None], 1)

Expected Output: [True, True, 10, True, 20]

Explanation: After adding 10 and 20, the first shuffle picks index 0 and returns 10. Removing 10 leaves only 20, so the second shuffle returns 20.

Input: (["shuffle", "add", "add", "remove", "shuffle"], [None, -5, -5, 7, None], 42)

Expected Output: [None, True, False, False, -5]

Explanation: The first shuffle is on an empty playlist, so it returns None. Adding -5 succeeds, adding it again fails, removing 7 fails, and the final shuffle returns -5.

Input: (["add", "add", "add", "remove", "shuffle", "remove", "shuffle", "add", "shuffle"], [7, 8, 9, 8, None, 7, None, 10, None], 1)

Expected Output: [True, True, True, True, 7, True, 9, True, 9]

Explanation: Removing 8 swaps in the last song, so the playlist becomes [7, 9]. The next shuffle returns 7. Removing 7 leaves [9], then adding 10 creates [9, 10], and the last shuffle returns 9.

Input: (["add", "add", "shuffle", "shuffle", "remove", "add", "shuffle", "shuffle"], [100, 200, None, None, 100, 300, None, None], 1)

Expected Output: [True, True, 100, 200, True, True, 200, 300]

Explanation: Two songs are added. The first two shuffles return 100 and 200 based on the deterministic state updates. After removing 100 and adding 300, the remaining shuffles return 200 and then 300.

Hints

You need fast membership checks and fast access to a song's current index.
Removing from the middle of an array is expensive; consider swapping the target with the last element before popping.

Quick Overview

This question evaluates data structure design and algorithmic complexity skills, focusing on managing dynamic sets, uniform random selection, and average-case time/space trade-offs.