Quick Overview

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.

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.

Overview: 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

  1. Any valid segmentation corresponds to choosing a single offset t in [0, m] and then cutting every m songs thereafter.
  2. 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.
  3. 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.

Loading coding console...

Show the approach

Approach

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)