Design a Song Randomizer Avoiding Recent Repeats

Problem Design a song picker for a playlist of n songs: each call returns a uniformly random song, except that none of the 20 most recently played songs may be returned.

Input / Output

• Input: a playlist of n songs, plus repeated calls to next().
• Output: each call returns a song id drawn uniformly from the songs not currently in the last-20 window, and records it as played.

Constraints

• next() should be O(1). Rejection sampling — re-roll until a non-recent song turns up — degrades badly as n approaches 20.
• n may be far larger than 20, or only slightly larger.
• Edge case: if n <= 20 the exclusion window cannot be honoured as stated; clarify whether the window shrinks to n-1 or the rule relaxes.
• Uniformity is over the eligible pool, not over the whole playlist.

Example

• n = 30 with a window of 20 → exactly 10 songs are eligible at any moment; each next() returns one of those 10 with probability 1/10, after which the oldest of the 20 recents re-enters the pool.
• n = 21 → exactly 1 song is eligible, so playback is fully deterministic — worth surfacing rather than silently shipping.