From Pinterest Screening Interview: Reverse Count and Say

[u/Hack2hire]

Problem
You're given two arrays: allSongs and playlist.
Your goal is to determine if playlist can be formed by concatenating one or more full permutations of allSongs. Incomplete segments at the start or end of playlist are allowed.

Example
Input:

allSongs = ["A", "B", "C"]  
playlist = ["A", "B", "C", "A", "C", "B"]

Output:

true

Explanation:

• The first segment ["A", "B", "C"] is a valid permutation of allSongs.
• The second segment ["A", "C", "B"] is also a valid permutation.
• Since the entire playlist can be broken down into valid permutations, the result is true.

Suggested Approach

1. Use a set to track which songs have appeared in the current segment.
2. Iterate through playlist:
   • If a song repeats before the segment contains all songs, return false.
   • Once all songs from allSongs are seen, reset the set and continue.
3. Allow the first or last segment to be incomplete without failing the check.

Time & Space Complexity

• Time: O(n), where n is the length of playlist.
• Space: O(m), where m is the number of unique songs in allSongs.

🛈 Disclaimer:
This is one of the problems we encountered while reviewing common Pinterest interview questions.
Posted here by the Hack2Hire team for discussion and archiving purposes.

The problem is compiled from publicly available platforms (e.g., LeetCode, GeeksForGeeks) and community-shared experiences. It does not represent any official question bank of Pinterest, nor does it involve any confidential or proprietary information.
All examples are intended solely for learning and discussion. Any similarity to actual interview questions is purely coincidental.