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