Detect shuffle-mode sequence
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Given a playlist of distinct songs and two player modes—Random (each next song chosen independently and uniformly at random, with replacement) and Shuffle (a random permutation is generated and played without repetition until exhaustion, then optionally reshuffled)—you begin listening at an arbitrary time and record a sequence of n songs. Design an algorithm that decides whether the observed sequence could have been produced by Shuffle mode (i.e., is consistent with some contiguous segment of one or more shuffled permutations). Explain the algorithm, analyze its time- and space-complexity, and discuss edge cases such as repeated songs and sequence length 1.
Quick Answer: This question evaluates algorithm design and analysis skills, focusing on reasoning about permutations, sequence consistency under different randomness models, and handling repeated elements within observed streams in the Coding & Algorithms domain.
You have a playlist P of m distinct song IDs. In Shuffle mode, the player picks a random permutation of P and plays it without repetition; when the permutation ends, a new permutation of P is picked, and playback continues. You start listening at an arbitrary time and record a contiguous sequence S of n songs. Determine if S could be produced by Shuffle mode, i.e., if there exists an offset t in [0, m] such that cutting S at indices t, t + m, t + 2m, ... yields segments in which no song repeats and every song in S is from P. Repeats are allowed only across these cut positions. Return true if such an offset exists, otherwise false.
Constraints
- 1 <= len(playlist) = m <= 200000
- 1 <= len(observed) = n <= 200000
- playlist contains distinct integers
- All observed songs must be in playlist for the answer to be true
- Song IDs fit in 32-bit signed integers
Hints
- Any valid segmentation corresponds to choosing a single offset t in [0, m] and then cutting every m songs thereafter.
- For any song that repeats at positions i < j with j - i < m, there must be a cut between i and j; this forces t modulo m to lie in a specific circular interval.
- Intersect all such circular intervals (for adjacent occurrences) to find if any t modulo m satisfies them all. Use a difference array on residues 0..m-1 for O(n + m) time.