Set with a fair random pick

Scenario

A music streaming app has a shuffle button on the list of songs a listener has liked. A listener can like and unlike songs all day, and the button must pick one liked song with equal chances for all of them.

The list can hold tens of thousands of songs, so each like, unlike and shuffle must take constant time.

To make the picks the same on every run, each shuffle comes with a number r that stands for the random draw.

Your task

Write run_picker(commands, values).

commands[i] is "like", "unlike" or "shuffle". For a like or an unlike, values[i] is a song id. For a shuffle, values[i] is the number r.
The liked songs sit in an array. A new song is added at the end. When a song is removed, the last song of the array moves into its place, and the array becomes one shorter.
A like returns 1 for a new song, and 0 when the song was already liked. An unlike returns 1 when the song was liked, and 0 otherwise.
A shuffle returns the song at position r mod n of the array, where n is the number of songs and positions start at 0. It returns -1 when no song is liked.
Return one number for each command, in order.

Examples

Example 1 (traced)#

text2 lines

Input:  commands = ["like", "like", "like", "unlike", "shuffle", "shuffle", "like"], values = [10, 20, 30, 10, 0, 1, 40]
Output: [1, 1, 1, 1, 30, 20, 1]

The trace shows the array after each command.

Step	Command	Array after	Answer
1	like 10	[10]	1
2	like 20	[10, 20]	1
3	like 30	[10, 20, 30]	1
4	unlike 10	[30, 20]: the last song, 30, moved into position 0	1
5	shuffle 0	[30, 20]: position 0 mod 2 = 0	30
6	shuffle 1	[30, 20]: position 1 mod 2 = 1	20
7	like 40	[30, 20, 40]	1

Example 2#

text2 lines

Input:  commands = ["shuffle", "like", "like", "unlike", "unlike", "shuffle"], values = [4, 5, 5, 6, 5, 9]
Output: [-1, 1, 0, 0, 1, -1]

The list is empty at the first shuffle. The second like of song 5 returns 0, and the unlike of song 6 returns 0. After song 5 is removed, the last shuffle finds the list empty again.

Example 3#

text2 lines

Input:  commands = ["like", "like", "shuffle", "shuffle", "shuffle"], values = [7, 8, 3, 4, 5]
Output: [1, 1, 8, 7, 8]

With two songs, r = 3, 4 and 5 give the positions 1, 0 and 1.

Constraints

1 ≤ commands.length = values.length ≤ 100,000
0 ≤ values[i] ≤ 1,000,000

What does n ≤ 100,000 tell you?

Looking for a song in an array costs up to one step for each liked song. With tens of thousands of songs and 100,000 commands, that is billions of steps. A table finds a song in one step.

But a table alone cannot pick by position, and an array alone cannot find a song. You need both.

Scenario

The list can hold tens of thousands of songs, so each like, unlike and shuffle must take constant time.

To make the picks the same on every run, each shuffle comes with a number r that stands for the random draw.

Your task

Write run_picker(commands, values).

commands[i] is "like", "unlike" or "shuffle". For a like or an unlike, values[i] is a song id. For a shuffle, values[i] is the number r.
The liked songs sit in an array. A new song is added at the end. When a song is removed, the last song of the array moves into its place, and the array becomes one shorter.
A like returns 1 for a new song, and 0 when the song was already liked. An unlike returns 1 when the song was liked, and 0 otherwise.
A shuffle returns the song at position r mod n of the array, where n is the number of songs and positions start at 0. It returns -1 when no song is liked.
Return one number for each command, in order.

Examples

Example 1 (traced)#

text2 lines

Input:  commands = ["like", "like", "like", "unlike", "shuffle", "shuffle", "like"], values = [10, 20, 30, 10, 0, 1, 40]
Output: [1, 1, 1, 1, 30, 20, 1]

The trace shows the array after each command.

Step	Command	Array after	Answer
1	like 10	[10]	1
2	like 20	[10, 20]	1
3	like 30	[10, 20, 30]	1
4	unlike 10	[30, 20]: the last song, 30, moved into position 0	1
5	shuffle 0	[30, 20]: position 0 mod 2 = 0	30
6	shuffle 1	[30, 20]: position 1 mod 2 = 1	20
7	like 40	[30, 20, 40]	1

Example 2#

text2 lines

Input:  commands = ["shuffle", "like", "like", "unlike", "unlike", "shuffle"], values = [4, 5, 5, 6, 5, 9]
Output: [-1, 1, 0, 0, 1, -1]

The list is empty at the first shuffle. The second like of song 5 returns 0, and the unlike of song 6 returns 0. After song 5 is removed, the last shuffle finds the list empty again.

Example 3#

text2 lines

Input:  commands = ["like", "like", "shuffle", "shuffle", "shuffle"], values = [7, 8, 3, 4, 5]
Output: [1, 1, 8, 7, 8]

With two songs, r = 3, 4 and 5 give the positions 1, 0 and 1.

Constraints

1 ≤ commands.length = values.length ≤ 100,000
0 ≤ values[i] ≤ 1,000,000

What does n ≤ 100,000 tell you?

Looking for a song in an array costs up to one step for each liked song. With tens of thousands of songs and 100,000 commands, that is billions of steps. A table finds a song in one step.

But a table alone cannot pick by position, and an array alone cannot find a song. You need both.