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
Solution
from typing import List
def is_shuffle_segment(playlist: List[int], observed: List[int]) -> bool:
m = len(playlist)
if m == 0:
# No songs in playlist: only empty observation can be valid
return len(observed) == 0
P = set(playlist)
# All observed songs must belong to playlist
for x in observed:
if x not in P:
return False
# last occurrence index per song
last = {}
# We will intersect allowed residues r in [0..m-1] where cuts occur at indices congruent to r mod m.
# Each constraint from adjacent equal songs at positions p < i with i - p < m requires a cut in (p, i],
# i.e., r must be in residues of p+1..i modulo m (a circular interval).
diff = [0] * (m + 1) # difference array over residues 0..m-1
constraints = 0
for i, x in enumerate(observed):
if x in last:
p = last[x]
d = i - p
if d < m:
a = (p + 1) % m
b = i % m
if a <= b:
diff[a] += 1
diff[b + 1] -= 1
else:
# Wrap-around interval: [a..m-1] union [0..b]
diff[0] += 1
diff[b + 1] -= 1
diff[a] += 1
diff[m] -= 1
constraints += 1
last[x] = i
if constraints == 0:
# No short-gap repeats: any offset works
return True
# Check if any residue satisfies all constraints
run = 0
for r in range(m):
run += diff[r]
if run == constraints:
return True
return False
Explanation
Let m be the playlist size. Shuffle boundaries occur every m songs; choosing an offset t in [0, m] fixes all boundary positions at indices t, t+m, t+2m, ... (equivalently, residues r = t mod m). For any repeated song at positions p < i with gap i - p >= m, a boundary must exist between them regardless of offset. Only repeats with gap < m constrain r: there must be at least one boundary in (p, i], so r must equal the residue of some index in {p+1, ..., i} modulo m. Each such pair yields a circular interval of allowed residues. Intersect all these intervals. If their intersection is non-empty, we can choose such an r (thus an offset t), ensuring no block contains a duplicate and all songs lie in the playlist; otherwise the sequence is impossible under Shuffle. Using a difference array over residues 0..m-1 lets us compute the intersection of all circular intervals in O(n + m) time.
Time complexity: O(n + m). Space complexity: O(m + u).
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.